std::map<Key, Value> is the standard library's sorted associative container of key-value pairs. It uses the same balanced binary search tree as std::set (red-black tree in every mainstream implementation), but each node stores a std::pair<const Key, Value> instead of just a key. std::multimap<Key, Value> is the variant that lets multiple values share a key. This chapter covers the data layout, the insertion and access APIs, the famous operator[] gotcha, structured-binding iteration, and multimap differences.

A std::map<Key, Value> is a red-black tree whose nodes carry a pair: the key, which the tree uses for ordering, and a value that travels with it. The key is const inside the pair, so once an entry is in the map, the key can't be mutated (changing it would break the tree's sorted invariant), but the value can be modified freely.

Iteration walks keys in sorted order, which is the defining property carried over from std::set. The element type is std::pair<const std::string, double>; entry.first is the key, entry.second is the value.

The diagram below shows the rough shape of a node and how a few entries hang off the tree.

Each node holds the key, the value, three pointers (parent, left child, right child) and a color bit for rebalancing. The tree is ordered by key alone; the value never influences the structure. That's why two different values can never share a key in a std::map. For that case, use std::multimap.

Insert, erase, find, operator[], and at are all O(log n). Each operation walks log-n tree nodes, and each node is a separate heap allocation, so the constant factor is meaningfully higher than for a std::vector or a hash-based map.

insert takes a std::pair<Key, Value> and returns the same std::pair<iterator, bool> pattern seen with std::set: an iterator to the entry and a bool saying whether the insert happened. The insert is a no-op if the key already exists, leaving the existing value untouched.

The second insert fails because "Mug" is already there, and the returned iterator still points at the original entry with value 12. The 999 is discarded. This is the right behavior for "insert only if absent", but it surprises callers expecting "set or overwrite." For the overwrite case, C++17 added insert_or_assign.

insert_or_assign writes the value either way. The bool reports whether a new entry was created (true) or an existing one was overwritten (false).

emplace constructs the pair in place from the arguments passed.

C++17 added try_emplace, which is emplace with one important fix: if the key already exists, the arguments for constructing the value are not consumed. With plain emplace, the arguments are forwarded to the pair's constructor before the duplicate-key check, so any move-only value gets moved-from even when the insert fails. try_emplace avoids that.

With try_emplace, the second unique_ptr was never moved-from because the insert was rejected. If this had been plain emplace, the unique_ptr would have been moved into a temporary pair that was then thrown away, and note would be empty afterward. try_emplace is the safer default any time the value type is move-only or expensive to construct.

All three are O(log n). try_emplace and insert_or_assign skip a temporary construction when the key is already present, which can matter for expensive value types.

std::map has an operator[] that looks like array indexing. It behaves like indexing with one major twist: if the key doesn't exist, operator[] inserts a new entry with a default-constructed value, then returns a reference to that value. It never fails or throws; the only way to read it is to insert it.

Read it carefully. Asking the map about "Phone" added "Phone" -> 0 to the map, even though nothing was "written". The size jumped from 2 to 3 from the read. This is a frequent source of bugs in code that uses operator[] for lookups in a "read-only" context.

Two correct ways to handle this. To ask "does this key exist?" use find, contains (C++20), or count.

To read with an exception when the key is missing, use at.

at throws std::out_of_range when the key is missing. It's strict about reads, which is what's wanted when "missing key" is genuinely an error. at also has a const overload, so it works on const std::map<> references; operator[] does not, because it might insert.

operator[] is good for two specific patterns: writing a value unconditionally, and "get-or-default" reads where the default-inserted value is the desired behavior (counting word frequencies, accumulating totals, and similar).

For the counting case, the default-insertion is the feature. The first time a product appears, reviewCounts[product] inserts a 0, then ++ makes it 1. Subsequent encounters increment the existing counter. Without operator[], this would be three lines (find, check, insert-or-update) instead of one.

operator[] is O(log n) like find, but with one extra side effect on a miss: it allocates a new tree node. For membership checks in a hot loop where the key often doesn't exist, find is cheaper because it skips the allocation.

These mirror std::set's API, returning iterators to pairs instead of single keys. find(key) returns an iterator (or end()), count(key) returns 0 or 1, and C++20's contains(key) returns a bool.

