set: Sorted, No Repeats, and Found in a Few Steps

Amara runs the sign-up sheet for the coding club, and names arrive in any order, some of them twice. She needs the different names in alphabetical order, and Kenji keeps asking whether he is on the list yet. A vector would need a sort and a sweep of repeats after every sign-up, or a full scan for every question. A sorted C array shifts every later name along by one for each new name. This lesson gives Amara a container that does both jobs as the names arrive.

Two promises: sorted, and no repeats

A set is a container that holds each value at most once and keeps its values sorted. You insert values in any order. Walk the set from its start, and the values come out from the smallest to the largest. Smaller means the same < you use on numbers, and on strings it means the byte order of Module 3.

Insert a value the set already holds, and nothing changes. Module 0 gave a set the values 30, 10, 20 and 10, and it printed 10 20 30. Here is the same idea with Amara's names.

So a set gives Amara two things at once: the names come out sorted, and each name comes out once.

Inside: a tree that stays short

How does a set find a name without looking at every one? It keeps its values in a binary search tree. Each value sits in a node, a small box in memory. Every smaller value lives somewhere to a node's left, and every larger value to its right. A search starts at the top node, the root, compares once, and goes left or right, leaving a whole side behind.

The picture finds 50 among seven values. A scan of the sorted array checks 10, 20, 30, 40 and then 50: five steps. The tree asks 40, then 60, then 50: three steps. GCC 12's library builds exactly this tree when the seven values arrive as 40, 20, 60, 10, 30, 50 and 70. Other orders give other shapes, as the next section shows.

Each new level of a tree doubles the room for values, so 20 levels hold over a million. The shortest tree for a million values has 20 levels, and a find in it takes at most 20 steps. Module 2's find on a vector may take a million.

A tree kept close to that shortest shape is called balanced. The library rebalances its tree after every insert and erase. The real tree can be taller than the shortest one, but at most twice as tall; lesson 05 measures it. So a find costs one comparison per level, and the library keeps the levels few.

Watch the tree grow, one insert at a time

GCC's standard library, called libstdc++, keeps a set in a red-black tree. Each node also carries a colour, red or black. After each insert or erase, the library recolours and turns a few nodes to keep its colour rules. The widget shows the real shape after each step, without the colours. The C++ standard names no tree at all: it promises only O(log n) steps for a find, an insert and an erase.

O(log n) means that doubling n adds about one step, as Module 0 put it. Now watch 10 to 80 arrive in rising order, the worst order for a tree that never rebalances.

Eight rising values made 4 levels. A plain tree that never rebalanced would hang each value right of the last: a chain 8 levels deep. Watch the root: it moved from 10 to 20, then to 40. The repeated insert(50) walked down to the 50 already there and changed nothing. find(35) fell off the tree below 30, so 35 is not in the set.

So the shape is the library's choice, and it stays a few levels deep in any arrival order.

The syntax you need on day one

#include <set>

set<T> s;                  an empty set of T
set<T> s{a, b, c};         a set made from a list; repeats are dropped
s.insert(x);               add x; nothing happens if x is already there
s.erase(x);                remove x, if it is there
s.count(x)                 1 if x is there, 0 if not
s.find(x)                  an iterator to x, or s.end() if x is not there
s.size()    s.empty()      how many values, and whether there are none
*s.begin()  *s.rbegin()    the smallest and the largest value
for (T x : s)              every value, from the smallest to the largest

multiset<T> m;             the same calls, but repeats are kept

So everyday set code names values, never positions.

insert, and the walk in sorted order

s.insert(x) puts x in its sorted place. A range-for walks the set from the smallest value to the largest. This program prints the whole set after each insert.

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

void show(const char* step, const set<int>& s) {
    cout << step << ':';
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
}

int main() {
    set<int> s;
    s.insert(30);
    show("insert(30)", s);
    s.insert(10);
    show("insert(10)", s);
    s.insert(20);
    show("insert(20)", s);
    s.insert(10);
    show("insert(10)", s);
    return 0;
}

