[2026] C++ map & unordered_map Explained (Hash Map vs Ordered Map)

These containers realize the dictionary and hash table ideas from algorithm fundamentals—see hash tables for the underlying model and typical complexities.

What are map and unordered_map?

std::map and std::unordered_map store key→value pairs. They are often called dictionaries or maps. Why use them?

• Fast lookup by key
• Flexible key types (with proper ordering/hash)
• Automatic memory management
• Standard, portable interfaces

std::map<std::string, int> ages;
ages[Alice] = 25;

map vs unordered_map

Property	map	unordered_map
Order	Sorted by key	Unspecified iteration order
Typical complexity	O(log n)	Average O(1)
Implementation	Balanced BST (commonly red-black)	Hash table
Memory	Tree nodes	Buckets + entries
Range queries	lower_bound / upper_bound	not natural (sort a copy)
아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

std::map<int, std::string> m = {{3, "C"}, {1, "A"}, {2, "B"}};
// iterates 1, 2, 3
std::unordered_map<int, std::string> um = {{3, "C"}, {1, "A"}, {2, "B"}};
// iteration order unspecified

아래 코드는 mermaid를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

flowchart TD
    subgraph map["map (balanced BST)"]
        m1[2]
        m2[1]
        m3[3]
        m1 --> m2
        m1 --> m3
    end
    subgraph unordered_map["unordered_map (hash table)"]
        u1["Bucket ..."]
    end

Basic usage (sketch)

map: #include <map> — insert with insert, emplace, or operator[]. unordered_map: #include <unordered_map> — similar interface; prefer reserve when you know size.

Example: word frequency

Use unordered_map<std::string, int> for fast counting.

Example: student records sorted by ID

Use map<int, Student> when you want keys sorted for display or processing.

Example: LRU cache sketch

Often combines std::list + unordered_map for O(1) touch/evict patterns.

Common problems

Problem: operator[] side effects

m[key] inserts default if missing. 아래 코드는 cpp를 사용한 구현 예제입니다. 비동기 처리를 통해 효율적으로 작업을 수행합니다, 에러 처리를 통해 안정성을 확보합니다, 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

auto it = m.find("maybe");
if (it != m.end()) { /* use it->second */ }
// or
try { auto v = m.at("maybe"); } catch (...) {}

Problem: custom keys

Provide comparison for map, hash+eq for unordered_map.

Problem: erase while iterating

Use erase return value: it = m.erase(it); or collect keys first.

Optimization ideas

• Avoid accidental copies: pass keys/values by const& where appropriate.
• Compile with optimizations for realistic timings.
• unordered_map::reserve for large inserts.

Patterns

• Frequency counting: unordered_map<T,int>
• Grouping: map to keep groups ordered by key
• Index mapping: unordered_map<string,size_t>

FAQ (short)

Q: Performance?
A: map O(log n); unordered_map average O(1), worst O(n) with bad hashing. Q: Sorted traversal?
A: Use map, or copy unordered_map pairs into a vector and sort.

Related reading

• STL cheatsheet series
• Container selection
• set vs unordered_set

Keywords

C++ map, unordered_map, hash map, STL dictionary, lower_bound

Related posts

• Browse the C++ series
• C++ Adapter Pattern