std::map vs std::unordered_map: The Iteration Contract Nobody Reads

90 Day C++ Challenge: Zero to Production -- Day 25

I broke a nightly report by making it faster. The data stayed correct; the rows just came out in a different order than the day before, and a golden-file test caught it. The single change responsible was swapping a std::map for a std::unordered_map to speed up a hot lookup. This post is about the contract I forgot to read.

The two containers are not interchangeable

std::map and std::unordered_map have nearly the same interface, so it is tempting to treat them as drop-in replacements. They are not. They are built on different data structures and they make different promises.

• std::map is a balanced binary search tree (a red-black tree). Keys are stored in sorted order. find, insert, erase are O(log n). Iteration is always in ascending key order, and that is guaranteed by the standard.
• std::unordered_map is a hash table. find and insert are O(1) on average (O(n) worst case under collisions). Iteration is in bucket order with no guarantee -- and it can change as the table grows.

If your code reads keys back out in iteration order and anything compares that order across runs, the difference is not academic.

Watching the order diverge

#include <map>
#include <unordered_map>
#include <string>
#include <iostream>

template <typename Map>
void print_keys(const char* label, const Map& m) {
    std::cout << label;
    for (const auto& [city, population] : m)
        std::cout << ' ' << city << '(' << population << ')';
    std::cout << '\n';
}

int main() {
    const std::pair<std::string, int> data[] = {
        {"Tokyo", 37}, {"Delhi", 32}, {"Cairo", 22}, {"Berlin", 4}};

    std::map<std::string, int>           tree(std::begin(data), std::end(data));
    std::unordered_map<std::string, int> hash(std::begin(data), std::end(data));

    print_keys("map (sorted):       ", tree);   // Berlin Cairo Delhi Tokyo
    print_keys("unordered (buckets):", hash);    // some permutation, do not rely on it
}

The map line prints Berlin Cairo Delhi Tokyo every time. The unordered_map line prints a permutation you must not depend on.

Load factor and rehashing

The reason unordered_map refuses to promise an order is that it physically reorganizes itself as it fills. It tracks a load factor equal to size() / bucket_count(). Once an insert pushes that past max_load_factor() (default 1.0), the table rehashes: it allocates more buckets and redistributes every element.

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> m;
    std::cout << "start buckets=" << m.bucket_count() << '\n';

    for (int i = 0; i < 50; ++i) {
        std::size_t before = m.bucket_count();
        m.emplace(i, "node");
        if (m.bucket_count() != before)
            std::cout << "rehash at size " << m.size()
                      << ": buckets " << before << " -> " << m.bucket_count()
                      << ", load=" << m.load_factor() << '\n';
    }
}

Each printed line is a rehash. A rehash invalidates every iterator into the table; pointers and references to elements survive because the nodes are not relocated, only the bucket array is rebuilt. If you cache an iterator and keep inserting, it dangles after the next rehash. Knowing the count, m.reserve(n) pre-sizes the buckets and skips rehashing entirely.

The operator[] insert-on-read trap

This is the bug that bites everyone once. operator[] is not a lookup. It returns a reference to the value at the key, default-constructing the entry if the key is absent. Reading a missing key with [] silently inserts it.

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> inventory{{"bolts", 500}};

    // Looks like a read. Actually inserts "screws" -> 0.
    if (inventory["screws"] == 0)
        std::cout << "out of screws (but I just created the entry)\n";

    std::cout << "size after the 'read': " << inventory.size() << '\n';  // 2

    // Honest lookups that never mutate:
    std::cout << "have bolts? "  << inventory.contains("bolts")  << '\n'; // 1
    std::cout << "have nails? "  << inventory.contains("nails")  << '\n'; // 0, no insert

    try {
        int n = inventory.at("nails");   // throws std::out_of_range
        std::cout << n << '\n';
    } catch (const std::out_of_range&) {
        std::cout << "at() threw instead of inserting -- size still "
                  << inventory.size() << '\n';
    }
}

For pure reads use find, at, or contains. Keep operator[] for genuine insert-or-update, where the counting idiom ++freq[key] relies on the default-to-zero behaviour deliberately.

set, unordered_set, and ordered ranges

std::set and std::unordered_set are the value-free versions of the same two structures: set is the sorted tree (ordered iteration, O(log n)), unordered_set is the hash table (unordered, O(1) average). Reach for them when you need uniqueness and membership tests without a mapped value.

The tree-backed containers offer one capability a hash table cannot: ordered range queries. lower_bound(k) returns the first key >= k, upper_bound(k) the first key > k, so you can iterate [lo, hi) in sorted order. There is no equivalent on an unordered container, because it has no order to slice.

How I actually fixed it

I kept the unordered_map for the speed -- that win was real -- and changed the downstream report to pull its keys and std::sort them before emitting rows. The ordering requirement now lives in the code that needs it, stated explicitly, instead of being borrowed from a container that never promised it.

The rule I am taking from day 25: pick an associative container by the contract you need, not the big-O you want. Read the iteration-order guarantee as carefully as you read the complexity.