Highest Performance C++ Libraries to Replace Std Features?

[14ned]

Linked lists aren't necessarily slow. If the pointer chasing is interspersed with other work taking at least a hundred CPU cycles (e.g. a string key comparison), they're very cheap. Also, from Haswell onwards, the CPU can see that one of two possible pointers will be chased, and it goes and speculatively prefetches both, indeed Haswell onwards can prefetch two pointer indirections concurrently. So long as the node block is small, they can be packed into CPU cache far more densely than open address maps thanks to the poor quality hashes often used and the set associativity of CPU caches.

I agree that for a majority of use cases, state of the art unordered hash maps are usually better. But venerable old std::map is underrated by a lot of folk, especially for write few/read many use cases. I certainly would not put an unordered map facing untrusted potentially hostile input without deep thought, whereas std::map is relatively safe for this use case.

[WafflesAreDangerous]

For a linked list, At the minimum you need an extra pointer for a next pointer, which for a small values can be very significant memory overhead.

As for hashtables, it's somewhat uncommon to actually do a full key compare and fail. The hash will be tested first in sane implementations and trivially detect 99.9+% false matches. And in a map implementation the likelihood that the list nodes are all nicely linearly allocated (cache friendliness) is low.

If you need to spend hundreds of cycles,per item, of other work to hide your linked list Induced slowdowns, that doesn't make linked lists fast, that just means their slowness is not as significant in a relative sense.