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

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

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

Show all headers | View raw

Lynn McGuire <lynnmcguire5@gmail.com> writes:

> On 8/15/2023 10:53 AM, Tim Rentsch wrote:
>
>> 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).
>
> What if your hash table is composed of chunks instead a contiguous
> section of memory ?

I'm not sure what you mean.  Something like a two-level array,
where there might be 200 pointers to blocks of 100 buckets each?
That kind of organization shouldn't have any effect on my
statement.

Back to comp.lang.c++ | Previous | Next — Previous 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