Boost unordered_flat_map: why does it need sentinel?

1 week ago 6
ARTICLE AD BOX

I've been going through the boost's unordered_flat_map implementation. Here's an overview:

https://www.boost.org/doc/libs/latest/libs/unordered/doc/html/unordered/structures.html#structures_open_addressing_containers

I also read the source code a little bit, but not fully. The metadata bytes use value of 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 at the end of the map.

It makes me wonder though, why do we need it to begin with? The hash map has to track the number of buckets. And therefore we know in advance how many buckets we have: it is the number of groups multiplied by 15. And so we know when iteration should end, without the need of sentinel byte.

Am I missing something here? Is there another reason for the sentinel byte?

Read Entire Article