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.