Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

19 May, 2024: Line wrapping has been changed to be more consistent with Usenet standards.
 If you find that it is broken please let me know here rocksolid.nodes.help


devel / comp.lang.c++ / "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen

SubjectAuthor
* "Inside STL: The unordered_map, unordered_set, unordered_multimap,Lynn McGuire
`* Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordTim Rentsch
 `* Re: "Inside STL: The unordered_map, unordered_set,Lynn McGuire
  +* Re: "Inside STL: The unordered_map, unordered_set,Alf P. Steinbach
  |`- Re: "Inside STL: The unordered_map, unordered_set,Lynn McGuire
  `- Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordTim Rentsch

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

<ub0rhv$28f2$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=994&group=comp.lang.c%2B%2B#994

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.76-231-159-151.lightspeed.hstntx.sbcglobal.net!not-for-mail
From: lynnmcgu...@gmail.com (Lynn McGuire)
Newsgroups: comp.lang.c++
Subject: "Inside STL: The unordered_map, unordered_set, unordered_multimap,
and unordered_multiset" by Raymond Chen
Date: Wed, 9 Aug 2023 15:05:20 -0500
Organization: A noiseless patient Spider
Message-ID: <ub0rhv$28f2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Aug 2023 20:05:20 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="76-231-159-151.lightspeed.hstntx.sbcglobal.net:76.231.159.151";
logging-data="74210"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Content-Language: en-US
 by: Lynn McGuire - Wed, 9 Aug 2023 20:05 UTC

"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

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

<86jztw715c.fsf@linuxsc.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1018&group=comp.lang.c%2B%2B#1018

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17...@z991.linuxsc.com (Tim Rentsch)
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=
 by: Tim Rentsch - Tue, 15 Aug 2023 15:53 UTC

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

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

<ubjgce$3euv0$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1034&group=comp.lang.c%2B%2B#1034

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: lynnmcgu...@gmail.com (Lynn McGuire)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The unordered_map, unordered_set,
unordered_multimap, and unordered_multiset" by Raymond Chen
Date: Wed, 16 Aug 2023 16:51:08 -0500
Organization: A noiseless patient Spider
Lines: 47
Message-ID: <ubjgce$3euv0$1@dont-email.me>
References: <ub0rhv$28f2$1@dont-email.me> <86jztw715c.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 16 Aug 2023 21:51:10 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="147152e1838b9b0a90d523233de00469";
logging-data="3636192"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19DnvN06HGcrjEhw7dXq2hfc8fPBQuOqXc="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:RbwjcwcwfunkoOugfT26qSxY7Rk=
In-Reply-To: <86jztw715c.fsf@linuxsc.com>
Content-Language: en-US
 by: Lynn McGuire - Wed, 16 Aug 2023 21:51 UTC

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

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

<ubjh3a$3f0nk$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1036&group=comp.lang.c%2B%2B#1036

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: alf.p.st...@gmail.com (Alf P. Steinbach)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The unordered_map, unordered_set,
unordered_multimap, and unordered_multiset" by Raymond Chen
Date: Thu, 17 Aug 2023 00:03:21 +0200
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <ubjh3a$3f0nk$2@dont-email.me>
References: <ub0rhv$28f2$1@dont-email.me> <86jztw715c.fsf@linuxsc.com>
<ubjgce$3euv0$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 16 Aug 2023 22:03:22 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="292507041f55db43132fdd889eb7131b";
logging-data="3638004"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+GZeidRgFGex3XwsZk0DZn"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:n5e1cI3lYl2J7iUTziS5xHOZ5Hs=
Content-Language: en-US
In-Reply-To: <ubjgce$3euv0$1@dont-email.me>
 by: Alf P. Steinbach - Wed, 16 Aug 2023 22:03 UTC

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

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

<ubjir5$3f8vf$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1037&group=comp.lang.c%2B%2B#1037

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: lynnmcgu...@gmail.com (Lynn McGuire)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The unordered_map, unordered_set,
unordered_multimap, and unordered_multiset" by Raymond Chen
Date: Wed, 16 Aug 2023 17:33:07 -0500
Organization: A noiseless patient Spider
Lines: 18
Message-ID: <ubjir5$3f8vf$1@dont-email.me>
References: <ub0rhv$28f2$1@dont-email.me> <86jztw715c.fsf@linuxsc.com>
<ubjgce$3euv0$1@dont-email.me> <ubjh3a$3f0nk$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 16 Aug 2023 22:33:10 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="109ecc078011588cf6b1f87cb1a3d083";
logging-data="3646447"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19WbzPI3T6jvFBUx8c6L38TcDsYfI6kJ4o="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:PA1YnKFQuDYhfubInrJ+g5eZdq8=
In-Reply-To: <ubjh3a$3f0nk$2@dont-email.me>
Content-Language: en-US
 by: Lynn McGuire - Wed, 16 Aug 2023 22:33 UTC

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

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

<86fs4i5rd8.fsf@linuxsc.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1042&group=comp.lang.c%2B%2B#1042

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17...@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen
Date: Wed, 16 Aug 2023 19:34:27 -0700
Organization: A noiseless patient Spider
Lines: 51
Message-ID: <86fs4i5rd8.fsf@linuxsc.com>
References: <ub0rhv$28f2$1@dont-email.me> <86jztw715c.fsf@linuxsc.com> <ubjgce$3euv0$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="a8782d2d7d1c356e90db8dd7e2df2f84";
logging-data="3822203"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/3YUDbSHIJOWNDtgUDVelGQ9Hy5KyDcPc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:lx+oaVsGwl+rGm+ozOP2A9YH95M=
sha1:Tb1hTpTTR6hPZPPAlEM9NJAfLXw=
 by: Tim Rentsch - Thu, 17 Aug 2023 02:34 UTC

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.


devel / comp.lang.c++ / "Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset" by Raymond Chen

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor