C++ unordered_map: Fast Hash Map Lookup Explained

When Order Doesn't Matter

You just saw std::map, which keeps its keys sorted using a balanced tree and gives you O(log n) operations. But sorting costs something, and a lot of the time you don't care what order the keys come out in - you just want to ask "is this key here, and what's its value?" as fast as possible.

That's what std::unordered_map is for. It's a hash table: it runs each key through a hash function to decide where to store it, which makes insert, lookup, and erase average O(1) instead of O(log n). The trade-off is that iteration order is unspecified - the keys come out in whatever order the buckets happen to hold them.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

The interface is almost identical to map on purpose - you can often swap one for the other by changing the type. Include <unordered_map> (not <map>), and the keys come out unsorted.

Inserting and Updating

There are a few ways to put entries in, and they don't all behave the same. The two you'll use most are operator[] and insert:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // create or overwrite
    votes["alice"] = 5;              // overwrites -> 5
    votes.insert({"bob", 2});        // inserts only if "bob" is absent
    votes.insert({"bob", 99});       // ignored, "bob" already exists

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, not 99
}

The key difference: operator[] overwrites an existing value, while insert leaves an existing key untouched. If you're on C++17, insert_or_assign(key, value) gives you "set this no matter what" semantics, and try_emplace(key, args...) constructs the value in place only when the key is new - handy for expensive-to-build values.

The operator[] Gotcha: It Inserts on Read

This is the single most common unordered_map bug, so it gets its own section. m[key] is not a pure read. If the key is missing, it default-constructs and inserts it (an int becomes 0, a string becomes ""), then returns a reference. So code that looks like a lookup quietly grows the map:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // We only meant to CHECK for "y", but [] inserted it:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, not 1!
}

seen["y"] created a "y" -> 0 entry just by being mentioned. To test membership without mutating the map, use count (returns 0 or 1) or find:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() reads cleaner than count()
    if (seen.contains("x")) cout << "x is here\n";
}

Rule of thumb: use [] only when you intend to create-or-update. For pure reads, use count, contains (C++20), or find.

find and at: Safe Lookups

find returns an iterator to the entry, or end() if the key is absent. It never inserts, and it lets you reach both the key and value through it->first and it->second in one lookup:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

When you know the key should exist and want a hard failure if it doesn't, use at. Unlike [], at does not insert - it throws std::out_of_range for a missing key:

int p = prices.at("pen");   // fine
int q = prices.at("hat");   // throws std::out_of_range - key absent

So you have three lookup styles: [] (inserts), at (throws), and find/count (report presence without touching the map). Pick the one whose failure mode matches your intent.

Iterating and Erasing

A range-based for loop with structured bindings is the clean way to walk every entry. Remember the order is arbitrary - never rely on it:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // order is unspecified
    }
}

To remove an entry, erase takes a key directly and returns how many were removed (0 or 1). One important gotcha: erasing while iterating invalidates only the erased element's iterator in an unordered_map, so use the return value of erase(it) to advance safely:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Drop every team with a score below 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase returns the next valid iterator
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Writing wins.erase(it++) style or ++it after a plain erase(it) is the classic dangling-iterator trap - the erased iterator is dead, so always take erase's returned iterator.

map or unordered_map?

Both store key-value pairs with a similar API, so the choice comes down to what you need:

// std::map            -> sorted keys, O(log n), range queries (lower_bound)
// std::unordered_map  -> no order,    O(1) avg, fastest plain lookup

Reach for unordered_map when you just need fast lookup by key and order is irrelevant (counting word frequencies, caching, deduplication). Choose map when you need keys in sorted order, want to iterate in order, or do range queries. Two caveats for unordered_map: its O(1) is an average - a bad hash can degrade it - and a custom key type needs a hash specialization or a hash functor, whereas map only needs operator<.

Next: Set

You've now seen both flavors of key-value container. Sometimes, though, you don't need a value at all - you only care whether something is present, like a collection of unique tags or visited IDs. Next we'll look at std::set (and its hash-based cousin unordered_set), which store just keys and automatically keep them unique.