Well, std::unordered_map is faster than than std::map, but it is still slow, since it uses lists for its buckets, with lots of dynamic allocation. See also:

https://stackoverflow.com/a/42588384/1593077

and the link there. Not sure that's what GP meant though.

I don't believe it has to, some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type.

And I don't like it when people use ridiculous hyperbole to describe what is in reality barely perceptible overhead, so it would be good if the person I originally responded to came out and defended his POV. Hopefully using actual numbers instead of agitated handwaving and screaming...

> some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type

Pretty sure that makes it impossible to implement merge without pointer/iterator invalidation, which is a constraint imposed by the standard (https://en.cppreference.com/w/cpp/container/unordered_map/me...).

> it would be good if the person I originally responded to came out and defended his POV

See https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... if you want numbers, or for example this talk by the same author https://www.youtube.com/watch?v=M2fKMP47slQ.

Abseil has a btree based hash map and it performs much better. I think it maintains the same constrains(iterator invalidation/exception safety...) as std::unordered_map.

The issue is that the implementors won't change their implementation of unordered_map as it's an ABI break, to say it simply. It could be better. But also, there are other tools like flat maps/open addressing that are not done in the std library.