C++ map vs unordered_map: Complexity, Pitfalls, and When to Use Each

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 share the same interface for basic operations but have different performance characteristics and different capabilities.

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

The longer answer depends on what each one actually does internally.

---

Internal Structures

std::map: Red-Black Tree

std::map is backed by a self-balancing binary search tree (a red-black tree in all mainstream implementations). Every node holds one key-value pair plus parent/left/right pointers and a color bit. All keys in a node’s left subtree are less than its 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 not less than “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 in that bucket’s linked list (the standard’s interface effectively requires separate chaining with node-based storage).

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 the hash, go to the bucket, compare a few keys.
• No ordering: iteration order is unspecified and can change after a rehash.
• Worst case O(n): if many keys land in the same bucket, lookup degrades to a linear scan.

---

Comparison at a Glance

Property	std::map	std::unordered_map
Insert / erase / lookup	O(log n)	O(1) average, O(n) worst
Iteration	O(n), sorted	O(n), unspecified order
lower_bound / upper_bound	O(log n)	Not available
Min / max key	O(1) via begin() / rbegin()	O(n), must scan every entry
Key requirement	operator< or a comparator (strict weak order)	Hash function + operator==
Memory per element	One node with 3 pointers + color	One node with a next pointer (often a cached hash), plus the bucket array
Iterator invalidation on insert	Never	All iterators if a rehash happens; references stay valid
Iterator invalidation on erase	Only the erased element	Only the erased element

The iterator invalidation rows matter more than they look. With map, you can hold iterators into the container while inserting other keys. With unordered_map, any insert that pushes the size past bucket_count() * max_load_factor() rehashes and invalidates every iterator you hold. Pointers and references to the elements survive, because the nodes themselves don’t move. See iterator invalidation for the full rules.

---

Code Examples

Basic Operations (Identical API)

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

int main() {
    std::map<std::string, int>           ordered;
    std::unordered_map<std::string, int> hashed;

    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

    // Existence checks that do not insert
    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 is sorted, unordered_map is not
    for (const auto& [key, val] : ordered)
        std::cout << "  " << key << ": " << val << '\n';
    // Alice: 95
    // Bob: 82
    // Charlie: 91

    for (const auto& [key, val] : hashed)
        std::cout << "  " << key << ": " << val << '\n';
    // Order unspecified
}

Inserting: operator[], insert, emplace, try_emplace

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

students[101] = "Alice";                 // insert or overwrite
students.insert({102, "Bob"});           // insert only if 102 is absent
students.emplace(103, "Carol");          // construct in place, only if absent
students.try_emplace(104, "Dave");       // C++17: like emplace, but see below
students.insert_or_assign(101, "Alicia");// C++17: explicit upsert, tells you which happened

insert, emplace and try_emplace never overwrite an existing value; they return a pair<iterator, bool> whose bool is false when the key was already present. The difference between the last two is subtle: emplace may construct the value (and possibly move from your arguments) before discovering the key exists, while try_emplace checks first and leaves the arguments untouched if it doesn’t insert. That matters when you pass a std::unique_ptr or a large string you intend to keep using.

Range Query: map Only

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

int main() {
    // Timestamps mapped 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";

    // All events with 150 <= t <= 400
    auto first = events.lower_bound(150);   // first key >= 150
    auto last  = events.upper_bound(400);   // first key > 400

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

Finding the bounds is O(log n), then iterating k results is O(k). With unordered_map the same question needs a full O(n) scan.

Grouping with Sorted Output

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

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);   // creates the vector on first use
    }
    return groups;   // iterates departments alphabetically
}

This is a legitimate use of operator[]’s insert-on-miss behavior, and so is a frequency counter.

Word Frequency with reserve()

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

std::unordered_map<std::string, int> wordCount(const std::vector<std::string>& words) {
    std::unordered_map<std::string, int> counts;
    counts.reserve(words.size());   // upper bound on unique words: no rehash while filling

    for (const auto& w : words)
        ++counts[w];                // missing key starts at 0
    return counts;
}

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

    std::cout << "the: " << freq.at("the") << '\n';   // 3
    std::cout << "cat: " << freq.at("cat") << '\n';   // 2
}

reserve(n) sizes the bucket array for n elements at the current max_load_factor, so filling the map never triggers a rehash (which would re-link every node into a new bucket array). If you want the result sorted by count, copy it into a std::vector<std::pair<std::string, int>> and std::sort that; neither map type can be ordered by value.

---

The operator[] Pitfall

operator[] has a side effect that surprises almost everyone once: if the key doesn’t exist, it inserts a value-initialized element and returns a reference to it.

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

std::cout << ages["Bob"] << '\n';   // prints 0, AND inserts "Bob"
std::cout << ages.size() << '\n';   // 2

In a one-off lookup that’s just a stray entry. In a long-running process it’s a memory leak and a correctness bug at once. A typical shape: a request handler checks if (cache[user_id].empty()) to decide whether to fetch something, and every unknown or malformed user ID now leaves a permanent empty entry behind. The map grows without bound, and code that later iterates over the map to “process all known users” starts processing IDs that never existed.

Consequences that follow from the same rule:

• operator[] does not exist on a const map, because it may need to modify it. If ages[...] fails to compile inside a const member function, that’s why; use at() or find().
• The mapped type must be default-constructible. std::map<std::string, Widget> where Widget has no default constructor can’t use operator[] at all, only insert/emplace/try_emplace.

Lookups that don’t insert:

// find(): returns end() if missing
if (auto it = ages.find("Bob"); it != ages.end()) {
    std::cout << it->second << '\n';
}

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

// contains() (C++20): just a yes/no
if (ages.contains("Bob")) { /* ... */ }

