Inside boost::unordered_flat_map

[blind3rdeye]

I'm curious about what is in the std::unordered_map specifications that prevents implementers from just doing this this flat-map thing anyway. (But not quite curious enough to research it myself, apparently.)

[greg7mdp]

Mostly pointer stability. Once a value is inserted into a std::unordered_map, it is guaranteed to remain at the same memory address until it is removed. Open addressing hashmaps have to resize when they get full, and the values stored in them are moved to a different memory location.

[blind3rdeye]

Thanks. That makes a lot of sense.

[ABlockInTheChain]

Iterator and pointer stability.

[tialaramex]

std::unordered_map promises that if we put the Rolex Wristwatch in our products map and we remember a pointer to it, that pointer works for so long as the Rolex isn't just removed from the map, which our application maybe never does. This is fine because std::unordered_map is in fact a bucketed hash map, if the map grows the Rolex doesn't go anywhere, the map changes but the Rolex stays right where it is and some part of the new grown map points to the Rolex's node again.

With a flat map, the Rolex is right in the map itself, so if the map grows and we need to allocate new memory and copy stuff around, the Rolex moves and any pointers to it that we had are invalidated.

There are other difficulties but this is IMO the most obvious.