std::map vs std::unordered_map in C++: Choosing the Right Associative Container

By the end of this page, you will know that std::unordered_map is not a universal replacement for std::map. You will be able to choose between them based on ordering needs, complexity guarantees, range queries, iteration behavior, memory, key requirements, and practical performance.

std::map and std::unordered_map are both associative containers: they store values by unique keys.

The main difference is how they organize data:

• std::map is usually implemented as a balanced search tree. Its keys are kept in sorted order according to a comparison function, normally std::less<Key>.
• std::unordered_map is a hash table. A hash function assigns each key to a bucket, and elements are not stored in sorted key order.

This leads to different complexity guarantees:

Average O(1) is often excellent, especially for direct key lookups. But it is not the only property that matters. A map can be the correct choice when sorted traversal, range operations, predictable worst-case performance, stable iteration behavior, or a comparison-only key type is more valuable than average lookup speed.

Also, asymptotic notation describes growth as n becomes large; it does not promise that one container is faster in every real workload. Hashing strings, allocating buckets, cache behavior, collisions, and the mix of operations all affect measured performance.

Think of std::map as a carefully alphabetized filing cabinet.

• You can find a file by repeatedly choosing the correct half of the cabinet.
• Files are always in alphabetical order.
• You can easily ask for every file from "m" through "r".

Think of std::unordered_map as a set of labeled bins.

• A machine hashes a key and tells you which bin to inspect.
• Finding one known key is usually very quick.
• The bins are not alphabetized, so asking for keys between two values has no useful meaning.
• If many keys land in the same bin, looking through that bin becomes slower.

Use the alphabetized cabinet when order and predictable behavior matter. Use bins when fast direct lookup is the main job.

Both containers have similar basic APIs, including find, contains (C++20), insert, erase, operator[], and at.

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

int main() {
    std::map<int, std::string> ordered{
        {30, "thirty"},
        {10, "ten"},
        {20, "twenty"}
    };

    std::unordered_map<int, std::string> hashed{
        {30, "thirty"},
        {10, "ten"},
        {20, "twenty"}
    };

    std::cout << "map: ";
    for (const auto& [key, value] : ordered) {
        std::cout << key << ' ';
    }
    std::cout << "\n";

    std::cout << "unordered_map: ";
    for (const auto& [key, value] : hashed) {
        std::cout << key << ' ';
    }
    std::cout << "\n";
}

The map loop always prints keys in ascending order:

map: 10 20 30

The unordered_map loop can print keys in any order. You must not write code that depends on its observed iteration order.

A major map feature is ordered searching:

std::map<int, std::string> scores{
    {10, "bronze"},
    {50, "silver"},
    {100, "gold"}
};

auto it = scores.lower_bound(50); // First key that is >= 50.
if (it != scores.end()) {
    std::cout << it->first << ": " << it->second << '\n';
}

std::unordered_map cannot provide lower_bound by key because its keys are not ordered.

Consider a lookup followed by a range query:

#include <map>
#include <iostream>

int main() {
    std::map<int, char> grades{{70, 'C'}, {80, 'B'}, {90, 'A'}};

    auto exact = grades.find(80);
    auto passing = grades.lower_bound(60);

    std::cout << exact->second << '\n';

    for (auto it = passing; it != grades.end(); ++it) {
        std::cout << it->first << ": " << it->second << '\n';
    }
}

Execution:

1. grades stores the pairs ordered by key: 70, 80, then 90.
2. find(80) navigates the tree to find the element whose key is exactly 80.
3. exact->second is 'B', so the first line prints B.
4. lower_bound(60) returns the first element with a key not less than 60. That is the key 70.
5. Incrementing a map iterator moves to the next greater key.
6. The loop prints all entries with keys at least 60:

70: C
80: B
90: A

With unordered_map, find(80) is available, but step 4 has no equivalent ordered operation. You would need to inspect every element and filter keys manually.

