Should I use map or unordered_map?

Default to unordered_map for lookup-heavy workloads — average O(1) vs O(log n) lookup. Use map when you need sorted iteration, range queries with lower_bound/upper_bound, or predictable worst-case performance without hash collision risk.

Why can unordered_map be slower than map sometimes?

Heavy hash collisions, an expensive hash function, or very small n where constants dominate. At n=10 elements, the O(log n) vs O(1) difference is negligible. Benchmark your specific workload.

How does map stay sorted?

std::map is typically implemented as a balanced binary search tree (red-black tree). Keys are ordered by the comparator, which defaults to std::less . Insertion, deletion, and lookup are all O(log n) worst case.

How do I use a custom struct as an unordered_map key?

Specialize std::hash for your type (or provide a custom hasher), and implement operator==. Without a hash specialization, the compiler will not find a hash function and the code will not compile.

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

2026년 3월 28일 · 18분 읽기 · 수정 2026년 4월 17일 intermediate tutorial

이 글의 핵심

map vs unordered_map: sorted red-black tree vs hash table. O(log n) vs average O(1) lookup, range query support, custom key hashing, and benchmarks to help you choose the right container.

The Core Question

You need an associative container — something that maps keys to values. C++ gives you two primary choices: std::map and std::unordered_map. They have the same interface for basic operations but dramatically different performance characteristics and different capabilities.

The short answer: use unordered_map by default, switch to map when you need ordering.

The detailed answer requires understanding what each actually does.

Internal Structures

std::map: Red-Black Tree

std::map is backed by a self-balancing binary search tree (typically a red-black tree). Every node in the tree holds a key-value pair. The tree maintains the invariant that all keys in the left subtree are less than a node’s key, and all keys in the right subtree are greater.

         "dog"
        /     \
     "cat"   "fox"
     /   \
  "ant" "cow"

This structure means:

Iteration is always sorted — in-order traversal yields keys in ascending order
Range queries work naturally — lower_bound("cat") jumps to the first key ≥ “cat” in O(log n)
Every operation is O(log n) worst case — there are no hash collision edge cases

std::unordered_map: Hash Table

unordered_map is backed by an array of buckets. When you insert a key, the hash function computes a bucket index, and the entry is stored there (with chaining if the bucket is occupied).

bucket[0]:  "dog" → 3
bucket[1]:  (empty)
bucket[2]:  "cat" → 1 → "cow" → 2  (both hash to bucket 2)
bucket[3]:  "ant" → 5

This structure means:

Average O(1) for insert/lookup/erase — compute hash, go to bucket, done
No ordering — iteration order is undefined and may change after rehashing
Worst case O(n) — all keys hash to the same bucket (hash flood attack)

Complexity Comparison

Operation	`std::map`	`std::unordered_map`
Insert	O(log n)	O(1) avg, O(n) worst
Erase	O(log n)	O(1) avg, O(n) worst
Lookup	O(log n)	O(1) avg, O(n) worst
Iteration	O(n), sorted	O(n), unordered
`lower_bound`	O(log n)	Not available
`upper_bound`	O(log n)	Not available
Min/max key	O(log n) via `begin()`/`rbegin()`	O(n) — must scan all entries

Code Examples

Basic Operations (Identical API)

#include <map>
#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Both have the same basic interface
    std::map<std::string, int>          ordered;
    std::unordered_map<std::string, int> hashed;

    // Insert
    ordered["Alice"]  = 95;
    ordered["Bob"]    = 82;
    ordered["Charlie"] = 91;

    hashed["Alice"]   = 95;
    hashed["Bob"]     = 82;
    hashed["Charlie"] = 91;

    // Lookup
    std::cout << ordered.at("Alice") << '\n';   // 95
    std::cout << hashed.at("Alice")  << '\n';   // 95

    // Check existence
    if (ordered.count("Dave") == 0)
        std::cout << "Dave not in ordered map\n";

    if (hashed.find("Dave") == hashed.end())
        std::cout << "Dave not in hashed map\n";

    // Iteration — map always sorted, unordered_map order undefined
    std::cout << "map (sorted):\n";
    for (const auto& [key, val] : ordered)
        std::cout << "  " << key << ": " << val << '\n';
    // Alice: 95
    // Bob: 82
    // Charlie: 91

    std::cout << "unordered_map (any order):\n";
    for (const auto& [key, val] : hashed)
        std::cout << "  " << key << ": " << val << '\n';
    // Order unspecified — could be any permutation
}

