C++ map vs unordered_map: When to Use Each and How They Work

What Are These Containers?

Both std::map and std::unordered_map store key → value pairs and let you look up a value by its key. The difference is in how they store and find elements:

• std::map: stores keys in sorted order using a balanced binary search tree (typically red-black tree). Every operation is O(log n).
• std::unordered_map: stores keys in hash buckets. Average O(1) lookup, but no ordering guarantee.

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

int main() {
    std::map<std::string, int> ordered;
    ordered["banana"] = 3;
    ordered["apple"] = 1;
    ordered["cherry"] = 2;

    // Iterates in alphabetical order: apple, banana, cherry
    for (const auto& [key, val] : ordered) {
        std::cout << key << ": " << val << '\n';
    }

    std::unordered_map<std::string, int> hashed;
    hashed["banana"] = 3;
    hashed["apple"] = 1;
    hashed["cherry"] = 2;

    // Iteration order is unspecified — depends on hash values
    for (const auto& [key, val] : hashed) {
        std::cout << key << ": " << val << '\n';
    }
}

---

Comparison Table

Property	std::map	std::unordered_map
Ordering	Sorted by key	No guaranteed order
Lookup	O(log n)	Average O(1), worst O(n)
Insert	O(log n)	Average O(1), worst O(n)
Iteration	Sorted	Unspecified
Range queries	lower_bound, upper_bound	Not natural
Memory	Tree nodes (extra pointers)	Hash buckets + entries
Key requirement	operator< (strict weak order)	std::hash<K> + operator==
Iterator invalidation	Insert: stable; erase: only the erased element	Rehash invalidates all; erase: only erased element

---

Basic Usage

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

// --- map ---
std::map<int, std::string> students;

// Insert
students[101] = "Alice";
students.insert({102, "Bob"});
students.emplace(103, "Carol");  // most efficient

// Lookup
auto it = students.find(101);
if (it != students.end()) {
    std::cout << it->second << '\n';  // Alice
}

// Access — throws if missing
try {
    std::string name = students.at(999);  // throws std::out_of_range
} catch (const std::out_of_range& e) {
    std::cerr << "Not found\n";
}

// --- unordered_map ---
std::unordered_map<std::string, int> wordCount;

// Reserve to avoid rehashing
wordCount.reserve(1000);

wordCount["hello"]++;
wordCount["world"]++;
wordCount["hello"]++;
// wordCount["hello"] == 2

---

The operator[] Pitfall

operator[] has a dangerous side effect: if the key doesn’t exist, it inserts a default-constructed value and returns a reference to it.

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

// PROBLEM: this inserts "Bob" with value 0
std::cout << ages["Bob"] << '\n';  // prints 0, AND inserts "Bob"!

// ages now has {"Alice": 25, "Bob": 0}
std::cout << ages.size() << '\n';  // 2 — you created an entry accidentally

Safe alternatives:

// Option 1: find() — no insertion, returns end() if missing
auto it = ages.find("Bob");
if (it != ages.end()) {
    std::cout << it->second << '\n';
} else {
    std::cout << "Not found\n";
}

// Option 2: at() — no insertion, throws if missing
try {
    int age = ages.at("Bob");
} catch (const std::out_of_range&) {
    std::cout << "Not found\n";
}

// Option 3: contains() (C++20)
if (ages.contains("Bob")) {
    std::cout << ages.at("Bob") << '\n';
}

When operator[] IS correct: when you intentionally want to insert-or-default:

// Word frequency counting — default 0 if not present, then increment
std::unordered_map<std::string, int> freq;
std::string word;
while (std::cin >> word) {
    freq[word]++;  // correct use of operator[] — insert 0 then increment
}

---

Practical Patterns

Word Frequency Counter

#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>

std::unordered_map<std::string, int> countWords(const std::string& text) {
    std::unordered_map<std::string, int> freq;
    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        freq[word]++;
    }
    return freq;
}

int main() {
    auto freq = countWords("the quick brown fox jumps over the lazy dog the");

    // Sort by frequency (descending) — copy to vector first
    std::vector<std::pair<std::string, int>> sorted(freq.begin(), freq.end());
    std::sort(sorted.begin(), sorted.end(),
        [](const auto& a, const auto& b) { return a.second > b.second; });

    for (const auto& [word, count] : sorted) {
        std::cout << word << ": " << count << '\n';
    }
    // the: 3
    // quick: 1, brown: 1, ...
}