Choose std::map when sorted keys are part of the requirement:

• Time-based events: Store events by timestamp and retrieve the next event at or after a given time with lower_bound.
• Price levels in a trading or booking system: Iterate prices from lowest to highest, or find the first price meeting a threshold.
• Prefix-like and interval-like key processing: With sorted strings, iterate from a lower boundary to an upper boundary. For example, process names beginning with a prefix by finding a starting point and stopping when the prefix no longer matches.
• Deterministic reports and serialized output: Iterate records in a defined key order without separately sorting keys.
• Untrusted input or latency-sensitive paths: Prefer the logarithmic worst-case bound when a hash table's collision behavior is unacceptable.
• Keys without a sensible hash: A custom type only needs a strict ordering for std::map; it needs a correct hash function and equality relation for std::unordered_map.

Choose std::unordered_map when the work is mainly exact lookup by key:

• Caches keyed by IDs or strings.
• Counting frequencies in input data.
• Looking up configuration entries by name.
• Indexing objects by database ID.
• Fast membership tests such as seen.contains(userId) in C++20.

In real code, container choice follows the operations the code must perform, not just the lookup complexity shown in a table.

Exact lookup with an unordered map

A cache commonly needs only direct access by ID:

std::unordered_map<int, User> usersById;

const User* findUser(const std::unordered_map<int, User>& users, int id) {
    auto it = users.find(id);
    if (it == users.end()) {
        return nullptr; // Guard clause for a missing user.
    }
    return &it->second;
}

Ordered range processing with a map

A scheduler can use lower_bound to avoid scanning old events:

std::map<int, Task> tasksByTime;

void runTasksFrom(std::map<int, Task>& tasks, int currentTime) {
    for (auto it = tasks.lower_bound(currentTime); it != tasks.end(); ++it) {
        it->second.run();
    }
}

Reserving an unordered map

If you know approximately how many elements will be inserted, reserve space. This can reduce costly rehashes and iterator invalidation during insertion.

