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|2 years ago