std::multimap<Key, Value> is the standard library's sorted associative container of key-value pairs, with the uniqueness rule dropped. Multiple entries can share the same key, which makes it useful for one-to-many relationships: a customer to many orders, a product to many reviews, an author to many books. It uses the same red-black tree as std::map, so every key-touching operation is O(log n), and iteration walks entries in key-sorted order. This chapter covers what changes once duplicate keys are allowed, why operator[] and at are gone, how to access values for a given key, and the workloads where multimap fits well.

A std::multimap is structurally identical to a std::map: each tree node holds a std::pair<const Key, Value>, the tree is ordered by key alone, and balancing keeps the height at O(log n). The difference is purely behavioral. map::insert rejects a second entry with an existing key. multimap::insert accepts it and adds a new node next to the old one.

Output:

Iteration walks the entries by key, with Alice's three orders grouped together and Bob's two right after. Within a single key, the values come out in insertion order: ORD-1001, then ORD-1003, then ORD-1010. The C++11 standard fixed this rule, and every current implementation honors it.

The exact tree shape depends on the implementation, but the in-order traversal is fixed: every Alice entry first (in insertion order), then every Bob entry. The cyan nodes are first-occurrences of each key, the orange nodes are repeats. Each is a real, distinct tree node with its own pair.

Every operation costs the same as on std::map: insert, erase, find, range queries are all O(log n) (with an extra +k factor for operations that walk a range of equal keys). The tree's height is independent of how many duplicates each key carries.

std::map::operator[](key) returns "the" value for a key. On a multimap, that doesn't have an answer. If Alice has three orders, which one does ordersByCustomer["Alice"] return? The operator does not exist on std::multimap. Calls to m["Alice"] are a compile error.

at(key) is gone for the same reason. Both functions are bracket-style accessors that pick a single value; without uniqueness, there's nothing to pick.

That leaves three options for "fetch values for a key": equal_range, find combined with manual iteration, and lower_bound/upper_bound paired up by hand. They all answer the same question, but equal_range is the most direct because it returns both ends of the run in one call.

equal_range(key) returns a std::pair<iterator, iterator> where the first iterator points at the first entry for that key and the second points one past the last. Walking from one to the other visits every value the key holds.

Output:

When the key isn't in the multimap, first == last, and the loop body never runs. Comparing the two iterators is the cheapest way to ask "does this key exist?" without paying for a separate count walk.

equal_range is O(log n) because it does two binary-search descents (one for lower_bound, one for upper_bound). Iterating the returned range is then O(k) where k is the number of matches. The caller controls iteration and can stop early.

find(key) on a multimap returns an iterator to some matching entry, with the standard not specifying which one. libstdc++ and libc++ both return the first match in iteration order. For code that depends on getting the first match specifically, lower_bound(key) is the safer call, since it's specified to return the first one.

Output:

The pattern lower_bound(k); if (it != end() && it->first == k) ... is the standard way to fetch the first match safely without a separate existence check.

count(key) returns the actual count for that key. It does an O(log n + k) walk to find both ends of the equal range and then steps through every match. For a quick existence check, the iterator comparison above is cheaper.

Output:

lower_bound and upper_bound are also useful for true range queries over keys, the same as on std::map. They don't fixate on a single key; they bracket every entry whose key falls in a range.

Output:

Every entry between day 2 and day 5 inclusive comes back, with all the duplicates intact. That's the multimap's value proposition in one query: ordered iteration plus duplicate keys plus range slicing.

insert(value) on a multimap returns just an iterator, not a pair<iterator, bool>. The insert always succeeds, so there's no bool to report.

Output:

Both calls to insert({"Headphones", ...}) add separate nodes; neither overwrites the other.

emplace(args...) constructs the pair in place from the supplied arguments, the same as on std::map. It also returns just an iterator on multimap.

Output:

std::map's insert_or_assign and try_emplace are absent from std::multimap. They don't have meaningful behavior when duplicates are allowed: there's no "the" value to assign over, and there's no failure mode for try_emplace to guard against. Bulk inserts via initializer list or iterator range work as expected, with every entry landing in the container.

