Hacker News Reader

In addition to the sibling’s comment on explicitly passing inna comparator, note that std::map is an ordered dictionary and requires an ordering on your elements. It sounds like you may have preferred hash_map

View on HN

I don't know, the way std::pair works is that it compares the two elements' `first`, or their `second` if `first` happens to be equal. That seems pretty good; lookup should still be O(n).

I'll keep hash_map in mind though, and maybe do some performance testing to see which is actually faster.

std::map is incredibly slow (and allocates willy-nilly), see https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... for a comparison of modern hash maps. Or at least boost::flat_map if you need ordering but don't do many insertions / removals and care instead for fast iteration on the map.

Note: when I say "incredibly slow", it is relative to what is possible to achieve in C++ - it will still roll over many other languages's map implementations.

In some cases, the performance of std::unordered_map is fixable with a custom allocator: https://github.com/Const-me/CollectionMicrobench

Chromium advised for their typical use cases to use std::map in favor of std::unordered_map. And they also provide own version of flat_map.

[1] - https://chromium.googlesource.com/chromium/src/+/master/base...

Reply on news.ycombinator.com