Library

since C++11

Basic

std::unordered_map

Hash map with O(1) average insert, lookup, and erase — the default associative container when key ordering is irrelevant.

std::unordered_map<K, V>since C++11

An open-addressed or chained hash table that maps unique keys to values, providing amortised O(1) insert, lookup, and erase at the cost of no key ordering and a minimum two-pointer overhead per bucket.

Overview

std::unordered_map stores key-value pairs in a hash table. The key is hashed to determine a bucket; elements within a bucket are compared with KeyEqual. The full template signature is:

cpp

template<
    class Key,
    class T,
    class Hash      = std::hash<Key>,
    class KeyEqual  = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;

Complexity guarantees (per the C++11 standard):

Operation	Average	Worst case
`find`, `count`, `contains`	O(1)	O(n)
`insert`, `emplace`, `try_emplace`	O(1)	O(n)
`erase` (by key or iterator)	O(1)	O(n)
Iteration over all elements	O(n)	O(n)

Worst-case occurs when many keys hash to the same bucket (collision chain). A quality hash function keeps average chain length near 1.

std::hash is specialised for all arithmetic types, std::string, std::string_view (C++17), pointers, and several vocabulary types — but not for user-defined structs or std::pair. Any key type without a std::hash specialisation requires a custom hasher.

Syntax

cpp

#include <unordered_map>

// (1) Default construction
std::unordered_map<std::string, int> m;

// (2) Initializer list — C++11
std::unordered_map<std::string, int> m2 = {
    {"alpha", 1}, {"beta", 2}, {"gamma", 3}
};

// (3) Range construction
std::vector<std::pair<std::string, int>> pairs = {{"x", 10}, {"y", 20}};
std::unordered_map<std::string, int> m3(pairs.begin(), pairs.end());

// (4) Custom hash and equality
std::unordered_map<MyKey, int, MyHash, MyEqual> m4;

// (5) Reserve buckets upfront (avoids rehash)
std::unordered_map<std::string, int> m5;
m5.reserve(1024);  // size hint — allocates ceil(1024 / max_load_factor) buckets

Examples

Insert strategies

cpp

std::unordered_map<std::string, std::vector<int>> index;

// operator[] — default-constructs value if key absent. Fine for scalars,
// but constructs an empty vector then copies for aggregates.
index["foo"].push_back(1);

// try_emplace — C++17: only constructs value if key is absent.
// Preferred for expensive-to-construct values: no wasted construction.
auto [it, inserted] = index.try_emplace("bar", std::vector{2, 3});

// insert_or_assign — C++17: always writes, returns {iterator, was_inserted}
index.insert_or_assign("foo", std::vector{99});

// insert — returns {iterator, bool}; does nothing if key exists
auto [it2, ok] = index.insert({"baz", std::vector{4}});
// ok == true because "baz" was absent

Lookup patterns

cpp

std::unordered_map<std::string, int> scores = {{"alice", 95}, {"bob", 80}};

// Safe read — never inserts
if (auto it = scores.find("alice"); it != scores.end()) {  // C++17 init-if
    std::println("alice: {}", it->second);  // C++23 std::println
}

// contains — C++20: boolean existence check without iterator overhead
if (scores.contains("bob")) {
    std::println("bob is present");
}

// at() — throws std::out_of_range for missing keys; safe on const maps
try {
    int s = scores.at("charlie");  // throws
} catch (const std::out_of_range&) { /* handle */ }

// operator[] — inserts 0 for missing keys, illegal on const maps
int& ref = scores["alice"];  // reference stable until next rehash
scores["new_entry"]++;       // inserts 0, then increments to 1

Erasing

cpp

std::unordered_map<int, std::string> m = {{1,"a"},{2,"b"},{3,"c"},{-1,"d"}};

m.erase(2);                  // by key; returns number of elements removed (0 or 1)
m.erase(m.find(3));          // by iterator; UB if iterator is end()

// erase_if — C++20: removes all elements matching predicate, returns count
std::size_t removed = std::erase_if(m, [](const auto& kv) {
    return kv.first < 0;
});

Custom hash for a struct key

The canonical hash-combine pattern (derived from the Boost approach) mixes bits to minimise collisions:

cpp

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t h = std::hash<int>{}(p.x);
        // Mix in y with a multiplicative constant and bit rotation
        h ^= std::hash<int>{}(p.y) + 0x9e37'79b9 + (h << 6) + (h >> 2);
        return h;
    }
};

