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

Joerg Sonnenberger joerg at britannica.bec.de
Sat Apr 7 07:07:17 PDT 2012

On Sat, Apr 07, 2012 at 03:28:05PM +0200, 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.
> I have never heard about any performance comparison between the two though,
> and I am not really I could come up with an optimized implementation...

Skip list tend to be fairly bad for modern memory architectures,
especially in multi-threaded applications. The problem is that they result
in a lot of cache trashing, so they are only beneficial if you have a
really small hot set.


More information about the cfe-dev mailing list