MySmartCoPilot
Ask Go Pro Your pass Pass ends in 7 days

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

C++  Module 10 – Standard containers

std::unordered_map, hashing and iteration order

Use std::unordered_map for fast average lookups, write hash functions for your own key types, and stop relying on iteration order, with runs on two compilers.

  • Intermediate
  • 25 minutes
  • Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
  • By MySmartCoPilot

What you will learn

  • Use unordered containers for fast average lookups
  • Write hash functions for your own types
  • Avoid depending on iteration order

Before you start

What you’ll learn · Before you start

What you will learn

  • Use unordered containers for fast average lookups
  • Write hash functions for your own types
  • Avoid depending on iteration order

Before you start

On this page

std::unordered_map and std::unordered_set are hash tables. They compute a hash of each key, a number, use it to pick one of many buckets, and keep the elements of each bucket in a short chain, so finding, inserting and erasing a key take constant time on average, however many keys there are. Choose them when you look keys up and never need the keys in order. The price is in the details: lookups slow down to linear time when many keys share a bucket, your own key types need a hash function, and the order in which the container lists its elements is unspecified. It differs between standard libraries and changes when the table grows, so code that prints or compares in that order breaks on another compiler.

This lesson counts words in both libraries and compares their orders, writes hash functions for a key type of its own and measures what a weak one costs, watches a table grow, and shows the bug that inserting during a loop causes.

Counting words, and the order they come back in

word_order.cpp C++ · word_order.cpp 
// Counting words with std::unordered_map, and the order in which the map gives them back: an order that depends on
// the hash function, the number of buckets and the library, and that changes when the map rehashes.
#include <algorithm>
#include <print>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

int main() {
    std::unordered_map<std::string, int> count;
    for (std::string w : {"ship", "anchor", "sail", "ship", "rope", "deck", "sail", "mast", "ship"}) ++count[w];

    std::println("{} words in {} buckets, load factor {:.2f}", count.size(), count.bucket_count(), count.load_factor());
    for (const auto& [word, n] : count) std::println("  {:<7} {}  (bucket {})", word, n, count.bucket(word));

    count.reserve(100);  // more buckets: every word is rehashed into a new bucket
    std::print("after reserve(100), {} buckets:", count.bucket_count());
    for (const auto& [word, n] : count) std::print(" {}", word);
    std::println("");

    // Output that must not depend on the library: copy the elements out and sort them.
    std::vector<std::pair<std::string, int>> sorted(count.begin(), count.end());
    std::ranges::sort(sorted);
    std::println("sorted: {}", sorted);
}
The same six words with libc++ and with libstdc++ Python · word_order_session.py 
from session import run

# word_order.cpp with libc++ (Apple clang), then with libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -Wall -Wextra word_order.cpp -o word_order
./word_order
g++-16 -std=c++23 -Wall -Wextra word_order.cpp -o word_order-gcc
./word_order-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra word_order.cpp -o word_order
$ ./word_order
6 words in 11 buckets, load factor 0.55
  mast    1  (bucket 5)
  deck    1  (bucket 2)
  anchor  1  (bucket 10)
  rope    1  (bucket 3)
  sail    2  (bucket 4)
  ship    3  (bucket 0)
after reserve(100), 101 buckets: mast deck anchor rope sail ship
sorted: [("anchor", 1), ("deck", 1), ("mast", 1), ("rope", 1), ("sail", 2), ("ship", 3)]
$ g++-16 -std=c++23 -Wall -Wextra word_order.cpp -o word_order-gcc
$ ./word_order-gcc
6 words in 13 buckets, load factor 0.46
  mast    1  (bucket 7)
  deck    1  (bucket 7)
  rope    1  (bucket 9)
  sail    2  (bucket 8)
  anchor  1  (bucket 5)
  ship    3  (bucket 5)
after reserve(100), 103 buckets: ship anchor sail rope deck mast
sorted: [("anchor", 1), ("deck", 1), ("mast", 1), ("rope", 1), ("sail", 2), ("ship", 3)]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 word_order_session.py

The counts agree, and almost nothing else does:

  • libc++ used 11 buckets for the six words and libstdc++ 13; the standard leaves the number of buckets a table starts with, and how it grows, to each library.
  • The words came out in two different orders, because each library has its own hash function for strings and its own bucket counts, and the bucket of a word follows from both.
  • In libstdc++, two buckets held two words each: mast and deck shared bucket 7, anchor and ship bucket 5. Sharing a bucket is normal; a lookup compares the key with the few words of its bucket.
  • After reserve(100), libstdc++ listed the words in a new order, while libc++ happened to keep its order. Neither library promised either.
