A std::vector answers "what is at position 3?". A std::map answers "what is stored under the key alice?".

Four containers do this with ordered keys: map, set, multimap, multiset.

The basics

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::map<std::string, int> ages;

    ages["alice"] = 30;
    ages["bob"] = 25;
    ages.insert({"carol", 35});
    ages.emplace("dave", 40);

    // Iteration is in KEY order, always — that is the guarantee.
    for (const auto& [name, age] : ages) {
        std::cout << name << " " << age << "\n";
    }

    // operator[] INSERTS a default-constructed value if the key is absent.
    std::cout << "eve's age: " << ages["eve"] << "\n";
    std::cout << "size is now " << ages.size() << "\n";

    // at() throws instead.
    try {
        ages.at("frank");
    } catch (const std::out_of_range& e) {
        std::cout << "at() threw for a missing key\n";
    }

    // The three ways to ask "is it there?" without inserting.
    std::cout << "contains bob: " << std::boolalpha << ages.contains("bob") << "\n";
    std::cout << "count bob: " << ages.count("bob") << "\n";
    if (auto it = ages.find("bob"); it != ages.end()) {
        std::cout << "find bob: " << it->second << "\n";
    }

    std::set<int> unique = {5, 1, 3, 1, 5, 2};
    std::cout << "set: ";
    for (int x : unique) {
        std::cout << x << " ";
    }
    std::cout << "(size " << unique.size() << ")\n";

    std::multiset<int> dupes = {5, 1, 3, 1, 5, 2};
    std::cout << "multiset size " << dupes.size()
              << ", count of 5 is " << dupes.count(5) << "\n";
    return 0;
}

alice 30
bob 25
carol 35
dave 40
eve's age: 0
size is now 5
at() threw for a missing key
contains bob: true
count bob: 1
find bob: 25
set: 1 2 3 5 (size 4)
multiset size 6, count of 5 is 2

Elements came out in alphabetical order despite being inserted in a different order — that is the guarantee, and it is what you are paying for.

The operator[] trap

Read those two lines again:

eve's age: 0
size is now 5

ages["eve"] on a missing key inserts {"eve", 0} and returns a reference to that new value. The map grew. Nothing warned you.

This bites in exactly one shape, and it is common:

// if (ages["frank"] > 18) { ... }        // inserts frank, then compares 0 > 18

That is a silent modification inside what looks like a read. The correct spellings:

// ages.contains("frank")                 // C++20 — clearest
// ages.count("frank") > 0                // pre-C++20
// ages.find("frank") != ages.end()       // when you want the value too
// ages.at("frank")                       // throws if absent

operator[] is also unavailable on a const map, for exactly this reason — it is a potentially mutating operation. If a const std::map& will not let you write m[k], that is the compiler telling you something true.

Use operator[] when you want insert-if-missing, which is a genuinely useful idiom:

// std::map<std::string, int> counts;
// for (const std::string& w : words) {
//     ++counts[w];              // inserts 0 then increments, exactly right
// }

What is inside

std::map and std::set are balanced binary search trees — red-black trees in every implementation in practice. That gives:

| Operation | Cost | |---|---| | insert, erase, find | O(log n) | | Iteration | in key order, O(n) total | | Iterators after insert | stable | | Iterators after erase | only the erased one is invalidated |

The stability follows from the structure: each element is its own node, so inserting elsewhere never moves it. This is the same property std::list has (lesson 13.3), for the same reason.

The cost is the same as a list's: a separate allocation per element, and pointer-chasing traversal. A std::map<int, int> with a million entries is dramatically slower to iterate than a sorted std::vector<std::pair<int, int>>, and Module 22 measures it.

Custom ordering, and what "equal" means

The comparator is part of the container's type, not a constructor argument:

#include <iostream>
#include <map>
#include <set>
#include <string>

struct Point {
    int x;
    int y;
};

// A custom ordering: a comparator is a type, and it is part of the set's type.
struct ByDistance {
    bool operator()(const Point& a, const Point& b) const {
        return (a.x * a.x + a.y * a.y) < (b.x * b.x + b.y * b.y);
    }
};

