Skip to content
Tutorials Center
My learning

Topics

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

std::map and std::multimap

Learn C++ std::map and std::multimap - sorted key-value storage, insert vs operator[], try_emplace, find and contains, lower_bound range queries and custom ordering.

A map associates keys with values: a username with an account, a word with its count, a date with the day's sales. std::map<Key, T> (header <map>) keeps its entries sorted by key at all times, finds any key in O(log n), and lets you ask questions a hash table can't answer, such as "what's the first entry at or after 9:30?" or "give me everything between A and F".

In this lesson you'll learn how a map stores its elements, the four different ways to add an entry (and the famous operator[] trap), lookups with find, contains and at, range queries with lower_bound, custom ordering, how to change a key, and std::multimap for keys that repeat. The next lesson covers its hashed cousin, std::unordered_map.

How a map works

std::map is a balanced binary search tree (a red-black tree in all major libraries). Each entry lives in its own node, and the tree stays balanced as you insert and erase, so its height is about logโ‚‚ n. A map with a million entries is roughly 20 levels deep, which means any lookup, insertion or removal takes about 20 key comparisons.

Each element is a std::pair<const Key, T>: first is the key, second is the mapped value. The key is const because changing it in place would break the tree's ordering. Iteration visits elements from the smallest key to the largest, using operator< on the key type by default.

C++ A map stays sorted by key

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.

The structured binding const auto& [city, people] unpacks each pair without copying it. Writing for (auto [city, people] : population) would copy every string. C++23's std::println can print a whole map, which is handy for debugging.

Adding entries: four tools, four behaviors

There are several ways to put something into a map, and they differ in what happens when the key already exists:

Call Key missing Key present Returns
m[key] = value Inserts a default value, then assigns Assigns (overwrites) T&
m.insert({key, value}) Inserts Does nothing pair<iterator, bool>
m.insert_or_assign(key, value) (C++17) Inserts Assigns pair<iterator, bool>
m.try_emplace(key, args...) (C++17) Constructs the value from args Does nothing, and doesn't touch args pair<iterator, bool>

There's also emplace(args...), which constructs a whole pair from its arguments. It may build that pair (including the value) before discovering that the key exists, and then throw it away, so prefer try_emplace for maps.

The operator[] pitfall

m[key] is convenient, but it has a side effect that surprises people: if the key isn't there, it inserts it with a value-initialized T (0 for numbers, empty for strings) and returns a reference to that new value. Merely reading with [] changes the map. Two consequences:

  • operator[] can't be used on a const map (it doesn't compile), and it requires T to be default-constructible.
  • Code like if (scores["zoe"] > 90) quietly adds "zoe" with score 0.
C++ operator[] versus insert, insert_or_assign and try_emplace

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.

try_emplace is the safest way to insert-if-absent: when the key exists, the argument is not moved from, so name keeps its contents. With insert, you'd have built a pair (and moved name into it) before the map rejected it.

Looking things up

To read without modifying, use one of these:

  • m.find(key) returns an iterator to the element, or m.end() if it's missing. Use it when you need the value afterwards.
  • m.contains(key) (C++20) returns bool. Use it when you only need yes or no.
  • m.count(key) returns 0 or 1 for a map: the pre-C++20 way to test membership.
  • m.at(key) returns a reference and throws std::out_of_range if the key is missing. It works on const maps.
C++
if (auto it = prices.find("tea"); it != prices.end()) {
    std::println("tea costs {}", it->second);   // one lookup, then use the result
}

The if with an initializer (see if, else if and else) keeps the iterator's scope tight. Avoid the double lookup if (m.contains(k)) { use(m[k]); }: it searches twice, and the [] would compile only on non-const maps.

Erasing

m.erase(key) removes the entry and returns how many were removed (0 or 1). m.erase(it) removes the element at an iterator and returns the iterator after it, which is how you erase while looping. C++20's std::erase_if(m, pred) does the loop for you; the predicate receives each pair:

C++
std::erase_if(inventory, [](const auto& entry) { return entry.second == 0; });

Because a map is node-based, inserting never invalidates iterators or references, and erasing invalidates only the erased element.

Ordered queries: lower_bound and upper_bound

Sorted storage is what makes std::map worth its cost over a hash table. These member functions run in O(log n):

  • lower_bound(k): the first element whose key is not less than k (key โ‰ฅ k).
  • upper_bound(k): the first element whose key is greater than k (key > k).
  • equal_range(k): both at once, as a pair.

With them you can find the nearest key, or iterate over all keys in a range, without visiting the rest of the map.

