Hash maps and sets in practice

std::unordered_map and std::unordered_set turn "have I seen this?" and "what goes with this key?" into O(1) average-time questions. Most "make it faster than O(n²)" problems are solved by one of four patterns built on them. This skill is about using them well — and about their traps. (Building one yourself comes in Level 4.)

1. What you get, and what it costs

A hash container stores elements in buckets. To find a key it computes hash(key), reduces it to a bucket index, and compares the key with the few elements in that bucket using ==.

The worst case happens when many keys land in the same bucket — a bad hash function, or input chosen to collide. Then a bucket is a long chain and every lookup walks it. "O(1)" is a statement about your hash on your data.

When the average is good, it's very good: no comparisons beyond the bucket, no log factor. When you need order — iterate sorted, find the smallest key ≥ x, range queries — use std::map (a balanced tree, O(log n) guaranteed) or a sorted std::vector / C++23 std::flat_map, which are often fastest of all for read-mostly data.

2. The API, and the trap in operator[]

#include <print>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock{{"apples", 3}};

    // Lookups that never insert:
    std::println("{}", stock.contains("pears"));      // false (C++20)
    if (auto it = stock.find("apples"); it != stock.end())
        std::println("apples: {}", it->second);
    std::println("{}", stock.at("apples"));           // throws std::out_of_range if missing

    // operator[] INSERTS a default value when the key is missing:
    int pears = stock["pears"];                       // adds {"pears", 0}!
    std::println("pears={} size={}", pears, stock.size());  // size is now 2
}

operator[] returns a reference to the mapped value, creating it if necessary. That's perfect for counting — ++count[word] starts missing words at 0 — and a bug everywhere else: a "read" that silently grows the map, and something you can't call on a const map at all.

Writing has three flavours. Pick by what should happen when the key exists:

insert and try_emplace return {iterator, bool}; the bool tells you whether the key was new. That makes "seen before?" a single hash lookup:

if (!seen.insert(x).second) { /* x was already in the set */ }

3. Four patterns

Seen-set: "has this value appeared before?"

#include <optional>
#include <print>
#include <unordered_set>
#include <vector>

std::optional<int> first_repeated(const std::vector<int>& v) {
    std::unordered_set<int> seen;
    for (int x : v)
        if (!seen.insert(x).second) return x;
    return std::nullopt;
}

int main() {
    std::println("{}", first_repeated({3, 1, 4, 1, 5, 3}).value_or(-1));  // 1
}

Value → index: "where did I see the value I need?"

The classic "two numbers adding to a target": for each element, the partner you need is target - v[j]. Look it up among the elements before j, then record v[j]. Looking up before inserting means an element never pairs with itself.

Frequency map: "how many of each?"

#include <print>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<std::string> words{"to", "be", "or", "not", "to", "be"};
    std::unordered_map<std::string, int> count;
    for (const auto& w : words) ++count[w];   // the good use of operator[]
    std::println("to={} be={} not={}", count["to"], count["be"], count["not"]);
}

Grouping by a canonical key

Map each element to a key that's equal exactly for elements in the same group — for anagrams, the word's letters sorted — and map the key to the group.

4. Worked example: value → index, carefully

Find indices i < j with v[i] + v[j] == target, preferring the smallest j, then the smallest i:

#include <cstddef>
#include <optional>
#include <print>
#include <unordered_map>
#include <utility>
#include <vector>

std::optional<std::pair<std::size_t, std::size_t>> pair_with_sum(const std::vector<int>& v, int target) {
    std::unordered_map<long long, std::size_t> first_index;   // value -> earliest index
    first_index.reserve(v.size());                            // no rehashes while we scan
    for (std::size_t j = 0; j < v.size(); ++j) {
        long long need = static_cast<long long>(target) - v[j];   // 64-bit: can't overflow
        if (auto it = first_index.find(need); it != first_index.end())
            return std::pair{it->second, j};                  // smallest j: first hit wins
        first_index.try_emplace(v[j], j);                     // keep the EARLIEST index
    }
    return std::nullopt;
}

