[bluGill]

In the mid 1990s when C++ was getting std::map and the other containers CPU caches were not a big deal. Average case was the correct thing to optimize for. These days CPU caches are a big deal and so your average case is typically dominated by CPU cache miss pipeline stalls. This means for most work you need different data structures. The world is still catching up to what this means.

[codelobe]

Well, Red-Black algos are supposed to be better at cache-locality, but I have an AVL-tree impl (ugg jokes, again: AVUL (ALV) is the "evil" tree of "forbidden" {carnal?} wisdom from The Garden of Eden, associated with Yggdrasil/Odin [a "pagan" God of Balance & Pleasure]) that has improved cache locality since its data nodes can be made to contain AvlTreeNode structure(s), and avoid copying any data, as users are made to provide node alloc/free function pointers to this C lib's Tree "constructor". This means, for real example, I have a command line option interpreter with const structures for each option, each node added to two AVL trees (to find by unicode codepoint and find by length prefixed unicode string name). C++ STL Map implementations can not conditionally generate code for const types and thus do needless coppies, whereas my C collections API causes 0 calls to malloc (vs STL's 2 mallocs per node insert). NodeAlloc is just pointer math to get at the apt AvlNode, NodeFree is NoOp.

Benchmarking the STL vs my AVL approach results in millions of times quicker cmd line opt interpretaion (for my gnu getopt replacement lib) due to reduction of pointer chasing...

And if I want to do something similar in C++ (overloading operator new), I have to instantiate multiple copies of the Tree code, one per each "class". What if I want to use my Sortable class with various allocators: OBJ cache, dynamic GC'd, static (no alloc, its in the .data section already)...? Well then I get N copies of EXACT SAME template code for no real reason, only differing in delete and new [con|de]structors. The cache-misses galore this causes isn't even fair to bench against the C w/ fn() ptr approach.

[bluGill]

Try benchmarking on something from 1995, like a 80486. Cache misses won't matter much.