std::unordered_map<Key, Value> is a hash-table-backed key-value container that gives average O(1) insert, find, and erase. It's the hash counterpart to std::map, and like std::unordered_set from the previous chapter, it trades sorted order for raw speed. std::unordered_multimap is the duplicate-keys variant. This chapter covers the storage layout, the API including the operator[] insertion gotcha, custom hashing for user-defined keys, rehashing behaviour, and when to reach for unordered_map over map.

A std::unordered_map<Key, Value> is a hash table whose buckets hold std::pair<const Key, Value> nodes. The Key is const because changing the key after insertion would put the entry in the wrong bucket; the value is freely mutable.

The picture mirrors unordered_set from the previous chapter, with the difference that each node holds a key and a value instead of just a key.

The hash is computed from the key only. The value rides along inside the same node. Bucket 2 holds two entries whose keys collided into the same bucket; lookups walk the chain comparing keys with operator== until they hit a match.

The iteration order isn't sorted and isn't insertion order. Two runs of the same program can produce identical output, but the order isn't part of the contract. A rehash, triggered automatically as the table grows, can reshuffle the visible order.

Average O(1) for insert, find, erase, operator[], and at. Worst case is O(n) when all keys end up in the same bucket. The bucket interface and rehashing rules from the unordered_set chapter all apply here too.

Most of the API matches std::map, just with different complexity guarantees. A tour of the everyday operations, using a price lookup table.

insert({k, v}) adds an entry only if the key isn't already present. If it is, the insert is rejected. The return type is a pair<iterator, bool> like unordered_set::insert.

The second insert returns false and leaves the existing value alone. For the new value to win, use insert_or_assign or assign through operator[].

at is the safe lookup. It returns a reference to the value if the key exists, and throws std::out_of_range if it doesn't. It doesn't insert anything.

The exception type is std::out_of_range regardless of compiler; the message text differs across implementations.

C++20 added contains, which is the cleanest way to ask "is this key here?".

Before C++20 the idioms were stock.count("mouse") > 0 or stock.find("mouse") != stock.end(). Use contains when the compiler supports it.

operator[] on a map has two behaviors. If the key exists, it returns a reference to the value. If the key doesn't exist, it default-constructs a new value, inserts the new entry, and returns a reference to the freshly inserted value.

That second behaviour is what's needed when building a counter.

counts[item]++ works because, on the first encounter of each key, the value is default-constructed (int{} is 0), then incremented to 1. Subsequent encounters find the existing entry and increment.

It's a trap for read-only access. Reading a non-existent key through operator[] grows the map.

The lookup for tablet looked harmless, but operator[] inserted tablet -> 0 as a side effect. The map grew without anyone explicitly inserting.

The right fix depends on intent:

operator[] also requires the value type to be default-constructible. A std::unordered_map<std::string, NonDefaultThing> won't allow operator[] unless NonDefaultThing has a default constructor.

operator[] on a missing key inserts a default-constructed value. For small types like int that's nothing, but for a std::vector or another container, that's a fresh allocation. To avoid the insert, use find or at.

C++17 introduced two operations that address recurring issues with insert and operator[].

insert_or_assign(k, v) is the "upsert" usually wanted: it inserts if k is absent and overwrites the value if k is present. It returns a pair<iterator, bool> where the bool indicates whether an insert happened.

The first call inserts. The second overwrites. Without insert_or_assign the alternatives are insert (which keeps the old value) or operator[] = (which works but reads less obviously).

try_emplace(k, args...) is the partner: it inserts a new entry constructed from args only if k is absent. The construction of the value happens only if the key is missing, which matters when the value's constructor is expensive.

The 1000-element vector argument is constructed before the try_emplace call, but try_emplace forwards the arguments separately and only constructs the value if it needs to. With emplace({"alice", std::vector<int>(1000, 0)}), the temporary pair (including the big vector) is built before the call even runs.

For pricing tables and counters where the value is a primitive type, operator[] is fine. For maps whose values are containers, smart pointers, or other types where construction matters, try_emplace is the safer call.

For built-in types and std::string, std::hash is already defined and the map works directly. For user-defined keys, a hash function has to be supplied. The mechanics are the same as for unordered_set, but a concrete example is worth showing because composite keys are common in real applications.

A map keyed by (productId, regionId). A small struct captures the key:

Both fields of ProductId participate in the hash and in the equality check, so two records with the same id but different region get distinct buckets and distinct entries.

The combine step h1 ^ (h2 << 1) is the same mixer from the unordered_set chapter. For real code, prefer something stronger such as boost::hash_combine:

The magic constant 0x9e3779b9 is the fractional part of the golden ratio scaled to 32 bits, chosen because it spreads bits evenly. The exact algorithm doesn't matter for correctness, only for collision distribution.

The alternative to specialising std::hash is to pass a functor as a template argument:

Use the std::hash specialisation when the key type is local and every container should hash it the same way. Use a functor argument when the key isn't local, or when one specific container needs different hashing than the default.

A degenerate hash that collides every key wrecks an unordered_map exactly like it does an unordered_set. All entries pile into one bucket, and every lookup walks the entire chain. Test composite hashes on representative data before shipping.

The iteration order of an unordered_map is unspecified. The standard doesn't promise anything about it, and two implementations are free to produce different orders for the same inserts. Even within a single implementation, the order can change as the map grows.

Consider this experiment.

The two iterations produce different orders on the same data, because the reserve triggered a rehash that put each element in a different bucket. For code that relies on iteration order, use std::map (sorted by key) or an additional std::vector<Key> that tracks insertion order alongside the map.

This also means iterators are invalidated whenever a rehash happens. Inside any code that inserts while iterating, that's a hazard.

The safe pattern is to collect the new entries into a std::vector while iterating, then insert them afterwards.

Everything from the unordered_set chapter applies. bucket_count, load_factor, max_load_factor, rehash, and reserve work identically. The two knobs that matter day-to-day are reserve(n) (size up front when the expected count is known) and max_load_factor(f) (control the trade-off between memory and chain length).

reserve(n) sizes the bucket array so the load factor stays below the default max (1.0) after n inserts. No rehashes happen during the loop.

A rehash is O(n) work for one call. For 10,000 inserts without reserve, a dozen or more rehashes may occur, each doing a linear sweep over what's already there. reserve flattens the cost curve.

Rehashes cost O(n) per occurrence. When the final size can be estimated within a factor of 2, call reserve upfront to skip the spikes.

std::unordered_multimap<Key, Value> is the duplicate-keys version. Several entries can share the same key, each with its own value. The bucket structure is identical; collisions and same-key entries both live in chains.

Differences from unordered_map:

When to choose unordered_multimap over unordered_map<Key, std::vector<Value>>?

Both approaches work; pick by which one reads more naturally for the problem.

The structural comparison from the unordered_set chapter carries over to maps. The headline summary.

Choose unordered_map when:

Choose map when:

For most general-purpose key-value lookup, unordered_map is the default.

The sorted order from map is a contract. The other order is whatever the hash function and bucket layout produced; don't rely on it.