unordered_map & unordered_set

std::unordered_map and std::unordered_set are hash-table based alternatives to std::map and std::set. They store the same kind of data — unique keys, or key-value pairs — but use a hash table internally instead of a balanced tree, trading away ordering for, on average, much faster lookups.

Basic usage

unordered_map_basics.cpp

CPP

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

int main() {
    std::unordered_map<std::string, int> ages;

    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages.insert({"Carol", 35});

    // Iteration order is UNSPECIFIED — do not rely on it.
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << std::endl;
    }

    if (ages.find("Bob") != ages.end()) {
        std::cout << "Found Bob" << std::endl;
    }

    ages.erase("Bob");
    std::cout << ages.count("Bob") << std::endl; // 0

    return 0;
}

unordered_set_basics.cpp

CPP

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> nums = {30, 10, 20, 10};  // duplicate ignored

    std::cout << nums.size() << std::endl; // 3

    if (nums.find(20) != nums.end()) {
        std::cout << "20 is present" << std::endl;
    }

    return 0;
}

map vs. unordered_map

Property	std::map / std::set	std::unordered_map / std::unordered_set
Underlying structure	Balanced binary tree (red-black tree)	Hash table
Iteration order	Sorted by key	Unspecified — do not rely on it
Average time complexity	O(log n) for insert/find/erase	O(1) for insert/find/erase
Worst-case time complexity	O(log n) — guaranteed	O(n) — possible with many hash collisions
Memory overhead	Tree node pointers (parent, left, right)	Hash table buckets, often with extra reserved capacity
Key requirement	Must support `<` (a strict weak ordering)	Must support `==` and have a `std::hash` specialization

When to choose which

If you need to iterate in sorted key order, or you need operations like “find the smallest key greater than X” (which std::map supports via lower_bound/upper_bound), the tree-based containers are the right tool — the hash-based versions cannot do this efficiently. If you only care about fast lookup, insertion, and removal, and don't need any ordering at all, unordered_map/unordered_set is usually the faster choice in practice, thanks to average O(1) operations.

Custom key types need a hash function

The standard library already provides std::hash specializations for built-in types and std::string, so those work as unordered_map/unordered_set keys immediately. For your own types, you need to provide a hash function — either by specializing std::hash<YourType> or by passing a custom hash functor as a template argument.

custom_hash.cpp

CPP

#include <unordered_set>
#include <functional>

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

// Specializing std::hash lets Point be used as an unordered_set/unordered_map key.
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> points;
    points.insert({1, 2});
    points.insert({3, 4});
    return 0;
}

Rule of thumb

Need sorted iteration, range queries, or predictable ordering? Reach for map/set. Just need the fastest possible average lookup and don't care about order? Reach for unordered_map/unordered_set. When in doubt for plain key-value lookups with no ordering requirement, the unordered versions are usually the better default in modern C++.

Hash-table based; average O(1), worst-case O(n) for insert/find/erase.
No ordering guarantee — never assume iteration order is stable or sorted.
Custom key types need operator== and a std::hash specialization (or custom hasher).