std::map and std::unordered_map

The problem maps solve

Suppose you want to store phone numbers for a list of contacts. You could keep two parallel vectors — one for names, one for numbers — but then looking up a number by name requires scanning the whole name vector. Worse, nothing prevents the two vectors from getting out of sync. A map bundles each key with its value in a single structure and does the searching for you efficiently:

#include <map>
#include <string>

std::map<std::string, unsigned long long> phone_book;

// Insert entries through operator[]:
phone_book["Joe"]     = 202'456'1111;
phone_book["Jill"]    = 202'456'1111;
phone_book["Francis"] = 39'06'6982;
phone_book["Charles"] = 44'020'7930'4832;

// Retrieve a value by key — no index arithmetic required:
std::println("Francis: {}", phone_book["Francis"]);  // 39066982

The map template takes two type arguments: map<Key, Value>. Keys must be unique — you cannot store two different phone numbers under the same name. The map owns both the key and the value together, so they can never get out of sync.

How operator[] works — and its hidden trap

The subscript operator on a map works differently from a vector. If the key already exists, it returns a reference to the existing value — you can read it or overwrite it. If the key does not exist, operator[] silently inserts a brand-new key–value pair, with the value zero-initialized (0 for numeric types, "" for strings), and returns a reference to that freshly inserted zero. This insertion-on-read is intentional — it enables the elegant word-counting pattern you will see shortly — but it can also bite you:

// Phone book has only Joe, Jill, Francis, Charles.
// Reading a missing key INSERTS it with value 0:
unsigned long long n = phone_book["Alice"];  // n == 0
//  ^ side effect: phone_book now contains "Alice" → 0

// Checking phone_book.size() reveals the insertion happened:
std::println("{}", phone_book.size());  // 5, not 4

// To check without inserting, use find() or contains() instead (see below).

Because of this insertion side effect, you should never use operator[] on a const map — the compiler won't allow it. When you want to check whether a key exists before reading, always prefer find() or contains().

Counting words — the operator[] sweet spot

The insertion-on-read behaviour is not a bug; it is a feature when your intent is exactly to start counting from zero. The canonical example is word counting: for each word in a text, increment the counter associated with that word. If the word has never been seen, you want to start at 1; if it has, you want to add 1 to the existing count. One line does both:

using WordCounts = std::map<std::string_view, std::size_t>;

WordCounts count_words(const std::vector<std::string_view>& words)
{
    WordCounts result;
    for (const auto& word : words)
        ++result[word];   // inserts 0 if new, then increments to 1
                          // increments existing count if already there
    return result;
}

// For "the quick brown fox jumped over the lazy dog the":
// "brown"→1  "dog"→1  "fox"→1  "jumped"→1  "lazy"→1
// "over"→1   "quick"→1  "the"→3

When the map has never seen the word, result[word] inserts a size_t with value 0 and returns a reference to it; ++ brings it to 1. On subsequent encounters the reference points to the existing count, which is then incremented. No if statement needed.

Elements are key–value pairs

Internally, each element stored in a map is a std::pair<const Key, Value>. The key is const because changing a key mid-flight would break the map's sorted order. You access the two parts through .first (the key) and .second (the value), or more elegantly through C++17 structured bindings:

// Verbose: .first and .second
for (const auto& element : phone_book)
    std::println("{} → {}", element.first, element.second);

// Clean: structured bindings (C++17+) — preferred
for (const auto& [name, number] : phone_book)
    std::println("{} → {}", name, number);

// Output (notice alphabetical order — std::map always sorts by key):
// Charles → 4402079304832
// Francis → 39066982
// Jill    → 2024561111
// Joe     → 2024561111

Because std::map is backed by a balanced binary tree, it keeps all entries sorted by key at all times. Iteration always yields elements in ascending key order — alphabetical for strings, numeric for numbers — with no extra sorting step required.

Safe lookup with find() and contains()

To check whether a key exists without accidentally inserting it, use contains() (C++20, returns a bool) or find() (returns an iterator). Because the map knows its own internal structure, these member functions are logarithmically fast — far faster than scanning with a generic algorithm. Always prefer them over std::find() from <algorithm>:

// contains() — simplest check, C++20
if (phone_book.contains("Francis"))
    std::println("Francis is in the book");

// find() — returns iterator; use when you also want the value
auto it = phone_book.find("Francis");
if (it != phone_book.end()) {
    // it->first  == "Francis"
    // it->second == 39066982
    const auto& [name, number] = *it;   // structured binding on dereferenced iterator
    std::println("{}: {}", name, number);
}

// Wrong — operator[] inserts "Unknown" with value 0 if missing:
// if (phone_book["Unknown"] == 0) { ... }  ← don't do this

// Correct — find() never inserts:
if (phone_book.find("Unknown") == phone_book.end())
    std::println("Unknown is not in the book");

The pattern it != map.end() is the standard idiom: if find() returns end(), the key was not found. If it returns anything else, dereference the iterator to get the key–value pair.

Inserting and erasing elements

Besides operator[], you can insert entries with insert() or the more modern emplace(). Unlike sequence containers, maps do not let you specify where to insert — they determine the position automatically from the key. Removing entries uses erase(), which accepts either a key directly or an iterator:

// Erase by key — does nothing if key not present:
phone_book.erase("Joe");

// Erase by iterator — useful when you already have an iterator from find():
auto it = phone_book.find("Jill");
if (it != phone_book.end())
    phone_book.erase(it);

// insert() does NOT overwrite an existing key:
auto [iter, inserted] = phone_book.insert({"Charles", 999});
// inserted == false — Charles already existed, value unchanged

// operator[] DOES overwrite:
phone_book["Charles"] = 999;  // replaces existing value

// Clear everything:
phone_book.clear();
std::println("{}", phone_book.empty());  // true

The difference between insert() and operator[] matters: insert leaves an existing entry untouched and tells you whether the insertion succeeded, while operator[] silently overwrites. Use insert()when you want “add only if not present” semantics.

std::unordered_map — when order does not matter

std::unordered_map<Key, Value> is a drop-in replacement for std::map with one key difference: it is backed by a hash table instead of a balanced tree. Hash tables store entries in buckets indexed by a hash of the key, which means lookup, insertion, and deletion all run in near-constant time on average — far faster than the logarithmic time of an ordered map for large collections. The trade-off is that iterating over an unordered_map yields elements in an unspecified, unpredictable order:

#include <unordered_map>

// Same API as std::map — just swap the type name:
std::unordered_map<std::string, unsigned long long> phone_book;
phone_book["Joe"]     = 202'456'1111;
phone_book["Francis"] = 39'06'6982;

// find(), contains(), erase(), operator[] — all work identically
if (phone_book.contains("Francis"))
    std::println("Francis: {}", phone_book["Francis"]);

// Iteration: same structured bindings, but ORDER IS NOT DEFINED
for (const auto& [name, number] : phone_book)
    std::println("{} → {}", name, number);
// Might print Francis before Joe, or Joe before Francis — no guarantee

// Average-case complexity comparison:
// std::map         : O(log n) lookup, O(log n) insert, O(log n) erase
// std::unordered_map: O(1)     lookup, O(1)     insert, O(1)     erase

For most built-in key types — std::string, integers, pointers — the standard library provides a hash function automatically. For custom class types you would need to provide one yourself.

In practice, unless you have profiled your program and identified map lookups as a bottleneck, start with std::map. Its deterministic ordering makes debugging and testing significantly easier, and logarithmic time is fast enough for the vast majority of applications.

Key rules to remember