C++ STL: map vs unordered_map — Key Differences and How to Choose

For a long time I used std::map and std::unordered_map interchangeably, and honestly I couldn't tell you why I picked one over the other. When I finally sat down and learned how they work under the hood — a red-black tree vs a hash table — choosing became obvious. This is the note I wish I had when I started.

TL;DR: need keys in sorted order or range queries → std::map. Just fast lookups → std::unordered_map. The rest of this post explains why.

1. Overview

std::map and std::unordered_map are containers used to store {key, value} pairs, and provide efficient insert, search, and delete operations.

The key difference: std::map keeps its elements sorted by key, while std::unordered_map makes no guarantee about order.

Compare std::map and std::unordered_map

	map	unordered_map
Time complexity	O(log N)	Average O(1), worst O(N)
Ordering	sorted by key	no guaranteed order
Underlying implementation	Red-black tree	Hash table
Key requirements	must support < (or a custom comparator)	must support == and be hashable

How to choose

• Use map when you need to traverse in key order, do range queries (lower_bound/upper_bound), or when the key type doesn't have a good hash function.
• Use unordered_map if you just need point lookups, frequent inserts, a large number of elements, and the hash distribution is uniform.

2. Space complexity

std::unordered_map spends extra memory on its bucket array, and it keeps the table less than fully packed (that's the load factor at work), so it typically uses more memory than std::map. As you insert more elements, the table rehashes and the bucket array keeps growing.

3. Requirements on the key

std::map stores its elements in a red-black tree, which requires comparing keys with <. The standard library uses operator< by default, but you can provide a custom comparator instead.

For example — Person as a key of std::map, with a custom comparator:

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

struct Person {
    std::string name;
    int age;

    friend std::ostream& operator<<(std::ostream& os, const Person& p) {
        return os << "(" << p.name << ", " << p.age << ")";
    }
};

struct PersonCompare {
    bool operator()(const Person& lhs, const Person& rhs) const {
        if (lhs.age != rhs.age) { return lhs.age < rhs.age; }
        return lhs.name < rhs.name;
    }
};

int main() {
    std::map<Person, std::string, PersonCompare> myMap;
    myMap[{"Alice", 25}]   = "Engineer";
    myMap[{"Bob", 20}]     = "Student";
    myMap[{"Charlie", 25}] = "Designer";

    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }
    return 0;
}

Run it and notice: the output is strictly sorted by (age, name) — that's the red-black tree at work.

std::unordered_map needs a hash function to decide which bucket each key goes into. Because different keys can end up with the same hash (a collision), it also needs == to tell keys apart.

And the same Person as a key of std::unordered_map — note the two extra template parameters (hash + equality) instead of one comparator:

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

struct Person {
    std::string name;
    int age;

    friend std::ostream& operator<<(std::ostream& os, const Person& p) {
        return os << "(" << p.name << ", " << p.age << ")";
    }
};

struct PersonHash {
    std::size_t operator()(const Person& p) const noexcept {
        return std::hash<std::string>{}(p.name) ^ (std::hash<int>{}(p.age) << 1);
    }
};

struct PersonEqual {
    bool operator()(const Person& lhs, const Person& rhs) const noexcept {
        return lhs.age == rhs.age && lhs.name == rhs.name;
    }
};

int main() {
    std::unordered_map<Person, std::string, PersonHash, PersonEqual> myMap;
    myMap[{"Alice", 25}]   = "Engineer";
    myMap[{"Bob", 20}]     = "Student";
    myMap[{"Charlie", 25}] = "Designer";

    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }
    return 0;
}

Run this one too: the output order will be different — and not sorted. That single difference in output is the "Ordering" row of the table above, live.

Two details worth noticing:

1. std::hash<std::string>{}(p.name) ^ (std::hash<int>{}(p.age) << 1) combines the two field hashes with XOR; the << 1 shift keeps (name, age) pairs from hashing symmetrically.
2. PersonEqual exists because of collisions: two different Persons can land in the same bucket, and == is what tells them apart — exactly the chaining mechanism in the Q&A below.

4. Q&A

Q: How does unordered_map deal with hash collisions?
A: C++ STL uses chaining — elements in the same bucket are linked into a list. When inserting, you attach to the end of the chain; when searching, you first use the hash to find the bucket, then traverse the list comparing keys. The more collisions there are, the longer the chain, and the worse the performance.

Q: Why is the worst case O(n)?
A: In the extreme case where all keys hash to the same bucket, the whole table degenerates into a linked list, and searching turns into a linear scan.

Reference

• std::map - cppreference.com
• std::unordered_map - cppreference.com