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

Groups > comp.lang.c++ > #91235 > unrolled thread

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

Back to article view | Back to comp.lang.c++

Contents

  "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

#91235 — "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen

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

We have used none of these in our software.

Lynn

[toc] | [next] | [standalone]

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

[toc] | [prev] | [next] | [standalone]

#91275

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 ?

The only contiguous memory that I know of is std::string and 
std::vector.  And I am not sure about std::string.

Lynn

[toc] | [prev] | [next] | [standalone]

#91277

On 2023-08-16 11:51 PM, Lynn McGuire wrote:
> 
> The only contiguous memory that I know of is std::string and 
> std::vector.  And I am not sure about std::string.

`std::string` got contiguous buffer at the committee meeting at 
Lillehammer, Norway, in 2005, and that wording was adopted for the 
formal, in C++11.

- Alf

[toc] | [prev] | [next] | [standalone]

#91278

On 8/16/2023 5:03 PM, Alf P. Steinbach wrote:
> On 2023-08-16 11:51 PM, Lynn McGuire wrote:
>>
>> The only contiguous memory that I know of is std::string and 
>> std::vector.  And I am not sure about std::string.
> 
> `std::string` got contiguous buffer at the committee meeting at 
> Lillehammer, Norway, in 2005, and that wording was adopted for the 
> formal, in C++11.
> 
> - Alf

Thats what I thought.

Thanks,
Lynn

[toc] | [prev] | [next] | [standalone]

#91283

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web