Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #91259

Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen

Show key headers only | View raw

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).

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

"Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen Lynn McGuire <lynnmcguire5@gmail.com> - 2023-08-09 15:05 -0500
  Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-15 08:53 -0700
    Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen Lynn McGuire <lynnmcguire5@gmail.com> - 2023-08-16 16:51 -0500
      Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-17 00:03 +0200
        Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen Lynn McGuire <lynnmcguire5@gmail.com> - 2023-08-16 17:33 -0500
      Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-16 19:34 -0700

csiph-web