Re: [boost] unordered_map implementation

Em 19 de fev de 2022, à(s) 19:23, Peter Dimov via Boost escreveu:

I've been helping Christian Mazakas maintain Unordered, and we've been looking into trying to improve its performance on the synthetic benchmarks we have for it

(https://github.com/boostorg/unordered/tree/develop/benchmark)

One of the things that are hurting us is that we need to do a double indirection in order to find an element, because Unordered uses a singly-linked list for all its nodes, with the bucket array pointing at the element before the first one (in order to be able to support erasing.)

There's also the option of using a doubly-linked list, which however increases the memory footprint.

I'm looking at the iterator invalidation rules for std::unordered_map, and iterators are invalidated on every rehash. This makes me wonder why is it necessary to have all the elements in a single list, as every implementation seems to do.

It seems to me that it's possible to just have singly- linked lists for each bucket, and then have a "fat" iterator that contains the bucket index and the pointer to the element. On increment, when the end of the bucket list is reached, the iterator can just go to the next non-empty bucket.

Is there something I'm missing in the requirements that renders this implementation non-conforming?

You may find this relevant: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf Joaquín M López Muñoz