Chapter 38 of 48

set & map

So far, every container we have seen keeps elements in the order we put them in. Finding a value in a vector or list means checking elements one by one: O(n). That is too slow when we have a million roll numbers and need to answer "is this roll number registered?" thousands of times.

The associative containers std::set and std::map solve this. They keep their elements sorted automatically, and finding, inserting or erasing any element takes only O(log n) time. For a million elements that is about 20 steps instead of a million.


What Are set and map?

std::set<Key> (header <set>) stores a collection of unique keys in sorted order.

std::map<Key, Value> (header <map>) stores key–value pairs with unique keys, sorted by key. Each key maps to exactly one value.

Real-life analogies:

  • A set is like the list of registered roll numbers: each appears once, and we mostly ask "is X in it?".

  • A map is like a dictionary: a word (key) leads to its meaning (value). Or a marks register: student name → marks.

Both have "multi" versions, std::multiset and std::multimap, that allow duplicate keys. We will see them later in this chapter.


How They Work Inside: Balanced Binary Search Trees

The standard does not name a data structure, but it requires O(log n) search, insert and erase, and sorted iteration. In practice, all major libraries (GCC, Clang, MSVC) implement set and map as a red-black tree, a self-balancing binary search tree.

            std::set<int> {10, 20, 30, 40, 50}

                       30
                     /    \
                   20      40
                  /          \
                10            50

  Rule: everything in the left subtree < node < everything in the right subtree
  Search for 40: 30 → go right → 40 found   (2 comparisons)
  • Because the tree is kept balanced, its height is O(log n), so search, insert and erase are O(log n) in the worst case (not just on average).

  • An in-order traversal of a BST visits keys in increasing order, which is why iterating a set or map always gives sorted output.

  • Every element is a separate tree node. So, like std::list, inserting never invalidates iterators or references, and erasing invalidates only the erased element.

The keys are compared with std::less<Key> (that is, operator<) by default. Two keys a and b are treated as equivalent (duplicates) if neither a < b nor b < a is true. The containers never use ==.


std::set – Sorted Unique Elements

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {50, 20, 40, 20, 10};      // duplicate 20 is ignored

    for (int x : s) std::cout << x << ' ';       // always sorted
    std::cout << "\nsize = " << s.size() << '\n';

    auto [it, inserted] = s.insert(30);          // C++17 structured binding
    std::cout << "insert 30: " << std::boolalpha << inserted << ", *it = " << *it << '\n';
    auto result = s.insert(30);
    std::cout << "insert 30 again: " << result.second << '\n';

    std::cout << "contains(40): " << s.contains(40) << '\n';   // C++20
    std::cout << "count(99): " << s.count(99) << '\n';

    if (auto f = s.find(20); f != s.end())                     // C++17 if-init
        std::cout << "found " << *f << '\n';

    std::cout << "erase(50) removed " << s.erase(50) << " element(s)\n";
    for (int x : s) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

10 20 40 50 
size = 4
insert 30: true, *it = 30
insert 30 again: false
contains(40): true
count(99): 0
found 20
erase(50) removed 1 element(s)
10 20 30 40 

Let's go through the important parts:

  • Duplicates are ignored. We wrote 20 twice, but the set holds it once.

  • insert returns a pair: an iterator to the element and a bool that is true only if a new element was actually inserted. auto [it, inserted] = ... is a structured binding (C++17) that unpacks the pair into two names.

  • contains(key) (C++20) returns true/false. Before C++20, use s.count(key) (0 or 1 for a set) or s.find(key) != s.end().

  • find(key) returns an iterator to the element, or end() if it is not present. The if (auto f = ...; condition) form (C++17) keeps f local to the if.

  • erase(key) returns how many elements were removed (0 or 1 for a set).

Elements of a set are read-only: *it = 99; does not compile. Changing a key in place could break the tree's ordering. To "change" an element, erase it and insert the new value.

lower_bound and upper_bound

