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.
insertreturns a pair: an iterator to the element and aboolthat istrueonly 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) returnstrue/false. Before C++20, uses.count(key)(0 or 1 for a set) ors.find(key) != s.end().find(key)returns an iterator to the element, orend()if it is not present. Theif (auto f = ...; condition)form (C++17) keepsflocal to theif.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 returns.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 = 50set: 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 91The 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 forkey. If the key does not exist, it first inserts it with a value-initialised value (0 for numbers, empty string forstd::string).
Consequences:
operator[]cannot be used on aconstmap (it might modify it).The value type must be default-constructible.
To only look up, use
find(),contains(), orat()(which throwsstd::out_of_rangefor 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: 3The 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 |
|---|---|---|---|
| Inserts default, then assigns | Overwrites | C++98 |
| Inserts | Does nothing | C++98 / C++11 |
| Inserts, constructing the value from | Does nothing (and does not even construct the value) | C++17 |
| Inserts | Overwrites | C++17 |
| Throws | 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: 98xxxx0003ms.erase(value)removes every copy of that value. To remove just one, erase an iterator:ms.erase(ms.find(value))(after checking thatfinddid not returnend()).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.multimaphas nooperator[]and noat(), 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, thenroll). Before C++20 you would writeoperator<yourself.With the
ByRollcomparator,DupandRaviare equivalent (same roll), soDupwas 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 |
|
|
|---|---|---|
| O(log n) | O(log n) |
| O(log n) | O(log n) |
| O(log n) | O(log n + matches) |
| O(log n) | O(log n + matches) |
| O(1) amortized | O(1) amortized |
| O(log n) (map only) | not available |
Full iteration (sorted) | O(n) | O(n) |
| 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
Reading with
m[key]and accidentally inserting keys. Usefind,containsoratto look up.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 members.lower_bound(x), which is O(log n).Dereferencing
end().*s.lower_bound(x)is undefined behavior if no element ≥ x exists. Check againsts.end()first.ms.erase(value)on a multiset when you meant to remove one copy. Usems.erase(ms.find(value)).Using an iterator after erasing it: write
it = m.erase(it);.Trying to modify a key through an iterator. Keys are const; erase and re-insert.
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
setstores unique sorted keys;mapstores key–value pairs with unique sorted keys. Both are balanced BSTs (red-black trees) with O(log n) insert, find and erase.insertreturnspair<iterator, bool>;containsis C++20;try_emplaceandinsert_or_assignare C++17.m[key]inserts a default value for a missing key. Great for counting, dangerous for lookups.lower_bound(first ≥ x) andupper_bound(first > x) answer ordered queries in O(log n); always use the member versions.multiset/multimapallow 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_maptrade 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.