[Const-me]

> Even for those languages, unless all relevant data is in simple arrays, making assertions about locality is hard.

It depends on the libraries you use. Take a look: https://github.com/Const-me/CollectionMicrobench

As you see, in practice, a good linked list is same or slightly faster than std::vector. And it’s consistently 2-3 times faster than equally linked std::list.

That’s not just synthetic tests. Recently, I’ve got 2.5x performance improvement in my app just by switching from std::unordered_map to CAtlMap with the same keys/values.

Theoretically, C++/11 fixes that with stateful allocators. Practically, I’ve not seen good open source ones with the performance comparable to CAtlPlex that powers these ATL node-based collections. I’m not even sure it’s possible. STL is too standardized and too old. It might be there’s no room in its allocators API for sufficient level of integration between a collection and it’s backing stateful allocator.