struct PointEq {
    bool operator()(const Point& a, const Point& b) const noexcept {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_map<Point, std::string, PointHash, PointEq> grid;
grid[{0, 0}] = "origin";
grid[{1, 0}] = "east";

Since C++26, std::hash_combine is being standardised; until then, roll your own or use a library hasher.

Dispatch table with `std::function` (C++11)

cpp

#include <functional>

using BinOp = std::function<double(double, double)>;  // C++11

std::unordered_map<char, BinOp> ops = {
    {'+', [](double a, double b){ return a + b; }},
    {'-', [](double a, double b){ return a - b; }},
    {'*', [](double a, double b){ return a * b; }},
    {'/', [](double a, double b){ return b != 0 ? a / b : 0; }},
};

double eval(char op, double a, double b) {
    if (auto it = ops.find(op); it != ops.end())
        return it->second(a, b);
    throw std::invalid_argument("unknown op");
}

Bucket and load-factor tuning

cpp

std::unordered_map<int, int> m;

// Pre-allocate for known capacity — prevents O(n) rehash during fill
m.reserve(50'000);  // C++11 digit separators since C++14

std::println("buckets: {}", m.bucket_count());
std::println("load:    {:.2f}", m.load_factor());       // elements / buckets
std::println("max load: {:.2f}", m.max_load_factor());  // default 1.0

// Lower max_load_factor trades memory for fewer collisions
m.max_load_factor(0.5f);
m.reserve(50'000);  // re-reserve after changing the threshold

Best Practices

Prefer try_emplace over operator[] for complex values. operator[] default-constructs then assigns; try_emplace constructs in-place only when the key is absent, saving one construction and one move for types like std::vector or std::string.

Call reserve(n) before bulk insertion. Without it, every load-factor breach triggers a full rehash — O(n) work that's easily amortised to zero by one upfront call.

Lower max_load_factor for read-heavy, latency-sensitive maps. The default of 1.0 means buckets average one element. Setting it to 0.5–0.7 roughly halves collision probability at the cost of ~1.5× memory.

In performance-critical paths, evaluate absl::flat_hash_map or robin_hood::unordered_map. The standard's open interface leaves rehash and probing strategy to the implementation; third-party flat hash maps use open addressing with better cache locality and can be 2–5× faster for dense integer keys.

Keep hash functions noexcept. Hash and equality functors that throw will propagate exceptions out of find, breaking exception safety guarantees on containers.

Common Pitfalls

`operator[]` on a `const` map is a compile error

cpp

const std::unordered_map<std::string, int> cm = {{"a", 1}};
int v = cm["a"];     // compile error: operator[] is non-const
int v2 = cm.at("a"); // OK — at() has a const overload
auto it = cm.find("a"); // OK — find() has a const overload

`operator[]` silently inserts a default value

cpp

std::unordered_map<std::string, int> m = {{"x", 1}};
int v = m["missing"];  // inserts {"missing", 0} — m.size() is now 2!
// Use find/at/contains for read-only access

Iterators and references are invalidated by rehash

Any insert that triggers a rehash invalidates all iterators, pointers, and references into the map. References obtained via operator[] or find()->second must not be held across insertions unless you reserve capacity upfront.

cpp

auto& ref = m["key"];  // reference to value
m.insert({"new", 1});  // may rehash — ref is now dangling
ref = 42;              // undefined behaviour

Hash collision attacks (HashDoS)

If keys come from untrusted input (e.g., HTTP headers, JSON field names), an adversary can craft keys that all hash to the same bucket, degrading performance to O(n) per lookup. Mitigations:

Use a randomised seed (inject entropy into your hash functor at construction).
Use absl::flat_hash_map which randomises its internal seed.
Validate and cap input cardinality before populating the map.

Unspecified iteration order

Order is not preserved across insertions or rehashes, and differs between program runs (implementations may randomise the seed). Never rely on iteration order for correctness. If you need deterministic output, collect keys, sort them, then iterate.

Custom Hash Functions

Any type used as a key must have a std::hash specialisation — user-defined structs have none by default. The standard provides std::hash for arithmetic types, pointers, std::string, and a few vocabulary types, but not for custom structs or std::pair<K, V>.

cpp

// C++11
struct Point { int x, y; };

// Step 1: provide equality comparison
bool operator==(const Point& a, const Point& b) noexcept {
    return a.x == b.x && a.y == b.y;
}

// Step 2: specialise std::hash<Point> using hash_combine pattern (Boost-derived)
namespace std {
    template<>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const noexcept {
            std::size_t h = std::hash<int>{}(p.x);
            // XOR + bit mixing prevents structured keys (e.g. {0,1} vs {1,0})
            // from producing the same hash
            h ^= std::hash<int>{}(p.y) + 0x9e37'79b9u + (h << 6) + (h >> 2);
            return h;
        }
    };
}

std::unordered_map<Point, std::string> grid;  // uses std::hash<Point>
grid[{0, 0}] = "origin";

Lambda hashers and equality comparators can be passed as constructor arguments instead of specialising std::hash. This is useful for local key types or when you want multiple hash policies for the same type.

cpp

// C++11 — lambda hash and equality via explicit template parameters
auto point_hash = [](const Point& p) noexcept -> std::size_t {
    std::size_t h = std::hash<int>{}(p.x);
    h ^= std::hash<int>{}(p.y) + 0x9e37'79b9u + (h << 6) + (h >> 2);
    return h;
};
auto point_eq = [](const Point& a, const Point& b) noexcept {
    return a.x == b.x && a.y == b.y;
};

using PointHash  = decltype(point_hash);
using PointEqual = decltype(point_eq);
std::unordered_map<Point, int, PointHash, PointEqual> m(0, point_hash, point_eq);
m[{1, 2}] = 42;

There is no std::hash<std::pair<K, V>> in the standard library, so unordered_map<pair<int,int>, V> will not compile without a custom hasher. Either specialise std::hash for the pair type or use a struct wrapper with the hash_combine pattern shown above.

Transparent Hashing (C++20)

Before C++20, looking up a std::string key with a std::string_view forces a heap allocation. The standard std::hash<std::string> does not accept std::string_view, so the map must construct a temporary std::string to call find.

cpp

// Pre-C++20: unavoidable copy/allocation on every lookup
std::unordered_map<std::string, int> m = {{"hello", 1}};
std::string_view sv = "hello";
auto it = m.find(std::string(sv));  // must construct std::string — heap alloc

C++20 heterogeneous lookup eliminates the allocation by letting the hasher and equality accept any compatible type. Mark the hasher and equality with using is_transparent = void to opt in.

cpp

// C++20
struct TransparentHash {
    using is_transparent = void;  // enables heterogeneous lookup

    std::size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
    std::size_t operator()(const std::string& s) const noexcept {
        return std::hash<std::string_view>{}(s);
    }
};

struct TransparentEqual {
    using is_transparent = void;

    bool operator()(std::string_view a, std::string_view b) const noexcept {
        return a == b;
    }
};

std::unordered_map<std::string, int, TransparentHash, TransparentEqual> m;
m["hello"] = 1;

std::string_view sv = "hello";
auto it = m.find(sv);  // C++20: no allocation — sv passed directly to hash

absl::flat_hash_map and robin_hood::unordered_map both support heterogeneous lookup with their built-in string hashers, so find(string_view) is zero-copy without manual hasher authoring.

Bucket Operations and Load Factor Control

The relationship between elements and buckets is governed by the load factor: load_factor() == size() / bucket_count(). When load_factor() exceeds max_load_factor() (default 1.0), the map rehashes — roughly doubling bucket_count() and moving all elements.

cpp

// C++11
std::unordered_map<int, int> m;

m.reserve(10'000);           // hint: allocate enough buckets for 10 000 elements
m.max_load_factor(0.25f);    // aggressive: keep buckets 75% empty → fewer collisions
m.reserve(10'000);           // re-reserve after changing max_load_factor

// Inspect bucket distribution
std::cout << "bucket_count : " << m.bucket_count()  << '\n';
std::cout << "load_factor  : " << m.load_factor()   << '\n';
std::cout << "max_load_factor: " << m.max_load_factor() << '\n';

// rehash(n) forces bucket_count >= ceil(n / max_load_factor) even if size < n
m.rehash(64'000);

Inspecting bucket sizes can reveal hash collision attacks. If an adversary crafts keys that all land in the same bucket, lookup degrades from O(1) to O(n). Log the distribution before opening a server to untrusted input.

cpp

// C++11 — detect skewed bucket distribution
std::size_t max_chain = 0;
for (std::size_t i = 0; i < m.bucket_count(); ++i)
    max_chain = std::max(max_chain, m.bucket_size(i));

if (max_chain > 32)
    std::cerr << "Warning: possible hash collision attack — max chain " << max_chain << '\n';

reserve(n) is a size hint (number of elements); rehash(n) is a bucket hint. Both can be called at any time and may trigger a full rehash if the requested capacity exceeds the current bucket count.

insert vs emplace vs try_emplace

insert, emplace, and try_emplace all return std::pair<iterator, bool> but differ in when and how they construct the mapped value. Choosing the wrong one for expensive value types wastes a construction.

cpp

// C++11
std::unordered_map<std::string, std::vector<int>> m;

// insert — constructs a pair<const string, vector<int>> first, then moves it in
m.insert({"key", std::vector{1, 2, 3}});  // pair constructed, then move into map

// emplace — forwards arguments directly to pair's constructor; avoids one copy,
// but ALWAYS constructs the value, even if the key already exists
m.emplace("key", std::vector{4, 5});  // vector constructed even though "key" exists!

// The classic bug: emplace always evaluates its arguments
std::vector<int> expensive_to_build = {/* ... */};
m.emplace("key", std::move(expensive_to_build));  // moved-from even if key present

try_emplace (C++17) constructs the value only when the key is absent, making it the correct default for maps whose values are expensive to construct or move.

cpp

// C++17
std::unordered_map<std::string, std::vector<int>> m;
m["key"] = {1, 2, 3};

// try_emplace: if "key" exists, does nothing — vector{4,5} is never constructed
auto [it, inserted] = m.try_emplace("key", std::vector{4, 5});
// inserted == false, m["key"] is still {1, 2, 3}

// try_emplace also supports in-place value construction via variadic args
m.try_emplace("new_key", 5, 99);  // constructs vector<int>(5, 99) in-place if absent

For insert_or_assign (C++17), the value is always written, whether the key exists or not — the mirror image of try_emplace.

unordered_multimap: Multiple Values per Key

std::unordered_multimap<K, V> allows multiple entries with the same key; find returns an iterator to one of them and equal_range returns all. It shares the same hash table internals as unordered_map but never rejects duplicate keys.

cpp

// C++11
#include <unordered_map>

std::unordered_multimap<std::string, int> mm;
mm.insert({"fruit", 1});
mm.insert({"fruit", 2});
mm.insert({"fruit", 3});
mm.insert({"veggie", 10});

// equal_range returns [first, last) over all entries with matching key
auto [first, last] = mm.equal_range("fruit");
for (auto it = first; it != last; ++it)
    std::cout << it->second << ' ';  // prints 1 2 3 (order unspecified)

// count is O(k) where k is the number of matching entries — not O(1)
std::cout << mm.count("fruit") << '\n';  // 3

Prefer unordered_map<K, std::vector<V>> over unordered_multimap when you insert all values at once and then read them in batch. The vector variant makes one allocation per key, is more cache-friendly to iterate, and avoids the O(k) count cost.

cpp

// C++11 — batch grouping pattern
std::unordered_map<std::string, std::vector<int>> grouped;
for (auto& [key, val] : raw_pairs)
    grouped[key].push_back(val);

// All values for "fruit" are contiguous in memory
for (int v : grouped["fruit"])
    std::cout << v << ' ';

Use unordered_multimap when values are inserted incrementally and key multiplicity is unbounded; use the vector variant when grouping a known dataset.

Performance: Probing Strategies and Alternative Maps

std::unordered_map uses separate chaining — each bucket holds a linked list of elements. On a lookup, the hash identifies the bucket and the list is scanned linearly for a matching key. Every cache miss follows a pointer; for sparse maps with few collisions this is still one or two pointer dereferences, but it is fundamentally pointer-chasing.

Implementation	Collision strategy	Lookup (miss)	Lookup (hit)	Cache-friendly	Memory overhead
`std::unordered_map`	Chaining (linked list)	~2 cache misses	~2 cache misses	No	~48–56 B/element
`absl::flat_hash_map`	Open addressing (SIMD probing)	~1 cache miss	~1 cache miss	Yes	~10–16 B/element
`robin_hood::unordered_map`	Robin Hood open addressing	~1 cache miss	~1 cache miss	Yes	~8–12 B/element
`std::flat_map` (C++23)	Sorted vector (binary search)	O(log n)	O(log n)	Yes (dense)	~0 B overhead

Open addressing stores all elements in a contiguous array, so a probe sequence stays within a single cache line. absl::flat_hash_map additionally uses SSE2/AVX2 to match up to 16 candidate slots per cycle. For integer-keyed maps of moderate size, absl::flat_hash_map typically runs 2–5× faster than std::unordered_map.

cpp

// Drop-in replacement — same API, faster constants
// Requires: #include "absl/container/flat_hash_map.h"
absl::flat_hash_map<int, int> fast_map;
fast_map.reserve(100'000);
fast_map[42] = 1;
auto it = fast_map.find(42);  // SIMD-accelerated probe

Prefer std::unordered_map when: portability and no third-party dependencies matter. Prefer absl::flat_hash_map or robin_hood::unordered_map when: throughput is measured and the map is a hot path. Use std::flat_map (C++23) when: the map is built once and read many times and sorted order is acceptable.

See Also

std::map — ordered by key, O(log n) operations; use when sorted traversal is needed
std::unordered_multimap — same hash table, allows duplicate keys (C++11)
std::unordered_set — same internals, keys only (C++11)
std::flat_map — C++23 sorted-vector map; better cache locality than std::map, ordered iteration
absl::flat_hash_map / robin_hood::unordered_map — drop-in replacements with better constant factors for performance-critical code