[cfe-dev] libc++ red-black tree: halving the branches

[David Chisnall]

On 7 Apr 2012, at 14:28, Matthieu Monrocq wrote:

> If we are speaking alternative implementations of std::map and co, does anyone know if a Skip List has ever been used to implement those ? They are in theory equivalent to red-black trees and avl trees, but use randomness instead of rebalancing which make them *much* simpler: you don't need a book to code them.

Skip lists, in general, have very poor cache utilisation which affects their performance in real code but doesn't always show up in microbenchmarks.  We based a lot of code around skip lists when they were cool in the '90s and would now suffering for it if not for the fact that computers became so fast in the intervening period that we could strip out those caches completely and still be fast enough.

David