Grouping with map (Sorted Output)

#include <map>
#include <vector>
#include <string>

struct Employee {
    std::string name;
    std::string department;
};

std::map<std::string, std::vector<std::string>> groupByDepartment(
    const std::vector<Employee>& employees)
{
    std::map<std::string, std::vector<std::string>> groups;
    for (const auto& emp : employees) {
        groups[emp.department].push_back(emp.name);  // insert-or-append
    }
    return groups;
}

// Result iterates departments in alphabetical order

Range Query with map

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> events = {
        {2020, "Event A"}, {2021, "Event B"}, {2022, "Event C"},
        {2023, "Event D"}, {2024, "Event E"}
    };

    // Find all events in [2021, 2023]
    auto begin = events.lower_bound(2021);
    auto end = events.upper_bound(2023);  // one past 2023

    for (auto it = begin; it != end; ++it) {
        std::cout << it->first << ": " << it->second << '\n';
    }
    // 2021: Event B
    // 2022: Event C
    // 2023: Event D
}

This range query pattern is only possible with std::map — unordered_map has no ordering.

---

Erasing During Iteration

The safe pattern uses the return value of erase():

std::map<std::string, int> scores = {
    {"Alice", 85}, {"Bob", 42}, {"Carol", 91}, {"Dave", 38}
};

// Remove entries with score below 50
auto it = scores.begin();
while (it != scores.end()) {
    if (it->second < 50) {
        it = scores.erase(it);  // erase returns iterator to next element
    } else {
        ++it;
    }
}
// scores: {"Alice": 85, "Carol": 91}

// Alternative: collect keys first, then erase (clearer intent)
std::vector<std::string> toRemove;
for (const auto& [name, score] : scores) {
    if (score < 50) toRemove.push_back(name);
}
for (const auto& name : toRemove) {
    scores.erase(name);
}

---

Custom Key Types

Custom Key for std::map

Need operator< (strict weak ordering):

struct Point {
    int x, y;

    // Required for map<Point, ...>
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

std::map<Point, std::string> locations;
locations[{0, 0}] = "origin";
locations[{1, 2}] = "near";

Custom Key for std::unordered_map

Need std::hash specialization and operator==:

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

// Hash specialization in std namespace
template<>
struct std::hash<Point> {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 32);  // simple combination
    }
};

std::unordered_map<Point, std::string> grid;
grid[{0, 0}] = "origin";

---

Performance Notes

unordered_map is faster for lookups but has higher worst-case behavior when there are hash collisions:

                  Average    Worst Case
unordered_map     O(1)       O(n) — all keys hash to same bucket
map               O(log n)   O(log n) — always

Memory:
unordered_map     Higher overhead (load factor, buckets)
map               Lower for small maps, higher for large (tree nodes)

For large maps: unordered_map with reserve() is typically 2-5x faster for lookups.

std::unordered_map<int, std::string> m;
m.reserve(10000);  // pre-allocate for ~10000 elements
m.max_load_factor(0.7f);  // rehash when 70% full (default is 1.0)

---

Key Takeaways

• Use unordered_map by default — O(1) average lookup, good for most key types
• Use map when you need sorted iteration, range queries with lower_bound/upper_bound, or when keys aren’t hashable
• operator[] inserts if the key is missing — use find() or at() when you don’t want that behavior
• Erase during iteration: use it = m.erase(it) pattern, or collect keys first
• Custom keys: map needs operator<, unordered_map needs std::hash<K> + operator==
• reserve() on unordered_map before large batch inserts to avoid repeated rehashing

---

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Master C++ std::map and std::unordered_map: ordered vs hash-based lookup, iterator invalidation, operator[] pitfalls, cu…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence. See the C++ series index for the full picture.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

---

Related Articles (Internal Links)

Other articles related to this topic.

• Hash Table | O(1) Search Data Structure Complete Guide
• C++ set/unordered_set | ‘중복 제거’ 완벽 가이드
• C++ string | ‘문자열 처리’ 완벽 가이드 [실전 함수 총정리]
• C++ STL vector | ‘배열보다 편한’ 벡터 완벽 정리 [실전 예제]

---

Keywords Covered in This Article (Related Search Terms)

This article covers C++, map, unordered_map, hash map, STL, dictionary.