Unordered Containers in C++: unordered_set and unordered_map with Worked Examples

std::map and std::set feel predictable because they iterate in sorted order, while the unordered family gives up that order for average constant-time exact-key operations. The beginner's real difficulty is knowing which type to choose and which apparently harmless operations change the container. Two decisions separate the four types: whether a key carries a mapped value, and whether equal keys may repeat. The operations that change a container without looking like it are operator[], which inserts a default value for a missing key, and any insertion that triggers a rehash, which invalidates existing iterators.

C++ unordered containers: choose among the four types

Choose along two axes: whether each key has a mapped value, and whether equal keys may repeat. All four types entered the standard library in C++11 through <unordered_set> or <unordered_map>, and they fit within the wider Coding & DSA learning path.

For exact miniature cases, unordered_set<int>{4, 7, 4, 9} has size 3 and count(4) == 1. Its multiset counterpart has size 4 and count(4) == 2. An unordered_map<string, int>{{"Ada", 91}, {"Linus", 88}} has size 2 and at("Ada") == 91, while unordered_multimap<string, int>{{"C++", 10}, {"C++", 12}} has size 2 and count("C++") == 2. None of these facts depends on iteration order.

How hashing, buckets, collisions, and load factor work

A lookup has three stages. The hasher converts a key to a hash value, the container maps that value to a bucket, and the equality predicate identifies the key among the bucket's candidates. Equal keys must have equal hashes, but unequal keys may collide. See Hashing and Collision Resolution when you want the collision methods unpacked.

Consider a conceptual table with five buckets and h(k) = k mod 5. Inserting 12, 7, 22, 19, 4 gives remainders 2, 2, 2, 4, 4. Buckets 0, 1, and 3 are empty, bucket 2 shows 12 -> 7 -> 22, and bucket 4 shows 19 -> 4. Finding 22 selects bucket 2 and takes three equality checks in this displayed chain. Erasing 7 leaves 12 -> 22.

This chain is a teaching model, not a layout or order promised by C++. A container's load_factor() is size() / bucket_count(). With size 12 and 17 buckets, it is 12 / 17 = 0.705882..., or about 0.706. find, insert, and erase are O(1) on average and O(n) in the worst case. reserve(1000) prepares for about 1,000 elements, but the resulting bucket count remains implementation-dependent.

unordered_set worked example: membership and duplicate insertion

This complete C++17 program prints only order-independent facts:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> ids{42, 17, 42, 8};
    auto [first, inserted_first] = ids.insert(23);
    auto [second, inserted_second] = ids.insert(23);

    std::cout << std::boolalpha << ids.size() << '\n';
    std::cout << inserted_first << ' ' << inserted_second << '\n';
    std::cout << (ids.find(17) != ids.end()) << '\n';
    ids.erase(17);
    std::cout << (ids.find(17) == ids.end()) << '\n';
}

4
true false
true
true

The repeated 42 makes the initial size 3. The first insertion of 23 succeeds, the second is rejected, 17 exists before erasure, and is absent afterwards. C++20 adds contains, but find keeps this example C++17-compatible. Checkpoint: inserting 5, 3, 5, 2, 3, 5 produces size 3, but iteration cannot portably promise the order 2, 3, 5.

unordered_map worked example: a word-frequency table

operator[] is useful when insertion is intentional. Here it creates missing counters at zero before incrementing them:

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

int main() {
    std::unordered_map<std::string, int> frequency;
    for (const std::string& word : {"red", "blue", "red", "green", "blue", "red"})
        ++frequency[word];

    std::cout << "red=" << frequency.at("red")
              << " blue=" << frequency.at("blue")
              << " green=" << frequency.at("green") << '\n';
    std::cout << std::boolalpha
              << "missing=" << (frequency.find("yellow") == frequency.end())
              << " size=" << frequency.size() << '\n';
    int yellow = frequency["yellow"];
    std::cout << "yellow=" << yellow << " size=" << frequency.size() << '\n';
}

The output is red=3 blue=2 green=1, then missing=true size=3, then yellow=0 size=4. find tested without mutation, while frequency["yellow"] inserted a default int value. Use operator[] for intended insertion, find for a portable C++17 existence check, and at when absence is an error because it throws std::out_of_range. Fixed-key printing makes no claim about first-seen or alphabetical traversal.

Custom keys in unordered containers: hash and equality together

A custom key needs equality and a compatible hash:

#include <functional>
#include <iostream>
#include <unordered_set>

struct Point {
    int x;
    int y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> points{{2, 3}, {4, 1}, {2, 3}};
    std::cout << std::boolalpha << points.size() << '\n'
              << (points.find(Point{2, 3}) != points.end()) << '\n';
}

It prints size 2 and then true. The repeated {2, 3} is equal and rejected, while {4, 1} is distinct. The invariant is precise: whenever a == b, both must produce the same hash. Unequal points may collide and equality resolves them. A disagreement for equal points breaks correct lookup. Numeric std::hash results and bucket positions are not portable output contracts.

C++ unordered container complexity and common errors

An ID frequency table for {101, 205, 101, 450} suits an unordered map. Printing records by ascending ID suits std::map, or a copied sequence followed by sorting.

Four common traps have direct fixes:

1. Assuming iteration is sorted leads to output changing across implementations or rehashes. Sort a copy or use an ordered container.

2. Using map[key] only to test membership inserts a default value. Use find instead.

3. Keeping iterators across an insertion that triggers rehash leaves invalid iterators. Reserve first where appropriate, or reacquire iterators after growth.

4. Defining equality without a matching hash can make equivalent keys unfindable. Hash exactly the fields used by equality.

For 1,000 expected unique keys, call reserve(1000) before bulk insertion. Treat bucket_count() and load_factor() as diagnostics. There is no universal best max_load_factor, more buckets do not automatically make the whole program faster, and GCC, Clang, and MSVC need not choose the same bucket count.

How exams and interviews test unordered containers

Start with the answer, then justify it:

1. Insert 5, 2, 5, 7, 2: an unordered_set has size 3 and count(5) == 1; an unordered_multiset has size 5 and count(5) == 2.

2. std::unordered_map<std::string, int> m; std::cout << m["ghost"] << ' ' << m.size(); prints 0 1 because operator[] inserts.

3. find is average O(1), but worst-case O(n) when many candidates need equality checks in the same collision group.

For a design question, choose unordered_map<string, int> for exact employee-ID-to-score lookup when traversal order is irrelevant. Choose map<string, int> when a report needs sorted keys or range queries. The operation requirement is the reason, not the blanket claim that unordered storage is always faster. Use Hashing MCQs: 12 Solved on Hash Functions (GATE) for more collision and complexity practice.

C++ unordered containers: the short version and next step

• Set versus map decides whether a mapped value exists.

• The multi variants decide whether equal keys may repeat.

• Hashing chooses candidate buckets.

• Equality confirms the key.

• Unordered iteration never promises sorted order.

Expect O(1) average exact-key operations and O(n) worst-case behaviour, and reserve before a known bulk insertion. For a focused route through the language and practice material, use the C++ Programming course. If you also need C, Java, Python, DSA, and placement-oriented coverage, Coding For Placements is the broader alternative.

Finish with code: build a character-frequency map for "BANANA" and verify A=3, N=2, and B=1 through fixed-key lookups. Replace unordered_map with map; the counts remain unchanged, while traversal becomes sorted.