Output:

The cost of each insert is O(log n): find the spot in the tree, allocate a node, splice it in, rebalance. As with std::set and std::map, the allocation cost dominates in tight loops.

erase(key) on a multimap removes every entry with that key and returns the number of removed entries.

Output:

To remove a single occurrence, get an iterator to the specific entry and call erase(it). Combined with find, that's the standard way to peel off one match while leaving the others alone.

Output:

find returned an unspecified match, which on libstdc++ is the first one ("Great"). To remove a specific value (not just any match for the key), iterate the equal range and compare each value:

Output:

The loop uses the it = erase(it) pattern to advance safely past the removed node. Writing reviews.erase(it++) works on a tree-based container too (the next iterator is still valid after the erase), but the assigned form is clearer and is the form that works on every standard container.

erase(first, last) removes a whole range. Combined with equal_range, it's a compact way to drop every entry for a key:

Output:

The cost of erase(key) is O(log n + k) (locate the range, then unlink k nodes). erase(it) is amortized O(1). Range erase is O(k log n) in the worst case but usually closer to O(k) when the range is dense.

Iterator stability is the same as std::map: inserts and erases never invalidate iterators to other entries. Long-lived iterators into a multimap stay valid across unrelated mutations.

Iteration walks the entries in key-sorted order, with entries that share a key grouped together in insertion order. The element type is std::pair<const Key, Value>, the same as std::map, so structured bindings work the same way.

Output:

The "print header on key change" pattern works because entries for the same key are guaranteed to be contiguous in iteration. There's no need for a separate group-by pass.

Values can be modified through a non-const iterator the same way they can on std::map. The key half is const and can't be changed.

Output:

Each entry's score is updated in place. No reallocation, no iterator invalidation, no rebalancing (the keys didn't change).

The comparator works exactly like on std::map: a strict weak ordering on the key type, supplied as the third template parameter. The default is std::less<Key>. The same rule applies: two keys that compare equal under the comparator are treated as duplicates, and the multimap stores them in distinct nodes but groups them together.

Output:

All three "books" entries (in different cases) end up grouped because the comparator treats them as equal. count("Books") returns 3 even though no two keys are byte-identical.

A lambda works too, with the usual decltype dance because lambdas have unnamed types. In C++20 the constructor argument can be dropped (lambdas with no captures became default-constructible); before that, the constructor argument is required.

A multimap fits when three conditions hold: keys can repeat, the data needs to come out in key order, and the relationship is one-to-many. A few examples:

The alternatives and when each one is a better fit:

The std::map<Key, std::vector<Value>> alternative deserves a closer look, because it solves the same one-to-many problem with a different cost profile. Insertion is m[key].push_back(value), which costs one O(log n) lookup plus amortized O(1) on the vector. Iteration over a key's values is a tight, contiguous loop over the vector, which is significantly cache-friendlier than walking a sequence of tree nodes. The trade-off is that the values for a single key live together in memory, which makes per-value iterator stability worse and per-value erase more expensive (linear in the vector length).

For most "one-to-many lookup" workloads, std::map<Key, std::vector<Value>> is the more pragmatic choice, especially with hot-path iteration over a key's values. std::multimap is the better fit when single-value operations dominate, the count of values per key varies wildly across keys, or stable iterators per value matter.

A small running example: a customer-support ticket queue. Each ticket has a category (the key) and a description (the value). Multiple tickets land in the same category, and the dashboard wants to display them grouped by category, count them per category, and let a support agent claim one ticket at a time from a category.

Output:

The first loop hops from one key group to the next using upper_bound(it->first), which skips over every entry sharing that key in one O(log n) jump. That is the common idiom for iterating over distinct keys on a multimap, and it works well when each key's value count is large enough that walking every entry would dominate the loop.

Compile with g++ -std=c++17 file.cpp. Every API used here works on C++17 (structured bindings); earlier standards work with the more verbose std::pair-based iteration.