Re: unordered_map implementation

From: Joaquín M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2022-02-19 21:10:36

> Em 19 de fev de 2022, Ã (s) 19:23, Peter Dimov via Boost <boost_at_[hidden]> 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