Comment by jsheard
1 day ago
Rust also switched their standard maps over to Swisstables a while ago. Unfortunately despite the original implementation being in C++, I don't think it's possible for C++ implementations to do the same with the STL maps due to constraints imposed by the spec. They'd have to create a new STL type for them.
Yes, in C++ in 2011 they standardized the hash table design you'd have been shown in a 1980s (or maybe 1990s if you got unlucky in where you went to school) Data Structures class. They called this type std::unordered_map
This was a Closed Addressing aka Separate Chaining table. The idea is easy enough that it's actually an Advent Of Code problem one year which is why this design is much older than the modern efficient Open Addressing tables. In C++ with std::unordered_map you are guaranteed that the address of items in the table won't change while they're in the table, this works because they're not actually stored directly in the table. You also provided an API to work with these chains of related items and to fiddle with "how full" the table is.
This API makes complete sense for a Closed Addressing table, but both the API functions and the pointer stability guarantee don't make any sense for Open Addressing.
If you only need the pointer stability you can pay just for that, Abseil offers a compatible type with that property, but if you need all the Chaining APIs (and you might in principle) then it doesn't have those, too bad.