unordered_map implementation

From: Peter Dimov (pdimov_at_[hidden])
Date: 2022-02-19 18:22:48

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?