SyntaxPilot
Courses/C++/Lesson 23

C++ · Lesson 23 of 40 · 12 min

STL 3: map and set

queued

These are the notes for C++ episode 23, the third STL episode. In episode 22 you built a deque and a linked list: great for adding and removing, but to find something you still walk through everyone. Here you fix that. You will invent the balanced binary search tree, and then meet the two STL containers built on it: std::map (a key and a value) and std::set (just keys). Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; outputs and error messages are copied from those runs. Timings change from run to run and machine to machine; the ratio between them is what matters.

The problem: your phone's contacts

Your phone's contacts list is a set of pairs: a name and a number. You never scroll to find Ravi; you type his name and the number appears. Now scale it up: a company directory with 100000 employees, and a phone system that looks people up thousands of times a minute. Finding by name must be fast.

Step 1: the obvious way, a vector of pairs

A name and a number belong together. C++ has a tiny struct for exactly that: pair. A pair<A, B> holds two values, called first and second. (It lives in <utility>, which <vector>, <map> and friends already include.)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<pair<string, string>> contacts = {
        {"Asha", "98100 11111"},
        {"Ravi", "98100 22222"},
        {"Meena", "98100 33333"}};
    string want = "Ravi";
    for (auto c : contacts)              // walk everyone
        if (c.first == want)
            cout << want << ": " << c.second << endl;
    return 0;
}

Output:

Ravi: 98100 22222

It works, for three contacts. To find Ravi, the loop checks Asha, then Ravi.

Step 2: scale it up, and time it

100000 contacts called user0, user1, ... and 20000 searches. We time it with <chrono>, the stopwatch from episode 22 (steady_clock::now(), duration_cast<milliseconds>(end - start).count()).

#include <iostream>
#include <vector>
#include <string>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    vector<pair<string, int>> contacts;
    for (int i = 0; i < 100000; i++)
        contacts.push_back({"user" + to_string(i), i});
    auto start = steady_clock::now();
    int found = 0;
    for (int q = 0; q < 20000; q++) {       // 20000 searches
        string want = "user" + to_string(q * 5);
        for (auto& c : contacts)
            if (c.first == want) { found++; break; }
    }
    auto end = steady_clock::now();
    cout << "vector: " << found << " found in "
         << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
    return 0;
}

Output:

vector: 20000 found in 2753 ms

Seconds, for one batch of searches. A real phone system would freeze.

Why the loop is slow

A loop starts at the first contact and checks them one by one. With n contacts, one search can take n checks, so the time grows in step with n: O(n) per search ("order n"; double the contacts, double the time). 20000 searches × up to 100000 checks is about a billion string comparisons. To go faster, we must skip most names without looking at them.

An old printed phone book is sorted, A to Z. You open it in the middle and land on M. Ravi comes after M, so the whole left half is gone in one look. Do it again on the half that's left: 100000 → 50000 → 25000 → ... → 1. That takes about 17 looks, because 2^17 = 131072 ≥ 100000. Halving at every step is called binary search, and its cost is O(log n) (log base 2: the number of times you can halve n before reaching 1).

Contacts (n) Loop, worst case Binary search, about
1000 1000 checks 10 looks
100000 100000 checks 17 looks
1000000 1000000 checks 20 looks
1000000000 1000000000 checks 30 looks

The catch: binary search needs the data sorted. Keep a sorted vector, and every new employee who joins in the middle makes everyone after them shift one place, the same pain as inserting at the front of a vector in episode 22.

Step 4: inventing the binary search tree

Picture a records office with cabinets. The first cabinet is labelled M. Files for names before M go into the cabinet on its left; names after M go to the right. Each of those cabinets splits again the same way: F on the left, S on the right, and so on.

                 [ M ]
               /       \
          [ F ]         [ S ]
         /    \        /     \
     [ Asha ] [ Ira ] [ Ravi ] [ Zoya ]

