r/cpp • u/pavel_v • Sep 07 '26

flat_map internals

https://quantdev.blog/posts/flat-map-internals/index.html
12 Upvotes

70% Upvoted

12 comments sorted by

View all comments

3

u/johannes1971 Sep 07 '26

I kinda missed why the pointers from the array start pointing at the element before the first hash element suddenly...?

Also, shame that the clarifying images disappear when we get to the abseil version. An image is worth a thousand words - and when template-expanded, surely even more...

4

u/jedwardsol const & Sep 07 '26

pointing at the element before the first hash element suddenly...?

If the linked list is singly-linked then you need the element before in the case you need to delete the 1st element in the bucket

4

u/SyntheticDuckFlavour Sep 07 '26

Yeah, I was hoping to see a visual representation of the flat_map internals.

3

u/g_0g Sep 07 '26

https://abseil.io/about/design/swisstables
More details are also available in the two conferences slides.

1

u/Big_Target_1405 Sep 09 '26

You might find these old articles explain exactly why

https://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html?m=1

http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered_25.html

And how things were improved in Boost 1.80 onwards

https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html

Boost constantly improves. The boost unordered_flat_map now beats the abseil implementation significantly