[ahartmetz]

AFAIK, std::map is also OK for what it is: an ordered, node-based (tree) map. These are (almost) always slower than hash tables. Of course, std::unordered_map, the std hash table, sucks because of unforced errors. For that, there is boost::unordered_flat_map.

[tialaramex]

std::map will be a Red Black Tree, as with most of the other container types this really likes pointer chasing

Unlike in std::unordered_map you are getting some value here, the RB tree is able to achieve meaningful efficiency gains from its use of pointers. The trouble is that your computer isn't a PDP-11, a hybrid which does fewer dereferences but has more locality will trade well here on a real computer built this century.

So, I'm torn, it's not awful but it's a problem that std::map is basically obliged to be a Red Black Tree even though that's not a good fit for today's machines.