Find "Ravi":  Ravi > M  -> go right
              Ravi < S  -> go left   -> found
  • Each cabinet is a node: it holds one key and two links, a left child and a right child.
  • The rule at every node: everything on the left is smaller, everything on the right is bigger.
  • This shape is a binary search tree (BST): "binary" because each node has at most two children.
  • Finding a name: one comparison per level, and every comparison throws away half of what's left.
  • Adding a name: walk down exactly like a search, then hang a new node at the bottom. No other file moves. Adding is as fast as finding.

One more rule: a careless office could put the names in A, B, C, D order and get a tree that is one long chain (then a search is a loop again). A good clerk keeps the two sides even. A tree that rebalances itself after every insert and erase is a balanced BST; its height stays about log₂ n. C++ uses a red-black tree, a kind of balanced BST, inside std::map and std::set. You never write the tree yourself.

Step 5: std::map, key to value, always sorted

#include <map>. map<Key, Value>: the key is what you search by, the value is what you get back.

Operation What it does Cost
m[key] = value store (adds the key if missing, else overwrites) O(log n)
m[key] read, but adds the key with a default value if it is missing O(log n)
m.at(key) read; throws std::out_of_range if missing, never adds O(log n)
m.count(key) 1 if the key is there, 0 if not (keys are unique) O(log n)
m.find(key) iterator to the entry, or m.end() O(log n)
m.insert({key, value}) add if missing; does not overwrite O(log n)
m.erase(key) remove the entry O(log n)
m.size(), m.empty() how many entries; whether there are none O(1)
for (auto p : m) every entry as a pair, in key order O(n)
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> phone;          // key: name, value: number
    phone["Ravi"] = "98100 22222";
    phone["Asha"] = "98100 11111";
    phone["Meena"] = "98100 33333";
    cout << "Ravi: " << phone["Ravi"] << endl;
    phone["Ravi"] = "99999 00000";      // same key: updated
    cout << "Contacts: " << phone.size() << endl;
    for (auto p : phone)                 // always in key order
        cout << p.first << " -> " << p.second << endl;
    return 0;
}

Output:

Ravi: 98100 22222
Contacts: 3
Asha -> 98100 11111
Meena -> 98100 33333
Ravi -> 99999 00000

Notice three things:

  1. Contacts: 3, not 4. A key appears only once; storing to "Ravi" again updated his value.
  2. The loop prints Asha, Meena, Ravi: sorted by key, although Ravi was added first. That's the tree.
  3. Each entry is a pair<const string, string>: p.first is the key, p.second the value. The key is const because changing it would break the tree's order.

The race

#include <iostream>
#include <map>
#include <string>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    map<string, int> contacts;
    for (int i = 0; i < 100000; i++)
        contacts["user" + to_string(i)] = i;
    auto start = steady_clock::now();
    int found = 0;
    for (int q = 0; q < 20000; q++) {       // the same 20000 searches
        string want = "user" + to_string(q * 5);
        if (contacts.count(want)) found++;
    }
    auto end = steady_clock::now();
    cout << "map: " << found << " found in "
         << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
    return 0;
}

Output:

map: 20000 found in 5 ms

The same 20000 searches: seconds with the vector loop, a few milliseconds with the map. Each search is now about 17 comparisons instead of tens of thousands.

Step 6: the [] trap, and reading safely

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> phone = {{"Asha", "98100 11111"},
                                 {"Ravi", "98100 22222"}};
    cout << "Zoya: [" << phone["Zoya"] << "]" << endl;
    cout << "Contacts: " << phone.size() << endl;
    return 0;
}

Output:

Zoya: []
Contacts: 3

No error, an empty number, and 3 contacts. Asking about Zoya added her.

Why: m[key] means "give me the value for this key, and if the key is missing, create it with a default value first" (empty string for string, 0 for int, false for bool). It has to, because it returns a reference you can assign to (phone["Zoya"] = ...). Handy for writing; dangerous for reading. It also means [] cannot be used on a const map (it might modify it).