std::unordered_map<std::string, int> counts;
counts.reserve(10'000);

for (const std::string& word : words) {
    ++counts[word];
}

Separating lookup from presentation

A frequent pattern is to use an unordered_map for fast lookup, then sort only when output is needed:

std::vector<std::pair<std::string, int>> entries(counts.begin(), counts.end());
std::sort(entries.begin(), entries.end());

This is often better than maintaining sorted order continuously if sorted output is rare. Conversely, if range queries or ordered traversal are central to the program, std::map keeps that order available all the time.

Assuming unordered_map iteration is stable or sorted

This code is incorrect if it expects ascending IDs:

std::unordered_map<int, std::string> names;
// ... insert values ...

for (const auto& [id, name] : names) {
    // Incorrect assumption: id increases on every iteration.
}

Use std::map, or copy entries to a vector and sort them before ordered processing.

Treating average O(1) as guaranteed O(1)

unordered_map can have collisions. Its worst-case lookup, insertion, and erase by key are linear in the number of elements. Do not use it solely because it has a better average-case Big-O label.

Using operator[] only to check whether a key exists

operator[] inserts a missing key with a default value:

std::unordered_map<std::string, int> visits;

if (visits["alice"] == 0) { // Inserts "alice" when it was absent.
    // ...
}

Use find or contains when you do not want insertion:

if (!visits.contains("alice")) {
    // No insertion occurred.
}

Keeping unordered-map iterators across a rehash

Insertion can cause an unordered_map to rehash, which invalidates its iterators. Do not save an iterator and assume it remains valid after arbitrary inserts. Call reserve when a known insertion batch is coming, or reacquire the iterator.

Forgetting the hash and equality contract

For an unordered_map, equivalent keys must produce the same hash value. If custom KeyEqual considers two keys equal but the hash function returns different values for them, lookups can fail in surprising ways.

Assuming a map is always more memory-efficient

There is no universal answer. Tree nodes often have pointer and allocation overhead; hash tables have a bucket array plus stored nodes or elements. Measure with your implementation, key/value types, load factor, and expected size.

Choosing based only on element count

A container with more than 1,024 elements is not automatically an unordered_map use case. A thousand elements with frequent range queries strongly favors map; millions of exact integer-ID lookups often favor unordered_map. Benchmark representative workloads when performance matters.

std::map versus sorting a vector

For mostly-read data that changes rarely, a sorted std::vector<std::pair<Key, Value>> can also be worth considering. It offers compact contiguous storage and binary search, but inserting in the middle costs O(n). map is more suitable when you need ongoing inserts and erases while keeping keys ordered.

std::unordered_map versus std::map for strings

Hashing a long std::string generally examines its characters. Tree comparisons may also examine characters, potentially multiple times while navigating the tree. Which is faster depends on string lengths, prefixes, data distribution, allocator behavior, and the operation mix. Profile rather than guessing.

• Use std::unordered_map<Key, Value> for mostly exact lookups when average-case speed is the priority.
• Use std::map<Key, Value> when you need keys sorted.
• map::find(key): guaranteed O(log n).
• unordered_map::find(key): average O(1), worst O(n).
• map::lower_bound(key): first key >= key.
• unordered_map has no key-order range query.
• Do not rely on unordered_map iteration order.
• Use find or C++20 contains to test presence without insertion.
• operator[] inserts a default value if the key is missing.
• Before bulk inserts into an unordered map, consider:

items.reserve(expectedCount);

• An unordered-map rehash invalidates iterators; map insertion does not invalidate existing iterators.
• For custom unordered keys: if a == b, then hash(a) == hash(b) must be true.
• For custom map keys: the comparator must define a consistent strict weak ordering.
• Benchmark with representative keys and operations when the choice is performance-critical.

Is std::unordered_map always faster than std::map?

No. It often has faster average exact lookup, but hashing, collisions, memory layout, allocations, and workload details matter. map also wins when sorted traversal or range searches avoid extra work.

Why would I use std::map if I do not currently need sorted output?

Use it if you need ordered operations such as lower_bound, threshold searches, or interval traversal. It can also be appropriate when predictable logarithmic worst-case behavior matters.

Does std::unordered_map preserve insertion order?

No. Its iteration order is unspecified and may change after a rehash. Use another container if insertion order is a requirement.

Can I get sorted output from an unordered_map?

Yes. Copy its entries into a vector and sort the vector. This is often a good design when ordered output is occasional rather than constant.

Should I call reserve on every unordered_map?

Not necessarily, but call it before a large insertion batch when you can estimate the number of elements. It can reduce rehashing and allocations.

Are std::map iterators invalidated when I insert another element?

Existing std::map iterators and references remain valid after insertion. Erasing an element invalidates iterators and references to that erased element only.

Can I use a custom class as the key in both containers?

Yes. std::map needs a valid ordering comparator. std::unordered_map needs a hash function and an equality comparison that agree with each other.

Is std::map safer against hash-collision attacks?

A map's logarithmic lookup bound does not depend on hash distribution, while an unordered map can degrade with many collisions. This can matter when keys originate from untrusted input or predictable latency is important.

• Associative containers — The broader C++ category containing maps and sets.
• std::set and std::unordered_set — The same ordered-versus-hashed trade-off without mapped values.
• Hash functions — Required for correct and efficient std::unordered_map keys.
• Equality comparison — Must agree with hashing for unordered containers.
• Strict weak ordering — The comparison rule required by std::map.
• Big-O complexity — Explains average, worst-case, and logarithmic complexity claims.
• Iterator invalidation — Important when modifying containers while holding iterators.
• lower_bound and upper_bound — Ordered-search operations that make std::map useful.
• std::vector and std::sort — A practical alternative for rarely changing data that only occasionally needs sorted output.
• Benchmarking and profiling — Necessary when actual performance determines the container choice.