int main() {
    std::set<Point, ByDistance> points = {{3, 4}, {1, 1}, {0, 5}};
    for (const Point& p : points) {
        std::cout << "(" << p.x << "," << p.y << ") ";
    }
    std::cout << "\n";

    // {3,4} and {0,5} both have distance 5, so the set treats them as EQUAL
    // and keeps only the first. Equivalence here is "neither is less than the
    // other" — not operator==, which Point does not even have.
    std::cout << "size " << points.size() << "\n";

    // Descending order with the standard comparator.
    std::map<int, std::string, std::greater<int>> descending;
    descending[1] = "one";
    descending[3] = "three";
    descending[2] = "two";
    for (const auto& [k, v] : descending) {
        std::cout << k << "=" << v << " ";
    }
    std::cout << "\n";

    // Range queries: the reason ordering is worth paying for.
    std::set<int> values = {10, 20, 30, 40, 50};
    auto lo = values.lower_bound(20);      // first >= 20
    auto hi = values.upper_bound(40);      // first > 40
    std::cout << "range [20,40]: ";
    for (auto it = lo; it != hi; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    return 0;
}

(1,1) (3,4) 
size 2
3=three 2=two 1=one 
range [20,40]: 20 30 40

The set has 2 elements, not 3. {3,4} and {0,5} both have distance 5, so ByDistance says neither is less than the other, and the set concludes they are the same element.

This is the single most important thing to understand about ordered containers:

Equivalence is defined by the comparator, not by operator==. Two elements are "the same" when !(a < b) && !(b < a).

Point has no operator== at all, and the set works fine — it never needs one. The consequence is that a comparator which ignores part of your data silently merges elements. Sometimes that is exactly what you want (case-insensitive keys); when it is not, it is a data-loss bug that no compiler will catch.

Your comparator must also be a strict weak ordering: irreflexive (!(a < a)), antisymmetric, and transitive. A comparator using <= instead of < violates the first, and the result is undefined behaviour — in practice a crash or a corrupted tree, not merely a wrong answer.

Range queries, the reason ordering is worth it

lower_bound and upper_bound are what an unordered container cannot offer:

// values.lower_bound(20)   first element >= 20
// values.upper_bound(40)   first element  > 40
// values.equal_range(30)   both at once, as a pair

"Every event between these two timestamps", "all names starting with M", "the closest key below this one" — these are O(log n) on a map and impossible on a hash table (lesson 13.5), which has no order at all.

If you never do a range query and never iterate in order, you are paying for ordering you do not use.

Structured bindings

// for (const auto& [key, value] : map)   // C++17, clear
// for (const auto& pair : map)           // pair.first, pair.second

A map's element is a std::pair<const Key, Value>. Note the const on the key: you cannot change a key in place, because that would move the element in the tree. To change a key, erase and re-insert.

insert versus insert_or_assign versus try_emplace

// m.insert({k, v});          does nothing if k exists; returns {iterator, bool}
// m[k] = v;                  inserts or overwrites — but default-constructs first
// m.insert_or_assign(k, v);  inserts or overwrites, without default-constructing (C++17)
// m.try_emplace(k, args...); inserts if absent, does NOT construct the value otherwise (C++17)

try_emplace is the one worth knowing about: m.emplace(k, expensive()) constructs the value even when the key is already present and the insert is discarded. try_emplace does not.

Try it

Checkpoint

• map, set, multimap, multiset keep keys ordered; iteration is always in key order.
• They are balanced binary search trees: O(log n) insert, erase, and find.
• Iterators are stable across insertion; only an erased element's iterator is invalidated.
• operator[] inserts a default-constructed value for a missing key — a silent write.
• Use contains (C++20), find, or at to look up without inserting.
• The comparator is part of the type, and it defines equivalence: !(a<b) && !(b<a).
• A comparator that ignores part of the data silently merges elements.
• A comparator must be a strict weak ordering; using <= is undefined behaviour.
• lower_bound, upper_bound, and equal_range are the payoff for ordering.
• The key in a map element is const; to change a key, erase and re-insert.
• try_emplace avoids constructing a value that will be discarded.