The iterator returned by find points at a std::pair, so ->first and ->second (or (*it).first after dereferencing) access the key and value.

The four lookups have slightly different shapes and all appear in regular use. The recommendation:

count(k) works for membership but reads a bit awkwardly; prefer contains or find for that intent.

The natural way to iterate a map in modern C++ is with a structured binding, which was added in C++17. It splits each pair into named variables right in the loop header.

That's the canonical form. Compare it to the C++11/14 spelling:

The structured-binding version reads better because the names are meaningful at the use site. To mutate values, drop the const and use auto& instead of const auto&.

The key inside the binding (item here) is still const because the pair's first element is const Key. Writing item = "something else" is rejected by the compiler even with a non-const reference. Only the value half is mutable.

Iteration is O(n). Each step is a tree-successor operation, which is amortized O(1) but involves a pointer chase per node, so the constant factor is higher than for a contiguous container.

erase works the same way as on std::set. Erasing can be done by key, by iterator, or by iterator range.

Erasing by key returns the number of elements removed (0 or 1 for std::map). Erasing by iterator returns an iterator to the next element, which is what's needed when removing inside a loop:

This is the safe pattern. Writing stock.erase(it++) instead of it = stock.erase(it) is a classic bug; it happens to work on a std::map because erase doesn't invalidate the next iterator, but the assigned form is clearer and works for every container.

Like std::set, inserts and erases on a std::map never invalidate iterators to other entries. The tree's nodes don't move when the tree rebalances; only the parent/child pointers shift around.

The same lower_bound, upper_bound, and equal_range from std::set are here too, and they work the same way on the key. The iterators come back pointing at pairs.

The lookup is two O(log n) calls and the walk is O(k) where k is the size of the range. This is the operation that distinguishes std::map from std::unordered_map. An unordered map can answer "give me the entry for key K" in average O(1), but it can't answer "give me every entry with a key between A and B" in less than O(n).

The comparator works exactly like it did on std::set. The default is std::less<Key>, which uses operator< on the key type. Supply a different functor to change the ordering.

For custom comparison logic, use a struct with operator() (or a lambda, with the same decltype pattern).

The second assignment hits the existing "Mug" entry (case-insensitive equality) and overwrites the value. The same rules apply as on std::set: the comparator must implement strict weak ordering (use <, never <=), and equality is implied by !comp(a, b) && !comp(b, a).

std::multimap<Key, Value> allows multiple entries with the same key. The classic use case is a one-to-many relationship: customer ID to orders, product to reviews, tag to articles, anything where one key naturally maps to several values.

Entries with the same key stay grouped together in iteration order (because the underlying tree is ordered by key). On libstdc++ and libc++, the order of values within a single key is insertion order; the C++ standard since C++11 requires it, so insertion order can be relied on within a key.

The big API difference: `multimap` has no `operator[]`. The point of operator[] is "return the value for this key," and that doesn't have a meaningful answer when several values could match. The same goes for at. To look up all values for a key, use equal_range.

equal_range(key) returns a half-open iterator range covering every entry with that key. count(key) works the same way, returning the actual number of matches.

insert on a multimap returns just an iterator (not a pair<iterator, bool>), because the insert always succeeds. There's no failure case to report.

erase(key) on a multimap removes every entry with that key and returns the count, just like multiset.

To remove one occurrence, find it first and erase by iterator: auto it = reviews.find("Mouse"); reviews.erase(it); removes only the first match.

The same picking rule between ordered and hash-based containers applies, with values added. std::unordered_map is the hash-based variant. The short version:

std::unordered_map gives average O(1) for insert, erase, and lookup. std::map gives guaranteed O(log n) plus the ordered-view operations. For a pure dictionary use case (lookups dominate, no order matters), unordered_map is the better default; for anything that needs key order, range queries, or stable iteration, map is the better fit.

A small comparison program puts the difference on display.

Compile with g++ -std=c++20 file.cpp. The contains call needs C++20; everything else works back to C++17 (with the small adjustment that try_emplace is C++17 too). Every operation here uses something map is good at: ordered iteration, range queries, and stable behavior on insert/erase.