C++ Range queries with lower_bound and upper_bound

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.

The shipping example uses the "floor" pattern: upper_bound(kg) finds the first tier that starts above the weight, and std::prev steps back to the tier that applies. It works because the map contains a tier starting at 0, so upper_bound never returns begin() for a non-negative weight; with arbitrary keys, check that before stepping back.

Custom ordering and heterogeneous lookup

The third template parameter is the comparison. It must be a strict weak ordering: irreflexive (comp(a, a) is false) and consistent. Two keys are considered equal when neither is less than the other, so a comparator also defines what "the same key" means.

C++
std::map<int, std::string, std::greater<int>> high_scores;   // largest key first

Lookups normally convert the argument to Key. For a std::map<std::string, T>, calling find("tea") with a string literal or a std::string_view builds a temporary std::string, which may allocate. A transparent comparator such as std::less<> (no type argument) can compare different types directly, so find, contains, lower_bound and friends accept anything comparable with the key:

C++ Custom order, transparent lookup and changing a key

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.

extract (C++17) unlinks a node and hands it to you as a node handle; you can modify the key, then insert it back into the same map or another map of the same type without allocating. m.merge(other) moves all nodes whose keys aren't already present from other into m the same way.

Notice that commands["QUIT"] replaced the value but kept the original key spelling "quit", because the comparator considered them equal.

std::multimap: repeated keys

std::multimap<Key, T> (also in <map>) allows several elements with the same key, kept in insertion order among themselves. It has no operator[] and no at() (which value would they return?). Instead:

  • insert always succeeds and returns just an iterator.
  • count(key) returns how many elements have that key.
  • equal_range(key) returns the range of all of them; find returns one of them.
  • erase(key) removes all of them; erase one by passing an iterator.
C++ A multimap of appointments

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.

A multimap is a good fit for "group by" data that stays sorted. Often a std::map<Key, std::vector<T>> is simpler, though: you get one entry per key with all its values together, plus operator[] for appending (by_day[day].push_back(what)).

Performance and alternatives

  • Every node is a separate allocation with three pointers and a color bit of overhead, so a map uses much more memory than its data and traverses slowly compared with a vector.
  • Lookups cost O(log n) comparisons. For string keys, each comparison can touch many characters.
  • If you don't need ordering, std::unordered_map usually looks up faster on average.
  • If the data is built once and then only read, a sorted std::vector<std::pair<K, V>> searched with std::ranges::lower_bound is often faster and smaller. C++23 packages that idea as std::flat_map in <flat_map>, which GCC 15 supports; insertions are O(n), lookups are cache-friendly.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::map<std::string, int> m; if (m["x"] == 0) {} What is m.size() afterwards?

    operator[] inserts a value-initialized element when the key is missing, even if you only read the result. Use find, contains or at to look without inserting.
  2. 2. The map already contains {"tea", 3}. What does m.insert({"tea", 9}) do?

    insert never overwrites. Its pair result holds an iterator to the existing element and false. Use insert_or_assign or operator[] to overwrite.
  3. 3. For the map {10: a, 20: b, 30: c}, what do lower_bound(20) and upper_bound(20) point to?

    lower_bound finds the first key not less than 20 (20 itself); upper_bound finds the first key greater than 20, which is 30.
  4. 4. Why should you prefer try_emplace over insert when the value is expensive to build or is passed with std::move?

    try_emplace checks the key first and only constructs the value if the key is missing, so a moved-from argument isn't consumed in vain.
  5. 5. Which operation does std::multimap NOT provide?

    With duplicate keys, operator[] would be ambiguous, so multimap has neither operator[] nor at(). Use equal_range to reach all values of a key.

Summary

  • std::map<K, T> is a balanced tree of pair<const K, T> sorted by key: O(log n) insert, find and erase, sorted iteration, stable iterators.
  • m[key] inserts a default value when the key is missing, even when you only read. Use find, contains (C++20) or at for read-only lookups.
  • insert and try_emplace never overwrite; insert_or_assign and operator[] do. try_emplace leaves its arguments alone when the key exists.
  • lower_bound (โ‰ฅ), upper_bound (>) and equal_range answer nearest-key and range questions in O(log n).
  • Custom comparators change the order and the meaning of "same key"; std::less<> enables lookups with string_view without allocating. extract lets you change a key without reallocating.
  • std::multimap allows duplicate keys: use count, equal_range, and erase by iterator to remove a single entry.

Next: std::unordered_map, the hash table that trades ordering for average O(1) lookups.