Skip to content
Tutorials Center
My learning

Topics

Lesson 111 of 171 ยท The Standard Library (STL)

multiset and multimap Families

Learn C++ containers that allow duplicate keys - multimap, multiset, unordered_multimap and unordered_multiset - with equal_range, safe erasing, grouping and when to choose them.

std::map and std::set promise that every key appears at most once. That is the right rule for a phone book with one number per name, but plenty of real data is not like that. A library has many books by the same author. An event calendar has many events on the same day. A log has many messages at the same severity. Forcing these into a std::map<Key, Value> means inventing a std::vector for each key and remembering to manage it.

The standard library has four duplicate-key containers that store several entries with equal keys directly: std::multiset, std::multimap, std::unordered_multiset and std::unordered_multimap. They look like their unique cousins but differ in the details that matter: insertion never fails, there is no operator[], and looking up a key gives you a range instead of a single element. This lesson covers all four, the usual traps, and how to decide between a multimap and a map of vectors.

The four containers at a glance

Container Header Stores Order Lookup
std::multiset<T> <set> values sorted O(log n)
std::multimap<K, V> <map> key/value pairs sorted by key O(log n)
std::unordered_multiset<T> <unordered_set> values none O(1) average
std::unordered_multimap<K, V> <unordered_map> key/value pairs none O(1) average

The sorted versions are trees, like map and set; the unordered versions are hash tables with buckets, like std::unordered_map. The set versions are covered briefly in the set lesson; this lesson concentrates on the map versions and on what is shared by all four.

multimap: several values per key

A std::multimap<K, V> keeps entries sorted by key. Entries with equal keys stay next to each other, in the order they were inserted. Because a key may occur many times, operator[] and at do not exist (which value would they return?). You add entries with insert or emplace, and insert always succeeds.

C++ Books grouped by author in a multimap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Look at how the three Le Guin titles appear in the same order in which they were inserted. The standard guarantees that for the sorted multi-containers: equivalent elements keep insertion order. For the unordered versions the order among equal keys is not specified, so do not rely on it there.

Finding all entries with a key: equal_range

find(key) returns an iterator to some entry with that key (not guaranteed to be the first). To get every entry, ask for a range with equal_range, which returns a pair of iterators: the first entry with the key, and the first entry after the last one. lower_bound and upper_bound (for the sorted containers) return the two halves of the same pair.

flowchart LR
    A["Atwood"] --> B["Atwood"] --> C["Butler"] --> D["Le Guin"] --> E["Le Guin"] --> F["Le Guin"] --> G["end()"]
    C -. "lower_bound and equal_range start here" .-> D

For the key "Le Guin", equal_range returns the pair (first Le Guin, end()); the range between them holds the three matches.

C++ equal_range and removing by key or by iterator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Three rules are worth memorizing:

  • erase(key) removes all matching entries and returns how many it removed. This surprises people who expect one.
  • To remove a single entry, erase an iterator (from find, or from inside an equal_range).
  • Erasing inside a loop requires it = container.erase(it); incrementing an erased iterator is undefined behavior.

Keys are const: you can edit it->second, but not it->first, since that would corrupt the order. To change a key, use extract, as shown below.

Inserting with a hint and extracting nodes

When you insert many entries in sorted order, passing a hint speeds up the insertion: m.emplace_hint(m.end(), key, value) is amortized constant time if the new entry belongs right before the hint. A multimap also supports extract (C++17), which removes an entry without destroying it and gives you a node handle whose key you may change before inserting it back, with no copy:

C++ Renaming a key with extract

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

unordered_multimap and unordered_multiset

The hashed versions work the same way: entries with equal keys go into the same bucket. equal_range still returns every match, and count(key) still counts them. You lose the sorted order, so there is no lower_bound and no ordered iteration, and the order inside the range is unspecified. In exchange, average lookup is O(1).

That is why you should never print an unordered container and expect the same output everywhere. To produce stable output, copy the data into a sorted container or a vector and sort it first. The example does exactly that to count words and group them by length:

C++ Grouping words by length with an unordered_multimap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

An unordered_multiset is the same idea for plain values: a fast bag that answers "how many of these do I have?" with count. If all you need is counts, a std::unordered_map<T, int> is usually simpler and smaller than a multiset that stores every duplicate.

multimap or map of vectors?

Both model "one key, many values". Choose with these trade-offs in mind:

multimap<K, V> map<K, vector<V>>
Adding a value one call map[key].push_back(v)
All values for a key equal_range, iterator pair a ready-made vector
Memory one tree node per entry one node per key, plus a vector
Cache friendliness poor (nodes scattered) better (values contiguous)
Removing one value erase an iterator std::erase on the vector
Counting keys needs a loop map.size()

If you mostly read all values for a key at once, a map of vectors is usually faster and easier to use. A multimap shines when entries are inserted and erased individually in the middle, when you want one flat sorted sequence of pairs, or when the "values" are naturally independent entries (events, edges, log lines) rather than a list that belongs to a key.

Whichever you choose, wrap it in a small class with the operations you need (add, values_for, remove) so the rest of your code does not depend on the container's quirks.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::multimap<int, char> m{{1,'a'},{1,'b'},{2,'c'}}; m.erase(1); What does erase return?

    erase(key) removes every entry with that key and returns the count removed, here 2. Only erase(iterator) removes a single entry and returns an iterator.
  2. 2. Why does std::multimap not provide operator[]?

    With duplicate keys there is no single mapped value for a key. Use find, equal_range or emplace instead.
  3. 3. What does equal_range(key) return?

    The pair marks the half-open range [first, last) of matches. An empty range, where first equals last, means the key is absent.
  4. 4. Which statement about iteration order is correct?

    The sorted multi-containers keep equivalent elements in insertion order. The hashed ones make no ordering promise, so sort before printing if output must be stable.
  5. 5. When is std::map<K, std::vector<V>> usually a better choice than std::multimap<K, V>?

    The vector keeps the values contiguous in memory and hands them to you as one sequence, which is faster and simpler for read-heavy grouping.

Summary

  • multiset, multimap, unordered_multiset and unordered_multimap allow several entries with equal keys; insert always succeeds.
  • There is no operator[] or at; look entries up with find, count and equal_range.
  • Sorted multi-containers keep equal keys in insertion order; hashed ones do not.
  • erase(key) removes all matches; erase an iterator to remove just one, and use the returned iterator in loops.
  • extract lets you change a key without copying; keys are otherwise constant.
  • A map<K, vector<V>> is often faster and simpler when you read all values of a key together.

Next: Exceptions, the C++ way of reporting and handling errors that the code at hand cannot fix.