Path: csiph.com!1.us.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen
Date: Tue, 15 Aug 2023 08:53:19 -0700
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <86jztw715c.fsf@linuxsc.com>
References: <ub0rhv$28f2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="4aa43ab23f99b81d777a1b3458fe2d41"; logging-data="3042514"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18T8ur+581KDJ1uxwjW5v+lIlNr8645p4Y="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:HsTZJ0EfhcE25yKOnMuY4psx4rk= sha1:52VwkyA2XfpX4ObJEhKnY99zric=
Xref: csiph.com comp.lang.c++:91259

Lynn McGuire <lynnmcguire5@gmail.com> writes:

> "Inside STL:  The unordered_map, unordered_set, unordered_multimap, and
> unordered_multiset" by Raymond Chen
>    https://devblogs.microsoft.com/oldnewthing/20230808-00/
>
> "The C++ standard library provides hash-based associative containers
> unordered_map, unordered_set, unordered_multimap, and
> unordered_multiset."
>
> "All of these collections are hash tables with different payloads.  The
> unordered_map and the unordered_multimap use a std::pair<Key, Value>
> as the payload, whereas the the unordered_set and the
> unordered_multiset use a Key as the payload."
>
> "Conceptually, the hash table consists of a bunch of buckets, and each
> bucket contains a linked list 

Presumably, points to a linked list, rather than containing it.

> of the nodes that fall into that
> bucket.  (This design is known as open hashing or separate chaining.)
> However, that's not how the information is structured internally,
> because iterating through a traditionally-structured hash table
> requires more state than a single pointer:  When you reach the end of
> each hash chain, you need some other information to tell you which
> chain to enumerate next."

Conceptually, an iterator over a hash table needs to hold two pieces of
information:  one to indicate the current item, and one to indicate the
hash table as a whole.  That need holds for both linked-list style hash
tables and rehash-and-grow-when-too-full style hash tables.

However, if each item in the linked list has a reference (or pointer) to
the overall hash table, then iterators can be implemented that hold only
a single pointer to the list element in question (or perhaps to a dummy
list element, to handle the edge conditions).