Comment by int_19h
1 day ago
We're using self-balancing trees for std::map because the specification for std::map effectively demands that given all the requirements (ordering, iterator and pointer stability, algorithmic complexity of various operations, and the basic fact that std::map has to implement everything in terms of std::less - it's emphatically not a hash map). It has nothing to do with ABI.
Are you rather thinking of std::unordered_map? That's the hash map of standard C++, and it's the one where people (rightfully) complain that it's woefully out of date compared to SOTA hashmap implementations. But even there an ABI break wouldn't be enough, because, again, the API guarantees in the Standard (specifically, pointer stability) prevent a truly efficient implementation.
Are there open source libraries that provide a better hash map? I have an application which I've optimized by implementing a key data structure a bunch of ways, and found boost::unordered_map to be slightly faster than std::unordered_map (which is faster than std::map and some other things), but I'd love something faster. All I need to store are ~1e6 things like std::array<int8_t, 20>.
You should probably use either boost::unordered_flat_map or absl::flat_hash_map if you don't need ordering. Especially with 20-byte values. (Though you didn't mention the key type). If you're dealing with building against Boost already, I'd just switch and measure it.
https://github.com/boostorg/boost_unordered_benchmarks/tree/... (Via a response from the boost authors in https://www.reddit.com/r/cpp/comments/yikfi4/boost_181_will_...) has more benchmarks depending on your pattern.