"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

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

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

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

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

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.