I've been going through Boost's unordered_flat_map implementation. Here's an overview:
I also read the source code a little bit, but not fully. The metadata bytes use the value 1 to indicate so called "sentinel" byte. As far as I understand, this sentinel byte is used for iterators to know where to stop. There is only one sentinel byte in the entire hash map, and it is at the end of the map.
It makes me wonder why we need it to begin with. The hash map has to track the number of buckets or groups of buckets, otherwise calculating a group index from the hash wouldn't be possible.
Therefore we know in advance how many buckets we have, and so we know when iteration should end, without the need of sentinel byte.
And as far as I understand, we still need to inspect all the buckets, or rather their metadata. In order to know whether the bucket holds a value or is empty.
The situation seems similar to strings ending with \0 byte vs keeping track of the string's length (in which case we don't need the \0 marker).
Is the sentinel byte some kind of optimization?
Am I missing something here? Is there another reason for the sentinel byte? Can we implement the flat map without the sentinel, and with zero being the only special metadata byte?