Range Query — map Exclusive

#include <map>
#include <string>
#include <iostream>

int main() {
    // Time-series data — timestamps map to events
    std::map<int, std::string> events;
    events[100] = "user login";
    events[200] = "page view";
    events[350] = "purchase";
    events[400] = "user logout";
    events[500] = "session end";

    // Find all events between t=150 and t=400 (inclusive)
    auto begin = events.lower_bound(150);  // first key >= 150
    auto end   = events.upper_bound(400);  // first key > 400

    for (auto it = begin; it != end; ++it)
        std::cout << "t=" << it->first << ": " << it->second << '\n';
    // t=200: page view
    // t=350: purchase
    // t=400: user logout

    // This range query is O(log n) to find bounds + O(k) to iterate k results
    // With unordered_map, you'd need O(n) to scan all entries
}

Performance-Optimized unordered_map

#include <unordered_map>
#include <string>
#include <vector>

// Pre-allocate buckets to avoid rehashing during insertions
std::unordered_map<std::string, int> wordCount(const std::vector<std::string>& words) {
    std::unordered_map<std::string, int> counts;

    // Reserve enough buckets for expected number of unique words
    // This prevents rehashing (which copies all elements to a larger table)
    counts.reserve(words.size());  // worst case: all unique

    for (const auto& w : words)
        ++counts[w];

    return counts;
}

int main() {
    std::vector<std::string> text = {
        "the", "cat", "sat", "on", "the", "mat", "the", "cat"
    };

    auto freq = wordCount(text);
    // Average O(1) per insertion, no rehashing because we reserved upfront

    std::cout << "the: " << freq["the"] << '\n';  // 3
    std::cout << "cat: " << freq["cat"] << '\n';  // 2
}

Custom Key Types

map: Needs Comparator

std::map requires that keys have a strict weak ordering — either operator< or a custom comparator:

#include <map>
#include <string>

struct Point {
    int x, y;
    // For map: operator< defines the ordering
    bool operator<(const Point& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;  // tie-break by y
    }
};

int main() {
    std::map<Point, std::string> labels;
    labels[{0, 0}] = "origin";
    labels[{1, 0}] = "right";
    labels[{0, 1}] = "up";

    // Iteration is sorted by (x, y)
    for (const auto& [pt, name] : labels)
        std::cout << "(" << pt.x << "," << pt.y << "): " << name << '\n';
    // (0,0): origin
    // (0,1): up
    // (1,0): right
}

unordered_map: Needs Hash + Equality

#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

// Specialize std::hash for Point
namespace std {
template<>
struct hash<Point> {
    size_t operator()(const Point& p) const {
        // Combine hashes of x and y
        // Common pattern: use XOR with a bit shift to reduce collisions
        size_t hx = std::hash<int>{}(p.x);
        size_t hy = std::hash<int>{}(p.y);
        return hx ^ (hy << 32) ^ (hy >> 32);
    }
};
}

int main() {
    std::unordered_map<Point, std::string> grid;
    grid[{0, 0}] = "origin";
    grid[{1, 0}] = "right";

    auto it = grid.find({0, 0});
    if (it != grid.end())
        std::cout << it->second << '\n';  // origin
}

A better hash combiner (avoids patterns that cause collisions with symmetric pairs like (1,2) and (2,1)):

// Better: use a proper mixing function
size_t operator()(const Point& p) const {
    size_t seed = 0;
    auto combine = [&seed](size_t val) {
        // Boost hash_combine pattern
        seed ^= val + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    };
    combine(std::hash<int>{}(p.x));
    combine(std::hash<int>{}(p.y));
    return seed;
}