Six words in 13 buckets: bucket 5 holds anchor and ship, bucket 7 mast and deck, bucket 8 sail and bucket 9 rope.libstdc++, 13 bucketsbucket 5anchor: 1 → ship: 3bucket 7mast: 1 → deck: 1bucket 8sail: 2bucket 9rope: 1

The six words of the example in libstdc++'s 13 buckets

Text description of the diagram

The diagram shows where libstdc++ kept the six words of the word-counting example, as the recorded run printed them, with each word's count.

  1. Bucket 5 holds a chain of two nodes: anchor (1), then ship (3).
  2. Bucket 7 holds mast (1), then deck (1).
  3. Bucket 8 holds sail (2), and bucket 9 holds rope (1).
  4. The other 9 of the 13 buckets are empty.

To find a word, the map hashes it, turns the hash into a bucket number from 0 to 12 and compares the word only with the nodes in that bucket's chain. libc++ used 11 buckets for the same words, so its buckets and its order are different.

To print or compare the contents in a way that holds everywhere, copy the elements out and sort them, as the last line did, or keep the data in a std::map if it is needed in order all the time. Sorting n elements costs O(n log n), once, at the moment of output. Tests should compare sorted contents, never the printed order of an unordered container. To check two outputs by hand, sort the lines of each and then compare the two.

What a hash function must do

The standard asks two things of a hash function h: equal keys must get equal hashes, and h(k) may depend only on k while the program runs. It does not promise that the values stay the same from one run of a program to the next, so never store them in files. For different keys, equal hashes should be rare, but they are allowed: the container compares keys with == to tell them apart.

Integers are hashed by doing nothing at all in both libraries: std::hash<int>{}(42) is 42. That is fast and works well because both libraries choose prime bucket counts, as the next sections show. It also means that anyone who controls the keys, such as the users of a web service, can choose keys that all land in the same bucket and turn every lookup into a linear search.

The standard library hashes the fundamental types, pointers, std::string, std::string_view, smart pointers and a few other library types. It has no hash for std::pair or std::tuple, so a pair cannot be the key of an unordered map without help:

pair_key.cpp C++ · pair_key.cpp 
// std::map accepts std::pair keys, because pairs have operator<. std::unordered_map needs std::hash of the key, and
// the standard library has no std::hash for std::pair, so this does not compile.
#include <unordered_map>
#include <utility>

int main() {
    std::unordered_map<std::pair<int, int>, int> steps;
    steps[{2, 3}] = 5;
}
cell_hash.cpp C++ · cell_hash.cpp 
// Two ways to hash your own key type: a specialisation of std::hash, which every unordered container then uses by
// default, or a hash function object passed as a template argument. Both need operator== on the key as well.
#include <cstddef>
#include <cstdint>
#include <functional>
#include <print>
#include <unordered_map>
#include <unordered_set>

struct Cell {
    int row;
    int col;
    bool operator==(const Cell&) const = default;
};

// Way 1: specialise std::hash for your own type. Pack both ints into one 64-bit value, which loses nothing, and mix
// its bits so that neighbouring cells get very different hashes.
template <>
struct std::hash<Cell> {
    std::size_t operator()(const Cell& c) const noexcept {
        std::uint64_t x = (std::uint64_t(std::uint32_t(c.row)) << 32) | std::uint32_t(c.col);
        x ^= x >> 33;  // the 64-bit finaliser of MurmurHash3
        x *= 0xff51afd7ed558ccdULL;
        x ^= x >> 33;
        x *= 0xc4ceb9fe1a85ec53ULL;
        x ^= x >> 33;
        return std::size_t(x);
    }
};

// Way 2: a hash function object of your own, named in the container's type.
struct RowMajorHash {
    std::size_t operator()(const Cell& c) const noexcept { return std::size_t(c.row) * 1'000'003 + std::size_t(c.col); }
};

int main() {
    std::unordered_set<Cell> walls{{0, 1}, {1, 1}, {2, 1}};
    std::println("is (1, 1) a wall? {}  is (1, 2)? {}", walls.contains({1, 1}), walls.contains({1, 2}));

    std::unordered_map<Cell, int, RowMajorHash> steps;
    steps[{2, 3}] = 5;
    steps[{0, 0}] = 0;
    std::println("steps to (2, 3): {}, cells stored: {}", steps.at({2, 3}), steps.size());
}
The first error of each compiler, then the fix Python · pair_key_session.py 
from session import run