Because the elements are sorted, a set can answer "what is the first element ≥ x?" in O(log n). This is one of the most useful features in competitive programming.

s.lower_bound(x) returns an iterator to the first element ≥ x.
s.upper_bound(x) returns an iterator to the first element > x.
Both return s.end() if no such element exists.

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {10, 20, 30, 40, 50};

    auto lb = s.lower_bound(25);   // first element >= 25
    auto ub = s.upper_bound(30);   // first element >  30
    std::cout << "lower_bound(25) = " << *lb << '\n';
    std::cout << "upper_bound(30) = " << *ub << '\n';

    // all elements in the range [20, 40]
    std::cout << "In [20, 40]: ";
    for (auto it = s.lower_bound(20); it != s.upper_bound(40); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';

    if (s.lower_bound(60) == s.end())
        std::cout << "No element >= 60\n";

    // largest element < 35 (the "predecessor")
    auto it = s.lower_bound(35);
    if (it != s.begin()) std::cout << "Largest < 35 = " << *std::prev(it) << '\n';

    std::cout << "min = " << *s.begin() << ", max = " << *s.rbegin() << '\n';
}

Output:

lower_bound(25) = 30
upper_bound(30) = 40
In [20, 40]: 20 30 40 
No element >= 60
Largest < 35 = 30
min = 10, max = 50
set:              10   20   30   40   50
lower_bound(25)             ↑ (first ≥ 25)
upper_bound(30)                  ↑ (first > 30)

*s.begin() is the minimum and *s.rbegin() (reverse begin) is the maximum. Both are O(1) in practice, but only valid if the set is not empty.


std::map – Key–Value Pairs

Each element of a std::map<K, V> is a std::pair<const K, V>: first is the key (constant, for the same reason as set elements) and second is the value (which you may change).

#include <iostream>
#include <map>
#include <stdexcept>
#include <string>

int main() {
    std::map<std::string, int> marks;
    marks["Ravi"] = 78;
    marks["Asha"] = 91;
    marks.insert({"Meena", 85});
    marks.emplace("Kabir", 66);

    for (const auto& [name, score] : marks)       // sorted by key
        std::cout << name << " -> " << score << '\n';

    marks["Ravi"] = 80;                           // overwrite existing value
    std::cout << "Ravi now: " << marks.at("Ravi") << '\n';

    std::cout << "size before: " << marks.size() << '\n';
    std::cout << "Zoya: " << marks["Zoya"] << '\n';   // inserts Zoya with 0!
    std::cout << "size after:  " << marks.size() << '\n';

    try {
        std::cout << marks.at("Nobody") << '\n';
    } catch (const std::out_of_range&) {
        std::cout << "at(\"Nobody\") threw out_of_range\n";
    }

    if (auto it = marks.find("Asha"); it != marks.end())
        std::cout << it->first << " scored " << it->second << '\n';
}

Output:

Asha -> 91
Kabir -> 66
Meena -> 85
Ravi -> 78
Ravi now: 80
size before: 4
Zoya: 0
size after:  5
at("Nobody") threw out_of_range
Asha scored 91

The operator[] Trap

Look closely at marks["Zoya"]. We only wanted to read Zoya's marks, but the size went from 4 to 5. This is the most important rule about map:

m[key] returns a reference to the value for key. If the key does not exist, it first inserts it with a value-initialised value (0 for numbers, empty string for std::string).

Consequences:

  • operator[] cannot be used on a const map (it might modify it).

  • The value type must be default-constructible.

  • To only look up, use find(), contains(), or at() (which throws std::out_of_range for a missing key).

But this "insert zero" behavior is exactly what we want for counting:

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::string text = "the cat and the dog and the bird";
    std::map<std::string, int> freq;

    std::istringstream in(text);
    std::string word;
    while (in >> word)
        ++freq[word];        // missing key starts at 0, then incremented

    for (const auto& [w, c] : freq)
        std::cout << w << ": " << c << '\n';
}

