skip to content

In C++, when do you choose std::unordered_map over std::map, and what must the key type provide for each?

level: juniorimportance: must knowfreq 80%

answer

  1. buckets versus a sorted tree
  2. average versus guaranteed cost
  3. std::hash plus operator==
  4. iteration order is unspecified

basics

~20 s

std::unordered_map hashes keys into buckets: lookup is O(1) on average but O(n) in the worst case, iteration order is unspecified, and the key needs a hash and equality. std::map keeps keys sorted, guarantees O(log n), and needs only a less-than ordering.

solid answer

~40 s

Choose `std::unordered_map` when you only look keys up by exact value and want the best average speed; choose `std::map` when you need sorted iteration, range queries such as `lower_bound`, or a worst-case bound. `std::unordered_map<Key, T, Hash = std::hash<Key>, KeyEqual = std::equal_to<Key>>` needs a hash and an equality predicate for the key; `std::map<Key, T, Compare = std::less<Key>>` needs only a strict weak ordering, usually `operator<`. That difference matters in practice: `std::pair` and `std::tuple` work as `std::map` keys out of the box but have no `std::hash` specialization, so an `unordered_map` keyed by a pair needs a custom hasher. Its `find` is average O(1) and worst O(`size()`), its iterators are forward-only, and its iteration order is unspecified and can change after any insert that rehashes.

code

cpp · 15 lines
cpp
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> hashed{{"carol", 3}, {"alice", 1}, {"bob", 2}};
    std::map<std::string, int> sorted{{"carol", 3}, {"alice", 1}, {"bob", 2}};

    std::cout << "unordered_map:";
    for (const auto& [name, id] : hashed) std::cout << ' ' << name;  // unspecified order
    std::cout << "\nmap:";
    for (const auto& [name, id] : sorted) std::cout << ' ' << name;  // always sorted
    std::cout << "\nfirst at or after \"b\": " << sorted.lower_bound("b")->first << '\n';
}

go deeper

for a junior

Recall the core difference: std::map is sorted with O(log n) operations, std::unordered_map is hashed with average O(1) lookups and no order.

for a middle

Explain the key requirements, std::hash and operator== versus a comparator, and why pair keys need a custom hasher only in the hash map.

for a senior

Choose by workload: range queries, deterministic output and worst-case bounds favour std::map; exact-key hot paths favour the hash map, confirmed by measurement.

for a principal

Set a default for new code, for example unordered_map for exact-key caches and map for ordered or observable data, and make exceptions need a measurement.

## Two containers, two contracts Both containers map unique keys to values, and their member functions look almost identical, which is why the choice is often made by habit. Their guarantees are not the same: | Property | `std::map` | `std::unordered_map` | |---|---|---| | Structure | ordered by a comparator (a balanced tree in practice) | buckets selected by a hash | | `find`, `insert`, `erase` by key | O(log n) guaranteed | O(1) average, O(n) worst case | | Key requirements | `Compare`, default `std::less<Key>` | `Hash`, default `std::hash<Key>`, and `KeyEqual`, default `std::equal_to<Key>` | | Iteration order | sorted by key | unspecified; changes when the table rehashes | | Iterator category | bidirectional | forward | | Range queries (`lower_bound`, `upper_bound`) | yes | no | | Effect of insert on iterators | none invalidated | all may be invalidated by a rehash | `std::unordered_map` arrived in C++11; `std::map` has been in the library since C++98. ## What the key must provide For **`std::map`**, the key needs an ordering. With the default comparator that means `operator<` on the key type. Built-in types, `std::string`, `std::pair` and `std::tuple` (which compare lexicographically) all work immediately. For **`std::unordered_map`**, the key needs two things that must agree: - a **hash**: by default `std::hash<Key>`, which the library provides for arithmetic types, enumerations, pointers, `std::nullptr_t`, `std::string`, `std::string_view` and a few others; - an **equality**: by default `std::equal_to<Key>`, which calls `operator==`. For any other type, `std::hash<Key>` is a *disabled* specialization and using it is ill-formed. `std::pair<int, int>` is the classic surprise: there is no `std::hash` for pairs or tuples, so `std::unordered_map<std::pair<int, int>, int>` fails to compile (Apple clang 21 starts with `call to implicitly-deleted default constructor of 'std::hash<std::pair<int, int>>'`), while `std::map<std::pair<int, int>, int>` just works. ## Iteration order is not a feature `std::unordered_map` iterates in bucket order, which depends on the hash function, the bucket count and the insertion history. The snippet below printed `bob alice carol` for the hash map with Apple clang 21 and libc++; another library, another bucket count or one more insert can print something else. Code that formats output, writes snapshots or compares test results by iterating an `unordered_map` therefore has a latent bug: - sort the keys first, or - use `std::map` for anything whose order is observable, or - compare containers with `operator==`, which for unordered containers ignores order. ## Picking for a session cache A session cache that maps a session identifier to session state is the textbook `std::unordered_map` case: 1. Lookups are by exact key, from every request. 2. Nobody needs the sessions in key order. 3. The key, an integer or a string, already has a standard hash. It stops being the right choice when the cache must also expire "all sessions with an identifier below X" (a range query), when the output must be deterministic, or when a worst-case latency bound matters more than the average and the keys can be chosen by an adversary. ## Costs beyond big-O The complexity table hides constant factors that often decide the matter: - **Hashing reads the whole key.** `std::hash<std::string>` processes every character of a long key, while a `std::map` comparison stops at the first differing character. With long keys and few elements, a tree can win. - **Both containers allocate a node per element.** In libstdc++ and libc++, `std::map` is a red-black tree whose node holds parent, child and colour fields beside the element; `std::unordered_map` keeps a node with a next pointer (and often a cached hash) plus a separate bucket array. Neither is compact; a sorted `std::vector` or C++23 `std::flat_map` is, for read-mostly data. - **Rehash spikes.** An `unordered_map` that grows pays an occasional full rehash; a tree's cost per insert is steady. `reserve` removes the spikes when the final size is known. ## Common mistakes - Assuming `std::unordered_map` is always faster: for small maps, or for keys whose hash is expensive (long strings), `std::map` or even a sorted vector can win; measure. - Assuming O(1) is guaranteed: the standard states it as an average and gives `size()` as the worst case. - Expecting `std::map`-style iterator stability: every insert into an `unordered_map` may invalidate all iterators, although references to elements survive.

  • Why does std::unordered_map<std::pair<int, int>, int> fail to compile while std::map<std::pair<int, int>, int> works?
    `std::map` needs only `operator<`, which `std::pair` provides lexicographically. `std::unordered_map` needs `std::hash<std::pair<int, int>>`, and the standard library provides no hash for pairs or tuples, so that specialization is disabled and the container cannot be instantiated. Supply a hasher type as the third template argument that combines the two members.
  • Is it safe to compare two std::unordered_map objects with operator== if they were filled in different orders?
    Yes. Equality of unordered containers is defined element-wise regardless of order: same size, and each key's equivalent group in one container is a permutation of the other's. It costs O(n) on average and O(n^2) worst case, and it is only defined if both containers use equality predicates that behave the same.

  • std::unordered_map lookups are guaranteed O(1) in every case
  • std::unordered_map iterates in insertion order
  • std::pair keys work in std::unordered_map without a custom hash
  • std::unordered_map is always faster than std::map
  • std::unordered_map needs operator< on the key type