skip to content

Ordered Maps and Sets

std::map and std::set keep keys sorted in a balanced tree with a strict weak ordering, and C++23 adds flat_map. Interviewers ask what operator[] inserts and when lookup is O(log n).

on this pageshow

explore

questions

6

In C++, what happens when std::map::operator[], at() and find() are each called with a key that is not in the map?

level: juniorimportance: must knowfreq 75%

answer

  1. only one of them writes
  2. value-initialized mapped value
  3. std::out_of_range
  4. the end() iterator
  5. no const operator[]

basics

~10 s

std::map::operator[] inserts the missing key with a value-initialized mapped value and returns a reference to it; at() throws std::out_of_range; find() returns end(). Only operator[] changes the map, so a const map has no operator[].

solid answer

~40 s

The three look the same in a code review but have different contracts. `m[k]` is specified as `try_emplace(k).first->second`: if `k` is absent it **inserts** `k` with a value-initialized mapped value (`0` for an `int`, an empty `std::string`) and returns a reference to it, so the map grows. `m.at(k)` returns a reference if the key exists and throws `std::out_of_range` otherwise. `m.find(k)` returns an iterator to the element or `m.end()`, and never changes the map. Because `operator[]` may insert, it has no `const` overload and needs a default-constructible mapped type. All three are logarithmic in `size()`. Use `find` (or C++20 `contains`) to ask, `at` when absence is a bug, and `operator[]` when you mean insert-or-update.

code

cpp · 25 lines
cpp
#include <iostream>
#include <map>
#include <stdexcept>

int main() {
    // Ask side of an order book: price in ticks -> resting quantity
    std::map<int, int> asks{{10100, 5}, {10105, 2}};

    int q = asks[10102];  // missing key: inserts {10102, 0}
    std::cout << "operator[]: q=" << q << " size=" << asks.size() << '\n';

    if (auto it = asks.find(10110); it != asks.end())
        std::cout << "found " << it->second << '\n';
    else
        std::cout << "find: not found, size=" << asks.size() << '\n';

    try {
        (void)asks.at(10110);
    } catch (const std::out_of_range&) {
        std::cout << "at: threw std::out_of_range, size=" << asks.size() << '\n';
    }

    const auto& view = asks;  // view[10100] would not compile on a const map
    std::cout << "contains(10105)=" << view.contains(10105) << '\n';
}

go deeper

for a junior

Recall the three outcomes cold: operator[] inserts, at throws std::out_of_range, find returns end(). Say which one changes the map.

for a middle

Explain why operator[] must insert: it is defined through try_emplace, needs a default-constructible mapped type and has no const overload.

for a senior

Show the production bug: a read through operator[] that grows a map, such as empty price levels in a book, and the find-based fix with a single lookup.

for a principal

Argue for a code-review rule on lookups in shared code: operator[] only for intended upserts, find or contains for questions, at only where absence is a bug.