Read safely with count or find:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> phone = {{"Asha", "98100 11111"},
                                 {"Ravi", "98100 22222"}};
    if (phone.count("Zoya") == 0)
        cout << "Zoya: not in contacts" << endl;
    auto it = phone.find("Ravi");        // an iterator, or end()
    if (it != phone.end())
        cout << it->first << ": " << it->second << endl;
    cout << "Contacts: " << phone.size() << endl;
    return 0;
}

Output:

Zoya: not in contacts
Ravi: 98100 22222
Contacts: 2

find returns an iterator (episode 22: a pointer-like object that marks a position). it->first is the key, it->second the value; it == phone.end() means "not found".

Or use at, which never adds:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> phone = {{"Asha", "98100 11111"}};
    cout << phone.at("Asha") << endl;
    cout << phone.at("Zoya") << endl;   // not there
    return 0;
}

Output:

98100 11111
terminate called after throwing an instance of 'std::out_of_range'
  what():  map::at

std::out_of_range is an exception: an error object thrown at run time. Nobody catches it here, so the program is terminated. You will learn to catch exceptions with try / catch in episode 31.

You want to... Use
store or update m[key] = value
read a key you know is there m.at(key) (crashes loudly if you were wrong)
check whether a key is there m.count(key)
check and then read, in one lookup auto it = m.find(key); if (it != m.end()) ... it->second
count or accumulate m[key]++, m[key] += x (the default 0 is exactly right)

Step 7: the canteen poll, [] used well

The office canteen asks everyone to vote for a drink. You keep a tally sheet: one line per drink, a stroke for every vote. A new drink? Write it down at zero, then add one. That is exactly what [] does:

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> votes = {"chai", "coffee", "chai", "lassi",
                            "chai", "coffee", "chai"};
    map<string, int> count;
    for (string v : votes)
        count[v]++;                 // a new drink starts at 0
    for (auto p : count)
        cout << p.first << ": " << p.second << endl;
    return 0;
}

Output:

chai: 4
coffee: 2
lassi: 1

count[v]++: if v is new, [] creates it at 0, and ++ makes it 1. The result comes out sorted by name, for free. Counting with a map (word frequencies, votes, how many times each number appears) is one of the most common patterns in real code and in interviews.

Step 8: the school gate, inventing the set

Students scan ID cards at the gate, and every scan is saved. Ravi scans three times, Asha twice. The principal asks: how many students came today?

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<string> scans = {"Ravi", "Asha", "Ravi", "Meena", "Asha", "Ravi"};
    cout << "Present today: " << scans.size() << endl;
    return 0;
}

Output:

Present today: 6

Wrong: only three students came. A vector keeps every repeat. We want the keys of a map without the values: each name once. That's std::set (#include <set>).

#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> scans = {"Ravi", "Asha", "Ravi", "Meena", "Asha", "Ravi"};
    set<string> present;
    for (string s : scans)
        present.insert(s);          // a repeat is ignored
    cout << "Scans: " << scans.size() << ", students: " << present.size() << endl;
    for (string s : present) cout << s << " ";
    cout << endl;
    auto r = present.insert("Ravi");
    cout << "Ravi added again? " << (r.second ? "yes" : "no") << endl;
    cout << "Is Zoya here? " << present.count("Zoya") << endl;
    return 0;
}

Output:

Scans: 6, students: 3
Asha Meena Ravi 
Ravi added again? no
Is Zoya here? 0
  • insert(x) adds x if it isn't there; a repeat is ignored.
  • insert returns a pair<iterator, bool>: .second is true if x was added, false if it was already inside.
  • count(x) is 0 or 1; find(x) returns an iterator or end(); erase(x) removes it.
  • Iteration is sorted, because a set is the same balanced tree, holding only keys.

A set answers the question "have I seen this before?" in O(log n).

Values in a set are read-only

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> rolls = {3, 7, 9};
    auto it = rolls.begin();
    *it = 5;                        // change a value inside the set
    return 0;
}

