The problem with RedBlackTree is that it's cache-unfriendly due
to the
memory allocation and per-node pointers. One reason quicksort
performs
so well is because it works in-place, and the partition
operation
accesses elements bilinearly (i.e., two linear traversals over
the same
stretch of memory interleaved with each other), so it's very
likely that
most of the accesses will hit the cache (possibly even all, if
hardware
prefetching is present). Whereas with RedBlackTree, it's
jumping all
over memory, so there will be a higher rate of cache misses and
the
resulting slow RAM fetches. Plus, memory allocation is slooow,
and is
best avoided where possible.
In an interview Stepanov said he would have used b* trees instead
for this reason if he were writing STL today.
Here is a (dated) benchmark comparison of hash libraries:
https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
