Inside STL: unordered_map, unordered_set, unordered_multimap, & unordered_multiset -- Raymond Chen
The C++ standard library provides hash-based associative containers
unordered_
, unordered_
, unordered_
, and unordered_
.
All of these collections are hash tables with different payloads. The unordered_
and the unordered_
use a std::pair<Key, Value>
as the payload, whereas the the unordered_
and the unordered_
use a Key
as the payload.
Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset
By Raymond Chen
From the article:
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.
C++ standard library implementations instead structure the hash table like this:
struct hashtable { using hint = std::list<payload>::iterator; std::list<payload> list; std::vector<hint> buckets; };The
list
is a linked list of payloads, sorted by bucket. Thebuckets
is a vector of iterators (pointers) into the list that tells you where each bucket begins. Each bucket implicitly ends when the next bucket begins, or (for the last bucket) when the end of the list is reached.