# pair_key.cpp does not compile; grep keeps the first error of each compiler, without the file and line in front.
# cell_hash.cpp compiles with both and runs.
run("""
clang++ -std=c++23 -Wall -Wextra pair_key.cpp -o pair_key 2>&1 | grep -m1 -o "error: .*"
g++-16 -std=c++23 -Wall -Wextra pair_key.cpp -o pair_key-gcc 2>&1 | grep -m1 -o "error: .*"
clang++ -std=c++23 -Wall -Wextra cell_hash.cpp -o cell_hash && ./cell_hash
g++-16 -std=c++23 -Wall -Wextra cell_hash.cpp -o cell_hash-gcc && ./cell_hash-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra pair_key.cpp -o pair_key 2>&1 | grep -m1 -o "error: .*"
error: call to implicitly-deleted default constructor of 'std::hash<std::pair<int, int>>'
$ g++-16 -std=c++23 -Wall -Wextra pair_key.cpp -o pair_key-gcc 2>&1 | grep -m1 -o "error: .*"
error: static assertion failed: hash function must be copy constructible
$ clang++ -std=c++23 -Wall -Wextra cell_hash.cpp -o cell_hash && ./cell_hash
is (1, 1) a wall? true  is (1, 2)? false
steps to (2, 3): 5, cells stored: 2
$ g++-16 -std=c++23 -Wall -Wextra cell_hash.cpp -o cell_hash-gcc && ./cell_hash-gcc
is (1, 1) a wall? true  is (1, 2)? false
steps to (2, 3): 5, cells stored: 2

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 pair_key_session.py

Clang said that the default constructor of std::hash<std::pair<int, int>> is deleted, and GCC that the hash function must be copy constructible: two ways of saying that the library has no usable hash for the key. The fix gives the key a type of its own, Cell, with a defaulted operator==, and a hash in one of two ways:

  • A specialisation of std::hash<Cell>, which every unordered container of Cell then uses without being told. The standard allows specialising a library template like std::hash only for types you declared yourself, never for std::pair<int, int> or any other type that belongs to the library.
  • A hash function object, such as RowMajorHash, named as the container’s third template argument. It suits keys from other libraries, or a different hash for one container.

Combining field hashes, measured

A key with several fields needs one hash for all of them, and a careless combination costs more than it looks. This program stores every cell of a 300 × 300 grid and looks each one up once, with two hash functions:

collisions.cpp C++ · collisions.cpp 
// What a weak hash costs: every cell of a 300 by 300 grid stored in an unordered_set, then looked up once, with two
// hash functions. KeyEqual counts how often the set has to compare two keys. A lookup compares the key only with
// elements whose hash is the same, so a hash that gives many cells the same value makes lookups slow.
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <print>
#include <unordered_set>

struct Cell {
    int row;
    int col;
};

static long long comparisons = 0;
struct SameCell {
    bool operator()(const Cell& a, const Cell& b) const {
        ++comparisons;
        return a.row == b.row && a.col == b.col;
    }
};

// Weak: row ^ col is 0 for every cell on the diagonal, and has only 512 different values on this grid.
struct XorHash {
    std::size_t operator()(const Cell& c) const { return std::size_t(c.row ^ c.col); }
};

// Strong: pack both ints into 64 bits (no two cells collide), then mix the bits (MurmurHash3's 64-bit finaliser).
std::size_t mix(const Cell& c) noexcept {
    std::uint64_t x = (std::uint64_t(std::uint32_t(c.row)) << 32) | std::uint32_t(c.col);
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return std::size_t(x);
}
struct MixHash {
    std::size_t operator()(const Cell& c) const { return mix(c); }
};
// The same hash, declared noexcept: libstdc++ then stops storing each element's hash in its node.
struct MixHashNoexcept {
    std::size_t operator()(const Cell& c) const noexcept { return mix(c); }
};

template <class Hash>
void trial(const char* name, int side) {
    std::unordered_set<Cell, Hash, SameCell> cells;
    for (int r = 0; r < side; ++r)
        for (int c = 0; c < side; ++c) cells.insert({r, c});
    std::size_t largest = 0;
    for (std::size_t b = 0; b < cells.bucket_count(); ++b) largest = std::max(largest, cells.bucket_size(b));
    comparisons = 0;
    for (int r = 0; r < side; ++r)
        for (int c = 0; c < side; ++c) (void)cells.contains({r, c});
    std::println("{:<15} largest bucket {:>4} cells; {} lookups made {} key comparisons", name, largest, side * side, comparisons);
}

int main() {
    trial<XorHash>("row ^ col", 300);
    trial<MixHash>("mixed", 300);
    trial<MixHashNoexcept>("mixed, noexcept", 300);
}
Key comparisons for 90,000 lookups, with two hash functions Python · collisions_session.py 
from session import run

# collisions.cpp with -O2, with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra collisions.cpp -o collisions
./collisions
g++-16 -std=c++23 -O2 -Wall -Wextra collisions.cpp -o collisions-gcc
./collisions-gcc
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra collisions.cpp -o collisions
$ ./collisions
row ^ col       largest bucket  300 cells; 90000 lookups made 9951336 key comparisons
mixed           largest bucket    8 cells; 90000 lookups made 90000 key comparisons
mixed, noexcept largest bucket    8 cells; 90000 lookups made 90000 key comparisons
$ g++-16 -std=c++23 -O2 -Wall -Wextra collisions.cpp -o collisions-gcc
$ ./collisions-gcc
row ^ col       largest bucket  300 cells; 90000 lookups made 9951336 key comparisons
mixed           largest bucket    6 cells; 90000 lookups made 90000 key comparisons
mixed, noexcept largest bucket    6 cells; 90000 lookups made 113284 key comparisons

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 collisions_session.py

With row ^ col, the 90,000 lookups made 9,951,336 key comparisons, about 110 per lookup, and the largest bucket held 300 cells. Exclusive or gives 0 for every cell on the diagonal, the same value for (1, 2) and (2, 1), and only 512 different values on the whole grid, so hundreds of cells shared each value. The mixed hash made exactly one comparison per lookup with both libraries. It first packs both 32-bit values into one 64-bit number, which loses nothing, so no two cells get the same input; then it mixes the bits with the finaliser of MurmurHash3, a published hash function, so that neighbouring cells get unrelated hashes. Adding or multiplying the fields, as RowMajorHash does, is fine for small grids but collides as soon as the fields can be large; Boost’s hash_combine is another well-tested way to fold several hashes into one.

For the first two hash functions the counts were identical with both libraries: each library stored every element’s hash in its node and compared hashes before keys, so only elements with an equal hash were compared. libc++ always stores the hash. libstdc++ stores it only for a hash function that may throw or that it treats as slow, such as the string hash, and the third line shows the difference: declared noexcept, the same mixed hash made libstdc++ drop the stored hash, which saves 8 bytes per node, and compare the key with other elements of its bucket, 113,284 comparisons instead of 90,000. That is why a node of an int took 16 bytes in libstdc++ and 24 in libc++ in the module’s first lesson.

Buckets, load factor and rehashing

The load factor is the number of elements divided by the number of buckets. When an insertion would push it above the maximum load factor, 1.0 unless you change it, the table rehashes: it allocates more buckets and moves every node into its new bucket.

rehash.cpp C++ · rehash.cpp 
// How an unordered_map grows: the bucket counts it goes through while 100,000 keys are inserted, with and without
// reserve, what a rehash leaves valid, and what max_load_factor really sets.
#include <cstddef>
#include <print>
#include <unordered_map>
#include <vector>

int main() {
    const int n = 100'000;
    std::unordered_map<int, int> grown;
    grown[-1] = 0;
    const int* first_value = &grown.at(-1);  // a pointer to an element, kept across every rehash below
    std::vector<std::size_t> counts{grown.bucket_count()};
    for (int i = 0; i < n; ++i) {
        grown[i * 7] = i;
        if (grown.bucket_count() != counts.back()) counts.push_back(grown.bucket_count());
    }
    std::println("without reserve: {} rehashes, through {} buckets", counts.size() - 1, counts);
    std::println("the pointer taken before them still reads the same element: {}", first_value == &grown.at(-1));

    std::unordered_map<int, int> reserved;
    reserved.reserve(n + 1);  // buckets for n + 1 elements at the maximum load factor, allocated once
    std::size_t start = reserved.bucket_count();
    for (int i = -1; i < n; ++i) reserved[i * 7] = i;
    std::println("with reserve({}): {} buckets, unchanged by the inserts: {}", n + 1, start, reserved.bucket_count() == start);

    std::println("load factor {:.2f}, maximum {:.2f}", grown.load_factor(), grown.max_load_factor());
    grown.max_load_factor(0.5f);  // only a hint: "may change the container's maximum load factor"
    std::println("after max_load_factor(0.5): maximum {:.2f}", grown.max_load_factor());
    grown.reserve(grown.size());  // rehash now if the new maximum needs more buckets
    std::println("after reserve(size()): {} buckets, load factor {:.2f}", grown.bucket_count(), grown.load_factor());
}
Growing to 100,000 keys with libc++ and with libstdc++ Python · rehash_session.py 
from session import run

# rehash.cpp with libc++ (Apple clang), then with libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -O2 -Wall -Wextra rehash.cpp -o rehash
./rehash
g++-16 -std=c++23 -O2 -Wall -Wextra rehash.cpp -o rehash-gcc
./rehash-gcc
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra rehash.cpp -o rehash
$ ./rehash
without reserve: 15 rehashes, through [2, 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877] buckets
the pointer taken before them still reads the same element: true
with reserve(100001): 100003 buckets, unchanged by the inserts: true
load factor 0.97, maximum 1.00
after max_load_factor(0.5): maximum 0.97
after reserve(size()): 102877 buckets, load factor 0.97
$ g++-16 -std=c++23 -O2 -Wall -Wextra rehash.cpp -o rehash-gcc
$ ./rehash-gcc
without reserve: 13 rehashes, through [13, 29, 59, 127, 257, 541, 1109, 2357, 5087, 10273, 20753, 42043, 85229, 172933] buckets
the pointer taken before them still reads the same element: true
with reserve(100001): 107897 buckets, unchanged by the inserts: true
load factor 0.58, maximum 1.00
after max_load_factor(0.5): maximum 0.50
after reserve(size()): 202409 buckets, load factor 0.49

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 rehash_session.py

  • Without reserve, libc++ rehashed 15 times and libstdc++ 13 times on the way to 100,000 keys, each time to a prime number of buckets about twice as large. Every rehash visits every node and allocates a new array of buckets.
  • With reserve(100001) first, both libraries allocated enough buckets once, 100,003 and 107,897, and never rehashed. reserve(n) is defined as rehash(ceil(n / max_load_factor())): room for n elements at the current maximum load factor.
  • The pointer taken before the first rehash still pointed to the same element after all of them. Rehashing relinks nodes; the elements themselves stay where they are.
  • max_load_factor(0.5) is only a hint in the standard’s words: it “may change” the maximum. libstdc++ took 0.5 and rehashed to 202,409 buckets at the next reserve; libc++ never sets the maximum below the current load factor, so it kept 0.97 and did nothing. To apply a new maximum, set it before the table fills up, then call reserve.

What a rehash invalidates

A rehash leaves pointers and references to the elements valid, but it invalidates every iterator and changes the order of the elements. An insertion that does not rehash invalidates nothing; erasing invalidates only what referred to the erased element. The most common way to break the rule is to insert into the container a loop is walking over:

insert_while_iterating.cpp C++ · insert_while_iterating.cpp 
// The bug that the rehash rule warns about: inserting into an unordered_map while a loop walks over it. When an
// insertion rehashes, the loop's iterator is invalidated, so this loop has undefined behaviour; the program records
// what each library happened to do, with a limit on the steps in case the loop never ends.
#include <map>
#include <print>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<int, int> m;
    for (int k = 0; k < 8; ++k) m[k] = 0;

    std::map<int, int> visits;  // how many times the loop reached each of the eight starting keys
    int steps = 0;
    for (auto it = m.begin(); it != m.end() && steps < 1000; ++it, ++steps) {
        if (it->first < 8) {
            ++visits[it->first];
            m[it->first + 100] = 1;  // wrong: may rehash while it is in use
        }
    }
    std::vector<int> twice, never;
    for (int k = 0; k < 8; ++k) {
        if (visits[k] > 1) twice.push_back(k);
        if (visits[k] == 0) never.push_back(k);
    }
    std::println("{} steps; starting keys visited twice: {}, never: {}; keys at the end: {} (16 expected)",
                 steps, twice, never, m.size());

    // The fix: collect what to insert, and insert it after the loop.
    std::unordered_map<int, int> fixed;
    for (int k = 0; k < 8; ++k) fixed[k] = 0;
    std::vector<int> to_add;
    for (const auto& [key, value] : fixed) to_add.push_back(key + 100);
    for (int key : to_add) fixed[key] = 1;
    std::println("collected, then inserted: {} keys", fixed.size());
}
The same loop with libc++ and with libstdc++ Python · insert_while_iterating_session.py 
from session import run

# insert_while_iterating.cpp with libc++ (Apple clang), then with libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -Wall -Wextra insert_while_iterating.cpp -o insert_while_iterating
./insert_while_iterating
g++-16 -std=c++23 -Wall -Wextra insert_while_iterating.cpp -o insert_while_iterating-gcc
./insert_while_iterating-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra insert_while_iterating.cpp -o insert_while_iterating
$ ./insert_while_iterating
8 steps; starting keys visited twice: [], never: []; keys at the end: 16 (16 expected)
collected, then inserted: 16 keys
$ g++-16 -std=c++23 -Wall -Wextra insert_while_iterating.cpp -o insert_while_iterating-gcc
$ ./insert_while_iterating-gcc
16 steps; starting keys visited twice: [3, 4, 5, 6, 7], never: [0, 1]; keys at the end: 14 (16 expected)
collected, then inserted: 16 keys

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 insert_while_iterating_session.py

The loop was meant to add k + 100 for each of the eight starting keys. Eight more keys double the size of a table that has fewer than 16 buckets, which pushes it past its maximum load factor, so in both libraries it rehashed while the loop was running. With libc++ the loop happened to visit each starting key once and end with 16 keys. With libstdc++ it visited five starting keys twice and two never, and the map ended with 14 keys. Neither result is something to rely on: the program has undefined behaviour, and in a busier map the loop could visit the new keys too, or never end. The fix is to collect the new keys during the loop and insert them afterwards, as the second half of the program does. Reserving enough buckets first also prevents the rehash, but whether the loop then visits the new elements is still unspecified.

Lookups by std::string_view

As with std::map, a std::unordered_map<std::string, int> can only look up a std::string, so a key that arrives as a std::string_view has to become a temporary std::string, which allocates when the text is long. Since C++20, the unordered containers accept other key types when both the hash and the equality test declare a member type named is_transparent:

transparent_hash.cpp C++ · transparent_hash.cpp 
// Heterogeneous lookup in an unordered_map (C++20): when both the hash and the key comparison declare
// is_transparent, find accepts a std::string_view and does not build a std::string. The global operator new below
// counts every allocation the program makes.
#include <cstddef>
#include <cstdlib>
#include <functional>
#include <new>
#include <print>
#include <string>
#include <string_view>
#include <unordered_map>

static std::size_t allocations = 0;
void* operator new(std::size_t n) {
    ++allocations;
    if (void* p = std::malloc(n)) return p;
    throw std::bad_alloc{};
}
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }

struct TextHash {
    using is_transparent = void;  // "I can hash anything that converts to std::string_view"
    std::size_t operator()(std::string_view text) const noexcept { return std::hash<std::string_view>{}(text); }
};

int main() {
    const std::string_view key = "customer-000123-billing-address";  // 31 characters: too long to fit in place
    std::unordered_map<std::string, int> plain{{std::string(key), 1}};
    std::unordered_map<std::string, int, TextHash, std::equal_to<>> transparent{{std::string(key), 1}};

    std::size_t before = allocations;
    int found = 0;
    for (int i = 0; i < 1000; ++i) found += plain.contains(std::string(key));  // must build a std::string
    std::size_t plain_allocations = allocations - before;
    before = allocations;
    for (int i = 0; i < 1000; ++i) found += transparent.contains(key);  // looks the view up directly
    std::size_t transparent_allocations = allocations - before;
    std::println("found {} of 2000; allocations: {} with the default hash, {} with TextHash and std::equal_to<>",
                 found, plain_allocations, transparent_allocations);
}
Allocations for 1,000 lookups of a 31-character key Python · transparent_hash_session.py 
from session import run

# transparent_hash.cpp with -O2, with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra transparent_hash.cpp -o transparent_hash
./transparent_hash
g++-16 -std=c++23 -O2 -Wall -Wextra transparent_hash.cpp -o transparent_hash-gcc
./transparent_hash-gcc
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra transparent_hash.cpp -o transparent_hash
$ ./transparent_hash
found 2000 of 2000; allocations: 1000 with the default hash, 0 with TextHash and std::equal_to<>
$ g++-16 -std=c++23 -O2 -Wall -Wextra transparent_hash.cpp -o transparent_hash-gcc
$ ./transparent_hash-gcc
found 2000 of 2000; allocations: 1000 with the default hash, 0 with TextHash and std::equal_to<>

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 transparent_hash_session.py

TextHash hashes anything that converts to a std::string_view, and std::equal_to<> compares a std::string with a std::string_view directly. A thousand lookups then made no allocation, against a thousand with the default hash. This is correct because the standard requires std::hash<std::string> and std::hash<std::string_view> to give the same value for the same text: equal keys must hash alike, whatever their type.

Your turn: two_sum and group_anagrams

Write the two functions of hashing_tasks.h, each in one pass over its input:

  1. two_sum(values, target) returns the positions i < j of two numbers that add up to target, choosing the pair with the smallest j and then the smallest i, or std::nullopt.
  2. group_anagrams(words) groups words with the same letters, such as "stop", "pots" and "tops". The words in a group keep their input order, and the groups are ordered by where their first word appears.

Both answers must be the same with every standard library, so neither may depend on the order of an unordered container.

The starter code and its sample tests

C header · hashing_tasks.h 

// Starter code for "Your turn": two problems that a hash map solves in one pass. Both must give the same answer with
// every standard library, so neither may depend on the order in which an unordered container lists its elements.
#pragma once
#include <optional>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

// The positions i < j of two numbers in values that add up to target, or std::nullopt. When several pairs exist,
// return the one with the smallest j, and for that j the smallest i.
inline std::optional<std::pair<int, int>> two_sum(const std::vector<int>& values, int target) {
    // TODO: walk j from left to right, and remember in an unordered_map where each value first appeared
    (void)values;
    (void)target;
    return std::nullopt;
}

// The words grouped by their letters: "listen", "silent" and "enlist" are anagrams. The words of a group keep their
// order in the input, and the groups are ordered by where their first word appears.
inline std::vector<std::vector<std::string>> group_anagrams(const std::vector<std::string>& words) {
    // TODO: the sorted letters of a word are the same for all its anagrams, so they make a good key
    (void)words;
    return {};
}

C++ · hashing_tasks_tests.cpp 

// Sample tests for hashing_tasks.h. Build: clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra hashing_tasks_tests.cpp -o hashing_tasks_tests
#include <optional>
#include <print>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "hashing_tasks.h"

int checks = 0;
int failures = 0;

void check(bool ok, const char* what) {
    ++checks;
    if (!ok) {
        ++failures;
        std::println("FAIL {}", what);
    }
}

using Pair = std::optional<std::pair<int, int>>;

// The slow way: every pair, in the order the rule asks for.
Pair slow_two_sum(const std::vector<int>& v, int target) {
    for (int j = 0; j < int(v.size()); ++j)
        for (int i = 0; i < j; ++i)
            if (v[i] + v[j] == target) return std::pair{i, j};
    return std::nullopt;
}

int main() {
    check(two_sum({2, 7, 11, 15}, 9) == Pair{{0, 1}}, "2 + 7 = 9 at positions 0 and 1");
    check(two_sum({3, 3}, 6) == Pair{{0, 1}}, "the same value twice");
    check(two_sum({1, 2, 3}, 7) == std::nullopt, "no pair adds up to 7");
    check(two_sum({5, 1, 5, 4}, 9) == Pair{{0, 3}}, "the smallest j, then the smallest i");
    check(two_sum({-4, 10, 7, -3}, 3) == Pair{{0, 2}}, "negative numbers");

    std::mt19937 random(9);
    bool same = true;
    for (int round = 0; round < 50 && same; ++round) {
        std::vector<int> v;
        for (int k = 0; k < 400; ++k) v.push_back(int(random() % 2'001) - 1'000);
        int target = int(random() % 3'001) - 1'500;
        same = two_sum(v, target) == slow_two_sum(v, target);
    }
    check(same, "50 random lists give the same pair as the slow way");

    check(group_anagrams({}).empty(), "no words, no groups");
    using Groups = std::vector<std::vector<std::string>>;
    check(group_anagrams({"listen", "google", "silent", "cat", "enlist", "act", "dog", "gogole", "tac"}) ==
              Groups{{"listen", "silent", "enlist"}, {"google", "gogole"}, {"cat", "act", "tac"}, {"dog"}},
          "four groups, in the order of their first words");
    check(group_anagrams({"stop", "pots", "tops", "spot"}) == Groups{{"stop", "pots", "tops", "spot"}}, "one group of four");

    std::println("{} of {} checks passed", checks - failures, checks);
    return failures == 0 ? 0 : 1;
}
The sample tests against the starter code Python · hashing_tasks_session.py 
from session import run

# The sample tests run against the starter code, before any TODO is done, with the sanitizers switched on.
run("""
clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra hashing_tasks_tests.cpp -o hashing_tasks_tests && ./hashing_tasks_tests
g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra hashing_tasks_tests.cpp -o hashing_tasks_tests-gcc && ./hashing_tasks_tests-gcc
""")

Output

$ clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra hashing_tasks_tests.cpp -o hashing_tasks_tests && ./hashing_tasks_tests
FAIL 2 + 7 = 9 at positions 0 and 1
FAIL the same value twice
FAIL the smallest j, then the smallest i
FAIL negative numbers
FAIL 50 random lists give the same pair as the slow way
FAIL four groups, in the order of their first words
FAIL one group of four
2 of 9 checks passed
[exit status 1]
$ g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra hashing_tasks_tests.cpp -o hashing_tasks_tests-gcc && ./hashing_tasks_tests-gcc
FAIL 2 + 7 = 9 at positions 0 and 1
FAIL the same value twice
FAIL the smallest j, then the smallest i
FAIL negative numbers
FAIL 50 random lists give the same pair as the slow way
FAIL four groups, in the order of their first words
FAIL one group of four
2 of 9 checks passed
[exit status 1]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 hashing_tasks_session.py

You are done when both compilers print 9 of 9 checks passed. Hints: for two_sum, walk j from left to right and look up target - values[j] among the values already seen, remembering only where each value first appeared (try_emplace leaves an existing entry alone). For group_anagrams, a copy of the word with its letters sorted is the same for all anagrams; map it to the position of its group in a std::vector of groups. A solution that builds the groups by walking the unordered map passes on neither compiler, because the map’s order is not the input’s.

Check yourself

6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 6 What does the C++ standard promise about the order in which a std::unordered_map lists its elements?

    Choose one answer.

    Show the answer

    Answer: Nothing; it differs between libraries and can change after any insertion that rehashes

    The order follows the buckets and the chains inside them, which depend on the hash function, the bucket count and the library. The same six words came out in different orders with libc++ and libstdc++, and libstdc++'s order changed after reserve(100).

  2. Question 2 of 6 An insertion into a std::unordered_map made it rehash. Which of these, taken before the insertion, can you still use?

    Choose every answer that is right.

    Show the answer

    Answer:

    • A reference to an element
    • A pointer to an element

    Rehashing moves nodes between buckets, not elements in memory, so pointers and references stay valid. It invalidates every iterator and changes the order of the elements.

  3. Question 3 of 6 Why does std::unordered_map<std::pair<int, int>, int> fail to compile, while std::map<std::pair<int, int>, int> works?

    Choose one answer.

    Show the answer

    Answer: The standard library has no std::hash for std::pair, and an unordered map needs one

    std::map needs only operator<, which pairs have. An unordered map needs a hash of the key and ==; give it a hash function object, or use a struct of your own with a std::hash specialisation.

  4. Question 4 of 6 In the collision example, how many key comparisons did the 90,000 lookups make with the mixed hash?

    Type a number.

    Show the answer

    Answer: 90000 comparisons

    One per lookup: with a hash that gives different cells different values, the only element with the same hash is the one being looked for. With row ^ col the same lookups made 9,951,336 comparisons.

  5. Question 5 of 6 A program will insert about a million keys into an empty std::unordered_map. What does calling reserve(1'000'000) first guarantee?

    Choose one answer.

    Show the answer

    Answer: Enough buckets that the million insertions never rehash, at the current maximum load factor

    reserve(n) is defined as rehash(ceil(n / max_load_factor())): it makes enough buckets for n elements, so insertions up to that size neither rehash nor invalidate iterators. Each node is still allocated on its own when its element is inserted.

  6. Question 6 of 6 What does a std::unordered_map<std::string, int, Hash, Equal> need so that find accepts a std::string_view without building a std::string?

    Choose one answer.

    Show the answer

    Answer: Both Hash and Equal must declare a member type named is_transparent

    Since C++20 the unordered containers offer heterogeneous lookup only when both the hash and the equality test opt in, as TextHash and std::equal_to<> do in the lesson's example. std::less<> is the ordered containers' opt-in.

Interview questions

Fresher · Why must code never rely on the iteration order of a std::unordered_map?

The standard leaves the order unspecified. It follows the buckets and the chains inside them, so it depends on the hash function, the number of buckets and how the library turns a hash into a bucket, and all three differ between standard libraries: the same six words came out in different orders with libc++ and libstdc++. The order also changes whenever the table rehashes, which can happen on any insertion that pushes the load factor past its maximum, or after reserve or rehash. And the standard lets hash values differ between runs of the same program. Code that prints results, writes files or compares test output in iteration order therefore breaks on another compiler or after a small change. Sort the elements before output, or use std::map when the order matters.

Key takeaways

  • Unordered containers find, insert and erase in O(1) on average and O(n) when many keys share a bucket.
  • Their iteration order is unspecified: the same words came out in different orders with libc++ (11 buckets) and libstdc++ (13), and libstdc++’s order changed after reserve. Sort before you print or compare.
  • std::pair has no std::hash. Give your key type operator== and either a std::hash specialisation or a hash function object; combine fields by packing and mixing them, never with ^, which made 110 times as many key comparisons on a grid.
  • reserve(n) allocates the buckets once; without it, 100,000 inserts rehashed 13 to 15 times. max_load_factor is only a hint, and libc++ never lowers it below the current load.
  • A rehash invalidates every iterator but no pointer or reference. Never insert into an unordered container while a loop walks over it; collect the keys and insert them afterwards.
  • Heterogeneous lookup needs is_transparent on both the hash and the equality test.

References

Related tools

Text Sorter Sort lines alphabetically, naturally, by number or length — or shuffle them. Text Diff See what changed between two versions — by line, word or character.

Report a problem with this lesson