g++ says:

main.cpp:8:9: error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<int>::operator*()’

Each value decides its own place in the tree; changing it in place would break the order, so set iterators give you const access. To "change" a value: rolls.erase(3); rolls.insert(5);. The same is true of a map's keys (but a map's values can be changed freely).

Step 9: ranges with lower_bound and upper_bound

A sorted container can answer range questions. A shop's phone prices; a customer wants phones from ₹10000 to ₹20000:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> prices = {8999, 12499, 15999, 19999, 24999, 31999};
    auto from = prices.lower_bound(10000);   // first price >= 10000
    auto to = prices.upper_bound(20000);     // first price > 20000
    cout << "Phones from 10000 to 20000: ";
    for (auto it = from; it != to; it++)
        cout << *it << " ";
    cout << endl;
    return 0;
}

Output:

Phones from 10000 to 20000: 12499 15999 19999 
Call Returns an iterator to...
s.lower_bound(x) the first element ≥ x (or end())
s.upper_bound(x) the first element > x (or end())

So [lower_bound(a), upper_bound(b)) is every element from a to b inclusive. Both calls take O(log n), however many prices there are. map has lower_bound / upper_bound too (by key).

multiset and multimap: when you do want repeats

Container Keeps Duplicates? Sorted?
set<T> keys no yes
multiset<T> keys yes yes
map<K, V> key → value no (unique keys) yes, by key
multimap<K, V> key → value yes (a key can repeat) yes, by key
#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;

int main() {
    multiset<int> marks = {78, 91, 78, 65, 91, 78};
    cout << "How many 78s? " << marks.count(78) << endl;
    for (int m : marks) cout << m << " ";
    cout << endl;
    multimap<string, string> phones;   // one person, several numbers
    phones.insert({"Ravi", "98100 22222"});
    phones.insert({"Ravi", "022 2400 1111"});
    phones.insert({"Asha", "98100 11111"});
    auto range = phones.equal_range("Ravi");   // every entry with key Ravi
    for (auto it = range.first; it != range.second; it++)
        cout << it->first << ": " << it->second << endl;
    return 0;
}

Output:

How many 78s? 3
65 78 78 78 91 91 
Ravi: 98100 22222
Ravi: 022 2400 1111

multiset::count(x) really counts; erase(x) removes all copies (to remove one, erase(s.find(x))). multimap has no [] (which value would it return?).

Ordering by something else

A map and a set sort with < by default. Pass a comparator as the last template argument to change the order, for example greater<int> for biggest first:

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <functional>
using namespace std;

int main() {
    set<int, greater<int>> scores = {45, 99, 72, 88};
    for (int s : scores) cout << s << " ";   // biggest first
    cout << endl;
    map<int, string, greater<int>> rank = {{3, "Meena"}, {9, "Ravi"}, {5, "Asha"}};
    cout << "Top: " << rank.begin()->second << endl;
    return 0;
}

Output:

99 88 72 45 
Top: Ravi

vector vs map vs set

Need Pick Why
a list in order of arrival, fast index vector contiguous, v[i] in O(1)
look up a value by a key map O(log n) find, insert, erase
unique items, "seen before?" set O(log n) insert / count
sorted output, ranges (lower_bound) map / set the tree keeps keys in order
repeats, still sorted multiset / multimap same tree, duplicates allowed

Common mistakes (and the real g++ messages)

Mistake What happens Fix
Reading with m[key] compiles, and silently adds the key with a default value; size() grows count, find or at
m.at(key) on a missing key terminate called after throwing an instance of 'std::out_of_range', what(): map::at check with count / find first (or catch it, episode 31)
*it = 5; on a set element error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<int>::operator*()’ erase the old value, insert the new one
Searching a big vector with a loop, over and over correct but O(n) per search: seconds a map or a set
Expecting insertion order from a map keys come out sorted, not in the order added keep a vector alongside if you need arrival order
m.insert({k, v}) to update does nothing if k exists m[k] = v or insert_or_assign

