[2026] C++ map vs unordered_map: Performance, Complexity, and How to Choose
![[2026] C++ map vs unordered_map: Performance, Complexity, and How to Choose](/og/s/cpp-comparison-02-map-unordered-map-en.webp)
이 글의 핵심
map vs unordered_map: sorted red-black tree vs hash table. When you need order or range queries, use map; for average-case fast lookup, unordered_map—plus hashing, collisions, and benchmarks.
For the abstract hash table model (buckets, collisions, average vs worst case), see hash tables. For Python dict and built-in mapping types alongside C++, see Python data types.
Introduction: “If I replace map with unordered_map, will it get faster?"
"I don’t need sorted order but I used map anyway”
The STL provides std::map (ordered) and std::unordered_map (hashed). Different complexities ⇒ choose for the workload. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
std::map<std::string, int> scores;
scores[Alice] = 100; // O(log n)
std::unordered_map<std::string, int> fast;
fast[Alice] = 100; // average O(1)This article covers:
- Internal structures
- Complexity
- Example benchmark numbers (illustrative)
- Memory tradeoffs
- Decision guidance
- Custom hashing
Table of contents
1. Internal structure
map: balanced BST (commonly red-black)
- Sorted by key
- Worst-case operations typically O(log n)
unordered_map: hash table
- Buckets + chaining/open addressing (implementation-defined)
- Average O(1); worst-case O(n) with bad hashing/adversarial inputs
2. Time complexity
| Operation | map | unordered_map |
|---|---|---|
| Insert/Erase/Lookup | O(log n) | average O(1), worst O(n) |
| Iteration | O(n), sorted order | O(n), unspecified order |
| min/max key | O(log n) begin/rbegin | O(n) scan |
3. Example benchmark narrative
Illustrative relative results from many blogs/microbenchmarks:
- Insert 1e6 ints: unordered_map often several× faster than map
- Lookup heavy: unordered_map often faster on average
- Iterate: similar order of magnitude
- Sorted iteration: map is natural; sorting a vector copy from unordered_map costs extra
Always validate on your data, compiler, and
-Oflags.
4. Memory
Tree nodes vs buckets + per-entry storage: depends on n, key size, implementation. Measure RSS if it matters.
5. Selection guide
아래 코드는 text를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
Need sorted keys or range queries (lower_bound/upper_bound)?
Yes -> map
No -> consider unordered_map
Worst-case latency guarantees critical?
Yes -> often map (log n) vs hash worst-case pathologies| Scenario | Prefer |
|---|---|
| Default fast lookup, no order | unordered_map |
| Sorted iteration / order statistics | map |
| Range search on keys | map |
| Hard realtime + predictable bounds | often map (depends) |
Examples
Word counts: usually unordered_map.
Leaderboard by score: often std::map with custom comparator or sorted container.
Cache: unordered_map + reserve.
Time-series range query: map + lower_bound/upper_bound.
Hash collisions and performance
- Bad hash ⇒ everything in one bucket ⇒ degrades toward linear scan.
- Use reserve when you know approximate final size to reduce rehashes.
Custom key types
- map:
operator<orCompare - unordered_map:
std::hashspecialization (or custom hasher) +operator==(orKeyEqual)
Summary
- Need order/range queries ⇒ map
- Average fast lookup, no order ⇒ unordered_map
- reserve to reduce rehash churn
- Profile instead of guessing
Related reading
- Map basics series posts
- Hashing guide
- Container selection guide