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

· 10분 읽기 · 수정 Beginner tutorial
C++ map & unordered_map Explained (Hash Map vs Ordered Map)

이 글의 핵심

Learn map vs unordered_map: ordering, performance, basics, and common pitfalls like accidental inserts via operator[].

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

Propertymapunordered_map
OrderSorted by keyUnspecified iteration order
Typical complexityO(log n)Average O(1)
ImplementationBalanced BST (commonly red-black)Hash table
MemoryTree nodesBuckets + entries
Range querieslower_bound / upper_boundnot natural (sort a copy)
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
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.

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.

  • STL cheatsheet series
  • Container selection
  • set vs unordered_set

Keywords

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