Prefer find() when you need the value afterwards: if (m.contains(k)) use(m.at(k)); does two lookups where one would do.

A related hidden cost: with std::map<std::string, int>, m.find("Bob") constructs a temporary std::string for every call. Declaring the map as std::map<std::string, int, std::less<>> enables heterogeneous lookup, so find can compare against a const char* or std::string_view directly. unordered_map gained the same ability in C++20, but it needs both a transparent hasher and a transparent equality (std::equal_to<>).

---

Erasing During Iteration

Erasing the element an iterator points to invalidates that iterator, so the classic for (auto it = m.begin(); it != m.end(); ++it) if (...) m.erase(it); increments a dead iterator. The correct pattern uses the iterator that erase() returns:

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

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

The same loop works for unordered_map (erase never triggers a rehash, so the other iterators stay valid). Don’t erase from inside a range-for loop; its hidden iterator is the one you just invalidated.

C++20 turns the whole loop into one call:

std::erase_if(scores, [](const auto& kv) { return kv.second < 50; });

---

Custom Key Types

map: Needs a Strict Weak Ordering

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

struct Point {
    int x, y;
    bool operator<(const Point& rhs) const {
        return std::tie(x, y) < std::tie(rhs.x, rhs.y);   // lexicographic
    }
};

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

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

std::tie gets the lexicographic comparison right without hand-written tie-breaking. In C++20 you can also write auto operator<=>(const Point&) const = default;. A comparator that is not a strict weak ordering (for example one using <=, or comparing only x) is undefined behavior: lookups miss elements that are there, and in debug builds MSVC asserts “invalid comparator”.

unordered_map: Needs Hash + Equality

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

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

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t seed = std::hash<int>{}(p.x);
        // boost::hash_combine style mixing
        seed ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

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

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

Passing the hasher as a template argument avoids touching namespace std. Specializing std::hash<Point> is also allowed and makes std::unordered_map<Point, std::string> work without the third argument.

Two things to avoid in hash functions:

• Plain XOR: hash(x) ^ hash(y) maps (1, 2) and (2, 1) to the same value, and every (n, n) to 0.
• hash(y) << 32: shifting a size_t by 32 is undefined behavior on 32-bit platforms, where size_t has 32 bits.

The equality and the hash must agree: if a == b, then hash(a) == hash(b). Forgetting a field in the hash is only slow; including a field in the hash that operator== ignores is a correctness bug, because equal keys land in different buckets.

---

When Collisions Hurt Performance

If many keys hash to the same bucket, every lookup in that bucket becomes a linear scan. With std::string keys and the standard hash that is rare by accident, but two situations cause it in practice:

• A weak custom hash, like the XOR example above, on structured keys.
• Adversarial input. In libstdc++ and libc++, std::hash<int> is the identity function, and the bucket index is the hash modulo the bucket count. If untrusted input chooses integer keys, it’s easy to pick keys that are all multiples of the bucket count and pile them into one bucket. Services that key hash maps by user-controlled values should use a randomized or keyed hash for those maps, or a std::map.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    for (int i = 0; i < 1000; ++i) m[i] = i;

    std::cout << "buckets: "     << m.bucket_count()    << '\n';
    std::cout << "load_factor: " << m.load_factor()     << '\n';   // size / bucket_count
    std::cout << "max: "         << m.max_load_factor() << '\n';   // default 1.0
    std::cout << "bucket of 42 holds " << m.bucket_size(m.bucket(42)) << " entries\n";
}

bucket_size() on a few hot keys is the quickest way to confirm a clustering problem. Lowering max_load_factor (for example to 0.7) trades memory for shorter chains, but it doesn’t help if the hash itself is clustering keys.

---

Performance in Practice

For large maps and lookup-heavy workloads, unordered_map is usually several times faster than map. But both are node-based: every element is a separate heap allocation, and walking either structure means chasing pointers across memory. That has two practical consequences:

• For small n, the difference disappears. For a few dozen elements, a sorted std::vector with std::lower_bound, or even a linear scan, often beats both because it fits in a couple of cache lines.
• String keys add their own cost. map compares strings character by character at each of its ~log2(n) levels, while unordered_map hashes the whole key once and then compares it with the keys in one bucket.

When lookup speed really matters, open-addressing hash maps outside the standard library (such as absl::flat_hash_map or boost::unordered_flat_map) are typically faster than std::unordered_map, because they store elements contiguously instead of in separate nodes. Measure with your real keys and access pattern before switching.

---

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 cheaply?
  Yes → std::map (begin() / rbegin())

Must you keep iterators valid across inserts?
  Yes → std::map

Are keys controlled by untrusted input, with worst-case latency important?
  Yes → std::map, or a hash map with a keyed hash

Otherwise:
  → std::unordered_map
  → reserve() if you know the size up front

Use Case	Container
Word frequency counter	unordered_map
Configuration key-value store	unordered_map (or map if you print it sorted)
Time-series events with range queries	map
Leaderboard (sorted by score)	std::multimap keyed by score, or a sorted vector
LRU cache	unordered_map + std::list
Index for range queries	map

---

map or unordered_map: the rules that matter

• unordered_map: average O(1), no ordering, O(n) worst case with a bad or attacked hash. The right default for lookups.
• map: O(log n) guaranteed, sorted iteration, range queries, stable iterators.
• operator[] inserts on a miss; use find(), at() or contains() to read.
• Erase while iterating with it = m.erase(it), or std::erase_if in C++20.
• reserve(n) before filling an unordered_map with n entries.
• Custom keys: map needs a strict weak ordering; unordered_map needs a hash and operator== that agree.

---

Related Articles

• Hash Table data structure
• C++ set vs unordered_set
• C++ iterator invalidation
• C++ STL vector