Path: csiph.com!weretis.net!feeder8.news.weretis.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: 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: <86jztw715c.fsf@linuxsc.com> 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= Xref: csiph.com comp.lang.c++:91283 Lynn McGuire writes: > On 8/15/2023 10:53 AM, Tim Rentsch wrote: > >> Lynn McGuire 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>> 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.