When Collisions Hurt Performance

If all keys hash to the same bucket, unordered_map degrades to O(n) for every lookup:

// Adversarial example — imagine keys that all produce the same hash
// (unusual with std::string, but common with poorly-written custom hashers)

std::unordered_map<int, int> m;
m.reserve(1000);

for (int i = 0; i < 1000; ++i) {
    m[i] = i;
}

// Check load factor — above 1.0 triggers rehashing in most implementations
std::cout << "load_factor: " << m.load_factor()     << '\n';   // typically ~0.5–1.0
std::cout << "max before rehash: " << m.max_load_factor() << '\n';  // default 1.0

// If you observe degraded lookup performance:
// 1. Check load_factor() — if near max_load_factor(), rehashing is happening
// 2. Profile your hash function — std::string default hash is usually fine
// 3. Consider a custom hash (Robin Hood, FNV, etc.) for critical paths

Benchmark Numbers (Illustrative)

Results vary by CPU, allocator, and key type. These are representative relative magnitudes for 1M string keys:

Operation	`map`	`unordered_map`
Insert 1M keys	~450ms	~90ms (5× faster)
Lookup 1M keys	~250ms	~50ms (5× faster)
Sorted iteration	O(n) natural	O(n log n) (need to sort)
Reserve + insert	same	~60ms (more cache-friendly)

Always benchmark your actual workload — key type, hash quality, cache effects, and compiler flags (-O2 vs -O3) all matter. The numbers above assume -O2, GCC/Clang, x86.

For integer keys (int, uint64_t), the gap is larger because hashing integers is trivial and the O(log n) tree traversal costs more relatively.

For std::string keys, the comparison cost in map (which must compare strings character by character) adds to the O(log n) constant, widening the gap further.

Decision Guide

Do you need sorted iteration or range queries (lower_bound/upper_bound)?
  Yes → std::map

Do you need the minimum or maximum key efficiently?
  Yes → std::map (begin() / rbegin())

Is worst-case latency critical and hash floods a concern?
  Yes → std::map (O(log n) guaranteed)

Otherwise:
  → std::unordered_map
  → reserve() to avoid rehashing if you know the size upfront
  → profile if performance matters

Use Case	Container
Word frequency counter	`unordered_map`
Configuration key-value store	`unordered_map`
Time-series events with range queries	`map`
Leaderboard (sorted by score)	`map` with score as key, or sorted vector
Cache (fixed-size with LRU eviction)	`unordered_map` + list
DNS lookup cache	`unordered_map`
Index for database range queries	`map`

Key Takeaways

unordered_map: average O(1) lookup, no ordering, potential worst-case O(n) with bad hash — the right default for lookup-heavy workloads
map: O(log n) guaranteed, sorted iteration, lower_bound/upper_bound range queries — use when ordering matters
reserve(n) before filling an unordered_map with n entries — eliminates rehashing overhead
Custom keys for map: implement operator< or provide a Compare type
Custom keys for unordered_map: specialize std::hash<T> and implement operator==
Hash quality matters — a poor hash that clusters keys in the same bucket kills O(1) performance; the Boost hash_combine pattern reduces collision risk
Benchmark before assuming — the O(1) vs O(log n) difference matters for large n; at n=10 they are equivalent

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. map vs unordered_map: sorted red-black tree vs hash table. When you need order or range queries, use map; for average-ca… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

[Hash Table | O(1) Search Data Structure Complete Guide](/en/blog/algorithm-series-03-hash-table/
C++ map vs unordered_map 심층 비교 | ‘어느 게 빠를까?’ 성능 비교와 선택 가이드
C++ STL vector | ‘배열보다 편한’ 벡터 완벽 정리 [실전 예제]

이 글에서 다루는 키워드 (관련 검색어)

C++, STL, map, unordered_map, hash table, performance, data structures 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.