insert(30): 30 (size 1)
insert(10): 10 30 (size 2)
insert(20): 10 20 30 (size 3)
insert(10): 10 20 30 (size 3)

The values arrived as 30, 10 and 20, yet 10 went before 30 and 20 between them. The second insert(10) found 10 already there, so the size stayed 3. So the walk is always sorted, whatever order the inserts came in.

Is it there? count and find

s.count(x) says how many copies of x the set holds. On a set that is only ever 1 or 0, so it reads as yes or no. s.find(x) returns an iterator to x, or s.end() when x is missing.

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

int main() {
    set<int> s{3, 9, 14, 27, 31};
    cout << s.count(14) << ' ' << s.count(5) << '\n';
    auto it = s.find(27);
    if (it != s.end()) {
        cout << "found " << *it << '\n';
    }
    if (s.find(5) == s.end()) {
        cout << "5 is not there\n";
    }
    return 0;
}

1 0
found 27
5 is not there

Compare find's answer with end() before you read it with *. Reading *s.end() is undefined behaviour: the C++ standard says nothing about what happens. So use count for a plain yes or no, and find when you also want the place.

erase by value

s.erase(x) removes x if the set holds it. If it does not, nothing happens.

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

int main() {
    set<int> s{3, 9, 14, 27, 31};
    s.erase(14);
    s.erase(5);
    cout << "left:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
    return 0;
}

left: 3 9 27 31 (size 4)

erase(14) removed 14. erase(5) found no 5 and did nothing, with no error. So erasing a value that is not there is safe, while reading one that is not there is not.

The smallest and the largest

s.begin() is the place of the smallest value, so *s.begin() reads it. s.rbegin() is where a walk backwards starts, the r is for reverse, so *s.rbegin() is the largest value.

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

int main() {
    set<int> temps{31, 28, 35, 29};
    cout << "coolest " << *temps.begin() << ", hottest " << *temps.rbegin() << '\n';
    temps.insert(38);
    temps.erase(28);
    cout << "coolest " << *temps.begin() << ", hottest " << *temps.rbegin() << '\n';

    set<int> none;
    if (none.empty()) {
        cout << "an empty set has no coolest\n";
    }
    return 0;
}

coolest 28, hottest 35
coolest 29, hottest 38
an empty set has no coolest

After the insert and the erase, both ends moved, and the program never searched for them. An empty set has no smallest and no largest value. There, *s.begin() and *s.rbegin() are undefined, and lesson 06 shows what one run did. So check empty() before you read either end.

No index, and no changing a value in place

A vector has positions, so v[0] is its first element. A set has no positions, and an index does not compile.

set<int> s{10, 20, 30};
cout << s[0] << '\n';

GCC 12 stops at the runner's flags with error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int'). To reach the third value you walk to it from begin(), and lesson 03 shows how. Changing a value through its iterator does not compile either.

set<int> s{10, 20, 30};
auto it = s.find(20);
*it = 25;

GCC 12 says error: assignment of read-only location 'it.std::_Rb_tree_const_iterator<int>::operator*()'. The reason is the tree, which is ordered by its values. A 20 changed to 25 in place would sit in the wrong spot, and later searches would go the wrong way. So the library hands out every value read-only: you may read it, but never write it.

So you change a set only by insert and erase: erase the old value, then insert the new one. Lesson 02 shows a way that keeps the node.

multiset: the cousin that keeps repeats

Sometimes repeats are the point. A class voting on a trip needs every vote, not one per place. A multiset is a set that keeps repeats. It sorts the same way, lives in the same header and has the same calls. Its count(x) says how many copies of x it holds.

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

int main() {
    multiset<string> votes{"zoo", "museum", "zoo", "park", "zoo"};
    cout << "votes:";
    for (const string& v : votes) {
        cout << ' ' << v;
    }
    cout << " (size " << votes.size() << ")\n";
    cout << "zoo: " << votes.count("zoo") << ", lake: " << votes.count("lake") << '\n';
    return 0;
}