Output:

and: 2
bird: 1
cat: 1
dog: 1
the: 3

The first time a word is seen, freq[word] creates it with 0, and ++ makes it 1. The output is in alphabetical order because the map is sorted by key. For n words with m distinct words, this runs in O(n log m) comparisons.

insert vs operator[] vs try_emplace vs insert_or_assign

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

int main() {
    std::map<std::string, int> stock = {{"pen", 10}};

    stock.insert({"pen", 99});                    // key exists: does NOTHING
    std::cout << "after insert:           pen = " << stock["pen"] << '\n';

    auto [it1, added1] = stock.try_emplace("pen", 50);       // C++17
    std::cout << "after try_emplace:      pen = " << it1->second
              << " (added: " << std::boolalpha << added1 << ")\n";

    auto [it2, added2] = stock.insert_or_assign("pen", 25);  // C++17
    std::cout << "after insert_or_assign: pen = " << it2->second
              << " (added: " << added2 << ")\n";

    auto [it3, added3] = stock.insert_or_assign("ink", 7);
    std::cout << "ink = " << it3->second << " (added: " << added3 << ")\n";
}

Output:

after insert:           pen = 10
after try_emplace:      pen = 10 (added: false)
after insert_or_assign: pen = 25 (added: false)
ink = 7 (added: true)

Operation

If key is missing

If key exists

Standard

m[k] = v

Inserts default, then assigns v

Overwrites

C++98

m.insert({k, v}) / emplace(k, v)

Inserts

Does nothing

C++98 / C++11

m.try_emplace(k, args...)

Inserts, constructing the value from args

Does nothing (and does not even construct the value)

C++17

m.insert_or_assign(k, v)

Inserts

Overwrites

C++17

m.at(k)

Throws std::out_of_range

Returns reference

C++11

All of these are O(log n). The insert-family functions return a pair<iterator, bool>, just like set::insert.

Erasing While Iterating

#include <iostream>
#include <map>

int main() {
    std::map<int, char> m = {{1, 'a'}, {2, 'b'}, {3, 'c'}, {4, 'd'}, {5, 'e'}};

    // erase all even keys while iterating
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2 == 0)
            it = m.erase(it);    // erase returns the next valid iterator
        else
            ++it;
    }
    for (const auto& [k, v] : m) std::cout << k << v << ' ';
    std::cout << '\n';

    std::erase_if(m, [](const auto& kv) { return kv.second == 'c'; });   // C++20
    for (const auto& [k, v] : m) std::cout << k << v << ' ';
    std::cout << '\n';
}

Output:

1a 3c 5e 
1a 5e 

m.erase(it) destroys the node it points to, so it becomes invalid. Since C++11, erase returns an iterator to the next element, so the safe pattern is it = m.erase(it); and we only do ++it when we did not erase. C++20 adds std::erase_if(container, predicate), which does the whole loop for you. (The [](const auto& kv) { ... } is a lambda, covered in the Lambda Expressions chapter; kv is each key–value pair.)


multiset and multimap – Duplicate Keys Allowed

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

int main() {
    std::multiset<int> ms = {5, 3, 5, 1, 5, 3};
    for (int x : ms) std::cout << x << ' ';
    std::cout << "\ncount(5) = " << ms.count(5) << '\n';

    ms.erase(ms.find(5));            // removes ONE 5
    std::cout << "after erase(find(5)): count(5) = " << ms.count(5) << '\n';
    ms.erase(5);                     // removes ALL remaining 5s
    std::cout << "after erase(5):       count(5) = " << ms.count(5) << '\n';

    std::multimap<std::string, std::string> phone;
    phone.insert({"Ravi", "98xxxx0001"});
    phone.insert({"Asha", "98xxxx0002"});
    phone.insert({"Ravi", "98xxxx0003"});

    auto [first, last] = phone.equal_range("Ravi");
    for (auto it = first; it != last; ++it)
        std::cout << it->first << ": " << it->second << '\n';
}