int main() {
    if (auto p = pair_with_sum({5, 5, 1}, 6)) std::println("({}, {})", p->first, p->second);  // (0, 2)
}

Each detail is a bug avoided:

• Look up, then insert — otherwise {3} with target 6 pairs 3 with itself.
• try_emplace, not first_index[v[j]] = j — the latter overwrites, so {5, 5, 1} would give (1, 2).
• long long need — INT_MIN - 1 in int is signed overflow, undefined behaviour.
• reserve — avoids repeated rehashing as the map grows (a constant-factor win).

Faded example — your turn

Count how many pairs i < j have v[i] + v[j] == target (not just the first). Fill in the two lines. What should the map store now: an index, or something else?

std::unordered_map<long long, std::size_t> seen_count;
std::size_t pairs = 0;
for (int x : v) {
    /* ??? */   // add the number of earlier elements equal to target - x
    /* ??? */   // record x
}

5. Your own types as keys

A key type needs a hash and equality that agree: equal keys must have equal hashes. std::hash exists for built-in types and the standard library's own (strings, smart pointers…), not for your structs:

#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point&) const = default;
};

std::unordered_set<Point> s;   // error: no std::hash<Point>

Supply a hash type. The quality of the hash is your complexity: x ^ y looks fine but maps every (i, i) to 0 and is symmetric, so (1, 2) and (2, 1) collide. Packing both 32-bit coordinates into one 64-bit value is collision-free:

#include <cstddef>
#include <cstdint>
#include <functional>
#include <print>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point&) const = default;
};

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        std::uint64_t key = (std::uint64_t{static_cast<std::uint32_t>(p.x)} << 32) | static_cast<std::uint32_t>(p.y);
        return std::hash<std::uint64_t>{}(key);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts{{1, 2}, {2, 1}, {1, 2}};
    std::println("{}", pts.size());   // 2
}

For keys with several fields that don't pack, combine hashes with a mixing step (e.g. h ^= hash(field) + 0x9e3779b97f4a7c15 + (h << 6) + (h >> 2)) rather than plain ^ or +.

Heterogeneous lookup

With std::unordered_map<std::string, V>, m.find(sv) for a string_view normally has to build a temporary std::string. Since C++20 you can opt in to lookup by any comparable type by making the hash and equality transparent:

#include <functional>
#include <print>
#include <string>
#include <string_view>
#include <unordered_map>

struct StringHash {
    using is_transparent = void;   // enables find(string_view) without a temporary string
    std::size_t operator()(std::string_view s) const noexcept { return std::hash<std::string_view>{}(s); }
};

int main() {
    std::unordered_map<std::string, int, StringHash, std::equal_to<>> ids{{"ada", 1}, {"bob", 2}};
    std::string_view who = "bob";
    if (auto it = ids.find(who); it != ids.end()) std::println("{}", it->second);
}

6. Iteration order and invalidation

• Order is unspecified and can change after any insert. Never let output depend on it — sort first if order matters (e.g. "top k, ties by smaller value").
• An insert may rehash (grow the bucket array). That invalidates all iterators, but references and pointers to elements stay valid — nodes don't move. reserve(n) pre-sizes the table so n inserts don't rehash.
• erase(it) invalidates it. Use it = m.erase(it) in a loop, or C++20's std::erase_if(m, pred).

Summary

• Hash containers: O(1) average for find/insert/erase, O(n) worst case, no order.
• operator[] inserts; use find/contains/at to look up, ++m[k] to count.
• try_emplace/insert keep existing values; insert_or_assign/m[k] = v overwrite.
• Patterns: seen-set, value → index, frequency map, group by canonical key.
• Custom keys need a hash consistent with == — and a good one, or you're O(n²).
• Need order or ranges? std::map, sorted vector, std::flat_map.