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

Christopher Jefferson chris at bubblescope.net
Sat Apr 7 07:45:27 PDT 2012

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.

I have not looked closely at skip lists, but I believe that the various complexity and stability requirements on std::map and the other tree algorithms place strong restrictions on the implementation that can be used. In particular they say that certain complexity requirements must be reached, which isn't guaranteed by random algorithms.

I'm sure implementing such algorithms in an STL-like way would be interesting, and might well be a welcome contribution to boost.


More information about the cfe-dev mailing list