## Three lookups, three contracts A **`std::map<Key, T>`** is an ordered associative container: its elements are `std::pair<const Key, T>` kept sorted by key, and every lookup costs **O(log n)** comparisons. It offers three common ways to reach the value for a key, and they disagree about what to do when the key is missing. | Call | Key present | Key missing | Usable on `const std::map`? | |---|---|---|---| | `m[k]` | reference to the value | **inserts** `{k, T()}`, returns a reference to it | no | | `m.at(k)` | reference to the value | throws `std::out_of_range` | yes | | `m.find(k)` | iterator to the element | returns `m.end()` | yes (returns `const_iterator`) | C++20 adds `m.contains(k)`, a plain `bool` membership test, which is what most `m.count(k) != 0` checks were trying to say. ## Why operator[] inserts The standard defines `operator[]` in one line: it is equivalent to `return try_emplace(x).first->second;`. `try_emplace` with no extra arguments constructs the mapped value from nothing, which is **value-initialization**: `0` for arithmetic types, `nullptr` for pointers, the default constructor for classes. So `m[k]` always yields a reference to a live element, and the only way to guarantee that for a missing key is to create one. Three consequences follow directly: - `operator[]` has **no `const` overload**. Calling it through a `const std::map&` fails to compile; Apple clang 21 reports `no viable overloaded operator[] for type 'const std::map<int, int>'`. - The mapped type must be **default-constructible**. A map of a type without a default constructor can use `try_emplace`, `insert`, `emplace` or `insert_or_assign`, but not `operator[]`. - `std::multimap` has **no `operator[]` and no `at()`**, because one key may own several values and there is no single reference to return. It is searched with `find`, `equal_range` or `lower_bound`. ## The order-book bug Consider the ask side of an order book, keyed by price in ticks: 1. A risk check reads `asks[price]` to see how much is resting at a price level. 2. The level does not exist, so `operator[]` silently inserts it with quantity `0`. 3. The book now has an empty level that iteration, depth snapshots and "best ask" logic all see. Nothing crashes, which is exactly why this is the classic `std::map` bug: a read that was meant to be pure became a write. The fix is to use `find` and test the iterator, or `contains` when only membership matters. The same lookup written inside a `const` member function at least fails to compile, because `operator[]` is not available there. ## Choosing between them - **`find`** when the key may legitimately be absent and you need the element: one lookup gives you the iterator, which you can also pass to `erase` or use as an insertion hint. - **`contains`** (C++20) when you only need a yes or no. - **`at`** when absence would be a logic error and an exception is the right report: configuration that must exist, an invariant that a key was registered earlier. - **`operator[]`** when you mean "insert if missing, then update", as in counting: `++histogram[word];` relies on the inserted `0`. Avoid the double lookup `if (m.contains(k)) use(m.at(k));`: it searches the tree twice where one `find` would do. And never test `m[k] == 0` to ask "is it there": it answers by adding the key. ## Beyond exact keys Exact-key lookup is only half of what an ordered map is for. Because the keys are sorted, `std::map` also answers **neighbour** questions in logarithmic time, none of which insert anything: - `m.lower_bound(p)`: the first element whose key is not less than `p`, for example the best ask at or above a limit price. - `m.upper_bound(p)`: the first element whose key is greater than `p`. - `m.equal_range(k)`: both bounds at once, which for a `std::multimap` spans every value stored under `k`. When a lookup misses, `lower_bound` also returns the position where the key would go, which can be passed as a hint to `emplace_hint` or `try_emplace` so the later insert does not search again. ## Complexity and iterator effects All three lookups are logarithmic in `size()`. `find` and `at` never invalidate anything. When `operator[]` inserts, the new node is linked into the tree without moving existing elements, so iterators, pointers and references to other elements stay valid; only the size, and every loop that assumed the key set was fixed, changes.

  • Why does m[k] = v fail to compile when the mapped type has no default constructor?
    `operator[]` is specified as `try_emplace(k).first->second`, which must construct the mapped value from no arguments when `k` is absent. If `T` has no default constructor, that construction is ill-formed, even when you only ever assign afterwards. Use `insert_or_assign(k, v)`, `try_emplace(k, args...)` or `emplace`, and read with `find` or `at`.
  • Does std::multimap offer operator[] or at(), and how do you read all values for one key?
    Neither: a key in a `std::multimap` can map to several values, so there is no single element to return a reference to. Use `equal_range(k)`, which returns the half-open range of all elements with an equivalent key, or `lower_bound` and `upper_bound`. `find(k)` returns one of them, not necessarily the first inserted.
  • When is find() better than contains() followed by at()?
    Whenever you need the element after confirming it exists. `contains` then `at` walks the tree twice; `find` walks it once and hands you an iterator you can read, update, erase or use as a hint. `contains` (C++20) is the right call only when the answer is just yes or no.

  • find() inserts a default entry when the key is missing
  • operator[] on a missing key throws std::out_of_range
  • at() returns a default-constructed value for a missing key
  • operator[] works through a const std::map reference for reads
  • Checking m[k] == 0 is a safe way to test membership
open as a page

What must a custom comparator for std::map or std::set guarantee, and what goes wrong if it compares with <= instead of <?

level: middleimportance: should knowfreq 50%

basics

~20 s

It must induce a strict weak ordering: comp(a, a) is false, comp is transitive, and equivalence, neither comp(a, b) nor comp(b, a), is transitive too. A <= comparator breaks irreflexivity, so using it is undefined behaviour and lookups silently fail.

open as a page

In C++17, how do std::map::try_emplace and insert_or_assign differ from insert, emplace and operator[] when the key already exists?

level: middleimportance: should knowfreq 40%

basics

~20 s

When the key exists, try_emplace does nothing, leaves its arguments untouched and returns {iterator, false}; insert_or_assign assigns the new value and returns {iterator, false}. insert and emplace also keep the old value, but may already have consumed a moved argument.

open as a page

A word-frequency std::map<std::string, int> is searched with std::string_view tokens; why does find(token) not compile, and how do you fix it without allocating?

level: seniorimportance: should knowfreq 35%

basics

~20 s

With std::lessstd::string, find takes const std::string&, and std::string_view does not convert to it implicitly. Declare the map with a transparent comparator such as std::less<>, and the C++14 find, count and lower_bound templates compare the string_view directly.

open as a page

In C++17, how do you change the key of an element already stored in a std::map or std::multimap, and what does extract save you?

level: seniorimportance: nice to knowfreq 25%

basics

~20 s

Stored keys are const, so extract the node, write nh.key(), and insert the node handle back. The element is never copied, moved or reallocated; only tree links change, and a pointer taken before extraction refers to the same element afterwards.

open as a page

When does C++23 std::flat_map beat std::map for an order book's price levels, and what do you give up by switching?

level: seniorimportance: nice to knowfreq 25%

basics

~20 s

std::flat_map keeps sorted keys and values in two contiguous containers, so lookup and iteration are cache-friendly and per-element overhead is small. Single-element insert and erase are linear, insertions can invalidate iterators and references, and there are no node handles.

open as a page