Most of the STL data structures guarantee stable element addresses, completely precluding any kind of cache-friendly rearrangement. They also require fast stab

Most of the STL data structures guarantee stable element addresses, completely precluding any kind of cache-friendly rearrangement. They also require fast stable iterators that are cheap to pass by value, constraining the implementation further. For this reason I am fairly confident that every std::map/set ever written will be a balanced tree with parent pointers. There's just no latitude to do anything else.