Mini project: a phone book

Commands from input: add <name> <number>, find <name>, del <name>, list, end. find must not add anyone.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> book;
    string cmd, name, number;
    while (cin >> cmd && cmd != "end") {
        if (cmd == "add") {
            cin >> name >> number;
            bool isNew = book.count(name) == 0;
            book[name] = number;
            cout << (isNew ? "Added " : "Updated ") << name << endl;
        } else if (cmd == "find") {
            cin >> name;
            auto it = book.find(name);          // never adds
            if (it == book.end()) cout << name << ": not found" << endl;
            else cout << name << ": " << it->second << endl;
        } else if (cmd == "del") {
            cin >> name;
            cout << (book.erase(name) ? "Deleted " : "No such contact ") << name << endl;
        } else if (cmd == "list") {
            for (auto p : book) cout << "  " << p.first << " " << p.second << endl;
            cout << book.size() << " contacts" << endl;
        }
    }
    return 0;
}

Output:

Added Ravi
Added Asha
Ravi: 98100
Zoya: not found
Updated Ravi
Deleted Asha
  Ravi 99999
1 contacts

(The output above is for the input add Ravi 98100 add Asha 98200 find Ravi find Zoya add Ravi 99999 del Asha list end, typed into the program's input box.)

Extensions: a prefix <letters> command that prints every name starting with those letters (hint: lower_bound(prefix), then walk while the name still starts with it).

Practice

  1. Word counter: count how many times each word appears in a sentence, printed alphabetically.
  2. Unique marks: given the marks of a class, print each distinct mark once, highest first, and how many distinct marks there are.
  3. First repeat: given a list of roll numbers, print the first one that appears a second time.
  4. Range count: in a set of prices, count the prices from a to b inclusive.
Solutions

1. stringstream (from <sstream>) splits a sentence into words with >>, just like cin.

#include <iostream>
#include <map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string text = "the cat saw the dog and the dog saw the cat";
    stringstream words(text);
    map<string, int> freq;
    string w;
    while (words >> w) freq[w]++;
    for (auto p : freq) cout << p.first << ": " << p.second << endl;
    return 0;
}

Output:

and: 1
cat: 2
dog: 2
saw: 2
the: 4

2. A set<int, greater<int>> removes repeats and sorts highest first.

#include <iostream>
#include <set>
#include <vector>
#include <functional>
using namespace std;

int main() {
    vector<int> marks = {72, 95, 60, 95, 72, 88, 60, 95};
    set<int, greater<int>> distinct(marks.begin(), marks.end());
    for (int m : distinct) cout << m << " ";
    cout << endl << distinct.size() << " distinct marks" << endl;
    return 0;
}

Output:

95 88 72 60 
4 distinct marks

3. insert(...).second is false the first time a value repeats.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> rolls = {12, 7, 31, 7, 12, 40};
    set<int> seen;
    for (int r : rolls) {
        if (!seen.insert(r).second) {   // already inside
            cout << "First repeat: " << r << endl;
            break;
        }
    }
    return 0;
}

Output:

First repeat: 7

4. distance(from, to) counts the steps between two iterators (it walks, so it is O(k) for a set; fine here).

#include <iostream>
#include <set>
#include <iterator>
using namespace std;

int main() {
    set<int> prices = {8999, 12499, 15999, 19999, 24999, 31999};
    int a = 12000, b = 25000;
    auto from = prices.lower_bound(a);
    auto to = prices.upper_bound(b);
    cout << distance(from, to) << " phones from " << a << " to " << b << endl;
    return 0;
}

Output:

4 phones from 12000 to 25000

Quick quiz

What does this print?

map<string, int> m;
m["b"] = 2;
m["a"] = 1;
m["b"] += 5;
cout << m["c"] << " ";
for (auto p : m)
    cout << p.first << p.second << " ";
Answer

