Should I use map or unordered_map?

Often unordered_map wins average-case lookup (O(1) vs O(log n)). Choose map when you need sorted order, range queries, or predictable worst-case bounds.

Why can unordered_map be slower than map sometimes?

Heavy hash collisions, expensive hash function, or very small n where constants dominate—benchmark.

How does map stay sorted?

Typically a balanced BST (commonly red-black): keys are ordered by the comparator (default less).

How do I reduce hash collisions in unordered_map?

reserve buckets, use a good hash, monitor load_factor and rehashing.

map needs strict weak ordering (usually operator< or custom Compare). unordered_map needs hash + equality.

C++ map vs unordered_map: Performance, Complexity, and How to Choose

2026년 3월 28일 · 15분 읽기 · 수정 2026년 3월 28일 Intermediate comparison

이 글의 핵심

Deep dive: map vs unordered_map internals, complexity, benchmarks, memory, and selection criteria.

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.

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

Internals
Complexity
Benchmarks
Memory
Selection
Custom keys
Summary

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 -O flags.

4. Memory

Tree nodes vs buckets + per-entry storage: depends on n, key size, implementation. Measure RSS if it matters.

5. Selection guide

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< or Compare
unordered_map: std::hash specialization (or custom hasher) + operator== (or KeyEqual)

Summary

Need order/range queries ⇒ map
Average fast lookup, no order ⇒ unordered_map
reserve to reduce rehash churn
Profile instead of guessing

Map basics series posts
Hashing guide
Container selection guide

Keywords

map vs unordered_map, C++ hash map, O(1) vs O(log n), std::unordered_map reserve

Browse the C++ series
C++ performance optimization
C++ Adapter Pattern