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.

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. The buckets 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.