0 a1 b7 c0. m["b"] += 5 makes b 7. Reading m["c"] adds c with the default 0 and prints 0. Then the loop prints every entry in sorted key order: a, b, c, including the c we added by accident.

Interview questions

  1. What data structure is behind std::map and std::set? A self-balancing binary search tree, usually a red-black tree. Find, insert and erase are O(log n); iteration is in sorted key order.
  2. What is the difference between m[k] and m.at(k)? [] inserts a default-constructed value if k is missing (and so cannot be used on a const map); at never inserts and throws std::out_of_range.
  3. How do you check whether a key exists? m.count(k) (0 or 1) or m.find(k) != m.end(); C++20 adds m.contains(k).
  4. Why can't you modify an element of a set through an iterator? Its position in the tree depends on its value; set iterators are const. Erase and re-insert.
  5. What do lower_bound and upper_bound return? The first element ≥ x, and the first element > x.
  6. map vs multimap? A map's keys are unique; a multimap allows repeated keys and has no operator[].
  7. When would you still use a sorted vector instead of a set? When the data is built once and then only searched: a sorted vector with binary_search / lower_bound uses less memory and is cache-friendly.
  8. What does set::insert return? A pair<iterator, bool>: where the element is, and whether it was newly inserted.

Glossary

Term Meaning, with an example
pair Two values stored together, first and second: pair<string, string> c = {"Ravi", "98100 22222"};
key What you look something up by: the name in a phone book.
value What you get back for a key: the phone number.
std::map A sorted container of unique keys, each with a value: map<string, string> phone;
std::set A sorted container of unique keys with no values: set<string> present;
multimap / multiset Like map / set, but a key may appear more than once.
binary search Finding a value in sorted data by halving the range at every look: about 17 looks for 100000 items.
O(n), O(log n) Big-O: how the work grows with the size n. O(n): doubles when n doubles. O(log n): grows by one step when n doubles.
logarithm (log₂ n) How many times you can halve n before reaching 1: log₂ 1024 = 10.
tree Data arranged as nodes linked from a single top node (the root), each node pointing to its children.
node One element of a tree (or a linked list): a value plus links to other nodes.
binary search tree (BST) A tree where each node has at most two children: smaller keys on the left, bigger on the right.
balanced tree A tree kept even on both sides so its height stays about log₂ n.
red-black tree The balanced BST used inside std::map and std::set; it recolours and rotates nodes to stay balanced.
iterator An object marking a position in a container: auto it = phone.find("Ravi");, then it->second.
end() The iterator one past the last element; find returns it for "not found".
count(k) How many elements have key k: 0 or 1 in a map or set.
find(k) An iterator to key k, or end().
at(k) Read the value for k; throws std::out_of_range if k is missing.
default value What [] creates for a missing key: "" for string, 0 for int.
exception An error object thrown at run time, such as std::out_of_range; if nobody catches it, the program terminates.
lower_bound(x) Iterator to the first element ≥ x.
upper_bound(x) Iterator to the first element > x.
comparator The rule that decides the order, less<T> by default; greater<T> sorts biggest first.
frequency count Counting how many times each item appears, e.g. count[v]++ in a map.

Summary

  • A loop over a vector checks everyone: O(n) per search, seconds for big data.
  • The phone book trick, binary search, throws away half at every look: about 17 looks for 100000 names.
  • A sorted vector makes inserts slow, so you invented the binary search tree: smaller left, bigger right, kept balanced (a red-black tree in C++).
  • std::map<K, V>: unique keys, each with a value, always sorted; find, insert, erase in O(log n).
  • m[k] adds missing keys. Read with count, find or at; use [] to write and to count (m[k]++).
  • std::set<T>: unique, sorted keys; insert(x).second tells you if x was new; values are read-only.
  • lower_bound / upper_bound answer range questions in O(log n).
  • multiset / multimap allow repeats.

Next episode: 17 steps is good, but what if a name could tell you exactly where it lives, in one step, like a hotel room number? unordered_map, unordered_set and hashing.