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

Dave Abrahams dave at boostpro.com
Sat Apr 7 07:56:58 PDT 2012

on Sat Apr 07 2012, David Chisnall <csdavec-AT-swan.ac.uk> wrote:

> 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.

Speaking of cache utilization, it's hard to beat btrees.  I don't know
if you can implement the requirements of std::map with btrees, though:


OK, re-lurking...

Dave Abrahams
BoostPro Computing

More information about the cfe-dev mailing list