votes: museum park zoo zoo zoo (size 5)
zoo: 3, lake: 0

The three zoo votes stayed, side by side, because equal values sit next to each other in sorted order. Removing just one of them takes a call that lesson 02 shows. So reach for a multiset when you need every copy, and for a set when one is enough.

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

int main() {
    set<int> s;
    for (int x : {42, 7, 19, 7, 3}) {
        s.insert(x);
    }
    cout << "sorted:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n' << s.size() << " different values\n";
    return 0;
}

sorted: 3 7 19 42
4 different values

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

int main() {
    set<string> signed_up;
    for (string name : {"maria", "bob", "zara", "bob", "amara"}) {
        signed_up.insert(name);
    }

    for (string who : {"kenji", "zara"}) {
        if (signed_up.count(who) == 1) {
            cout << who << " is on the list\n";
        } else {
            cout << who << " is not on the list yet\n";
        }
    }

    signed_up.insert("kenji");
    auto it = signed_up.find("kenji");
    if (it != signed_up.end()) {
        cout << "now " << *it << " is on it too\n";
    }
    cout << signed_up.size() << " different people so far\n";
    return 0;
}

kenji is not on the list yet
zara is on the list
now kenji is on it too
5 different people so far

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

int main() {
    set<int> booked{12, 3, 27, 8, 15};
    booked.erase(3);
    booked.insert(30);

    cout << "booked:";
    for (int seat : booked) {
        cout << ' ' << seat;
    }
    cout << '\n';
    cout << "nearest the stage: " << *booked.begin() << ", farthest: " << *booked.rbegin() << '\n';
    if (booked.count(3) == 0) {
        cout << "seat 3 is free again\n";
    }
    return 0;
}

booked: 8 12 15 27 30
nearest the stage: 8, farthest: 30
seat 3 is free again

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

int main() {
    multiset<int> marks{85, 72, 85, 90, 64, 85, 72};
    set<int> different{85, 72, 85, 90, 64, 85, 72};

    cout << "every mark:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';
    cout << marks.count(85) << " students scored 85\n";
    cout << "lowest " << *marks.begin() << ", highest " << *marks.rbegin() << '\n';
    cout << "the multiset keeps " << marks.size() << ", a set keeps " << different.size() << '\n';
    return 0;
}

every mark: 64 72 72 85 85 85 90
3 students scored 85
lowest 64, highest 90
the multiset keeps 7, a set keeps 4

set<int> prices{10, 20, 30};
for (int& p : prices) {
    p += 5;
}

#include <iostream>
using namespace std;

int main() {
    set<int> s{3, 1, 2};
    cout << s.size() << '\n';
    return 0;
}

set<string> steps;
steps.insert("wash");
steps.insert("cut");
steps.insert("cook");
for (const string& s : steps) {
    cout << s << '\n';
}

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

int main() {
    set<string> s{"bob", "Zara", "amara"};
    cout << "order:";
    for (const string& name : s) {
        cout << ' ' << name;
    }
    cout << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    set<string> names;   // every different name, kept in alphabetical order
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        // Add name to names.
    }

    // Print how many different names there are, then every name in
    // alphabetical order, one per line.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    set<int> first;
    for (int i = 0; i < n; i++) {
        int mark;
        cin >> mark;
        first.insert(mark);
    }
    int m;
    cin >> m;
    set<int> second;
    for (int i = 0; i < m; i++) {
        int mark;
        cin >> mark;
        second.insert(mark);
    }

    // Walk first from its lowest mark. Print every mark that second also
    // holds, on one line, separated by single spaces, or the word none.

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    set<int> board;   // the highest different scores, never more than five
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        // Put score on the board, keep only the five highest, then print
        // the lowest score left on the board.
    }
    return 0;
}

Next, lesson 02 goes through every set and multiset operation, one by one, each with its cost.