Output:

1 3 3 5 5 5 
count(5) = 3
after erase(find(5)): count(5) = 2
after erase(5):       count(5) = 0
Ravi: 98xxxx0001
Ravi: 98xxxx0003
  • ms.erase(value) removes every copy of that value. To remove just one, erase an iterator: ms.erase(ms.find(value)) (after checking that find did not return end()).

  • count(key) on a multiset is O(log n + k), where k is the number of matches.

  • equal_range(key) returns the pair {lower_bound(key), upper_bound(key)}: all elements with that key.

  • multimap has no operator[] and no at(), because a key may correspond to several values.

  • Since C++11, equal keys keep their insertion order (a new duplicate goes after the existing ones), which is why Ravi's two numbers come out in the order we inserted them.

A multiset is a handy "sorted bag": for example, to maintain the running median, or the minimum and maximum of a sliding window, while elements are added and removed.


Custom Ordering

The full template is std::set<Key, Compare> and std::map<Key, Value, Compare>. The comparator decides both the order and what counts as a duplicate.

#include <compare>
#include <functional>
#include <iostream>
#include <set>
#include <string>

struct Student {
    std::string name;
    int roll;
    auto operator<=>(const Student&) const = default;   // C++20: compares name, then roll
};

struct ByRoll {
    bool operator()(const Student& a, const Student& b) const { return a.roll < b.roll; }
};

int main() {
    std::set<int, std::greater<int>> desc = {3, 9, 1, 7};
    for (int x : desc) std::cout << x << ' ';
    std::cout << '\n';

    std::set<Student> byName = {{"Ravi", 3}, {"Asha", 7}, {"Meena", 1}};
    for (const auto& s : byName) std::cout << s.name << '(' << s.roll << ") ";
    std::cout << '\n';

    std::set<Student, ByRoll> rolls = {{"Ravi", 3}, {"Asha", 7}, {"Meena", 1}, {"Dup", 3}};
    for (const auto& s : rolls) std::cout << s.name << '(' << s.roll << ") ";
    std::cout << "\nsize = " << rolls.size() << " (Dup has the same roll as Ravi)\n";
}

Output:

9 7 3 1 
Asha(7) Meena(1) Ravi(3) 
Meena(1) Ravi(3) Asha(7) 
size = 3 (Dup has the same roll as Ravi)
  • std::greater<int> sorts in descending order.

  • A struct used as a key needs an ordering. The simplest modern way is the defaulted three-way comparison operator<=> (C++20), which compares members in declaration order (here: name, then roll). Before C++20 you would write operator< yourself.

  • With the ByRoll comparator, Dup and Ravi are equivalent (same roll), so Dup was rejected as a duplicate, even though the names differ. This surprises many people: equivalence comes only from the comparator.

The comparator must be a strict weak ordering. Using <= violates it (an element would not be equivalent to itself) and causes undefined behavior.


C++23: flat_set and flat_map

A red-black tree allocates one node per element and jumps around memory when searching. C++23 adds std::flat_set and std::flat_map (headers <flat_set> and <flat_map>), which store the keys in a sorted vector instead (a flat_map uses one vector for keys and one for values) and use binary search.

#include <flat_map>
#include <iostream>
#include <string>

int main() {
    std::flat_map<std::string, int> fm;   // C++23: sorted vectors instead of a tree
    fm["pen"] = 10;
    fm["book"] = 40;
    fm["ink"] = 5;
    for (const auto& [k, v] : fm) std::cout << k << '=' << v << ' ';
    std::cout << '\n';
}

Output (GCC 15, -std=c++23):

book=40 ink=5 pen=10 

Lookups are still O(log n) but faster in practice thanks to contiguous memory, and iteration is very fast. The price: insertion and erasure are O(n) (elements shift), and any insertion or erasure can invalidate iterators and references. Use them for data that is built once and searched many times. Compiler support is recent (GCC 15 has them; older compilers may not), so check before relying on them.


