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

[Dave Abrahams]

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:

https://github.com/boostcon/2011_presentations/raw/master/tue/proposed_b_tree_library.pdf
http://blip.tv/boostcon/the-proposed-boost-b-tree-library-5349968

OK, re-lurking...

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com