Complexity Summary

Operation

set / map

multiset / multimap

insert, emplace

O(log n)

O(log n)

find, contains, lower_bound, upper_bound

O(log n)

O(log n)

count(key)

O(log n)

O(log n + matches)

erase(key)

O(log n)

O(log n + matches)

erase(iterator)

O(1) amortized

O(1) amortized

m[key], at(key)

O(log n) (map only)

not available

Full iteration (sorted)

O(n)

O(n)

size(), empty(), begin()

O(1)

O(1)

The iterators are bidirectional: you can use ++, --, std::next, std::prev, but not it + 5. std::distance(s.begin(), it) works but takes O(n), so a set cannot tell you "the index of x" quickly.


Common Mistakes

  1. Reading with m[key] and accidentally inserting keys. Use find, contains or at to look up.

  2. Using std::lower_bound(s.begin(), s.end(), x) on a set. It compiles, but with bidirectional iterators it takes O(n) steps. Always call the member s.lower_bound(x), which is O(log n).

  3. Dereferencing end(). *s.lower_bound(x) is undefined behavior if no element ≥ x exists. Check against s.end() first.

  4. ms.erase(value) on a multiset when you meant to remove one copy. Use ms.erase(ms.find(value)).

  5. Using an iterator after erasing it: write it = m.erase(it);.

  6. Trying to modify a key through an iterator. Keys are const; erase and re-insert.

  7. A comparator that is not a strict weak ordering (for example using <=, or comparing only part of the data when you need all of it): wrong results or undefined behavior.


Interview / GATE-Style Questions

Q1. Which data structure is typically used to implement std::map, and what are the complexities of insert, find and erase?

A self-balancing binary search tree, in practice a red-black tree. Insert, find and erase (by key) are O(log n) in the worst case, because the tree's height is kept at O(log n).

Q2. What does this print? std::map<std::string, int> m; if (m["x"] == 0) std::cout << m.size();

It prints 1. m["x"] inserts the key "x" with value 0 before the comparison, so the map now has one element.

Q3. Given std::set<int> s = {2, 4, 6, 8}, what are *s.lower_bound(4), *s.upper_bound(4) and s.lower_bound(9) == s.end()?

4 (first element ≥ 4), 6 (first element > 4), and true (no element ≥ 9).

Q4. How do you count how many elements of a std::set lie in the range [a, b]? Why is std::distance a problem?

Iterate from s.lower_bound(a) to s.upper_bound(b) and count, or use std::distance between those iterators. Finding the two ends is O(log n), but counting the elements between them is O(k) because set iterators are bidirectional (no random access). For O(log n) range counts you need a different structure, such as a Fenwick tree or GCC's policy-based ordered set.

Q5. When would you choose std::map over std::unordered_map?

When you need keys in sorted order, range queries (lower_bound/upper_bound), the smallest/largest key, or guaranteed O(log n) worst-case time. A hash map gives average O(1) lookup but no ordering and an O(n) worst case. The next chapter covers this in detail.


Summary

  • set stores unique sorted keys; map stores key–value pairs with unique sorted keys. Both are balanced BSTs (red-black trees) with O(log n) insert, find and erase.

  • insert returns pair<iterator, bool>; contains is C++20; try_emplace and insert_or_assign are C++17.

  • m[key] inserts a default value for a missing key. Great for counting, dangerous for lookups.

  • lower_bound (first ≥ x) and upper_bound (first > x) answer ordered queries in O(log n); always use the member versions.

  • multiset/multimap allow duplicates; erase(key) removes all of them.

  • The comparator defines both order and equality; it must be a strict weak ordering.

  • C++23's flat_set/flat_map trade O(n) insertion for faster lookups and iteration.

In the next chapter, unordered_set & unordered_map, we give up the ordering to get average O(1) lookups using hash tables.