Set

A set keeps different numbers (or words) in sorted order while you add and remove them. It tells you whether a number is there and finds the nearest number above or below a given one, each in O(\log n). A map is a set whose keys each carry a value, such as a number and how many times it occurred.

Use a set when numbers are added and removed between searches. When all of them are known before the first search, sort them once and use binary search on the sorted vector.

Let's run a few calls on an empty set to see how it works.

The set is empty.

s.insert(5) puts 5 in its sorted place.

s.insert(2) puts 2 in its sorted place.

s.insert(8) puts 8 in its sorted place.

s.insert(5): 5 is already there, so nothing changes.

s.insert(6) puts 6 in its sorted place.

s.count(6) is 1: 6 is there.

s.erase(5) removes 5, and the row closes up.

s.count(5) is 0: 5 is not there.

s.lower_bound(7) finds 8, the smallest number that is at least 7.

s.lower_bound(9) finds nothing: no number is at least 9, so it returns s.end().

for (int x : s) goes through 2 6 8, in increasing order.

1/12

Fig. 1. The numbers stay sorted, and each number is in the set at most once.

These are the set's calls:

How it works

A sorted vector finds a number fast by binary search, but adding 4 to 2 5 6 8 moves 5, 6 and 8 one cell right.

A set stores its numbers in a binary search tree instead: a binary tree, a kind of graph, where every number has at most two children right below it. Every number below and to the left of a number is smaller than it, and every number below and to the right is larger.

Fig. 2. Smaller numbers are to the left, larger to the right. Read left to right, the tree is the sorted row.

This is why for (int x : s) gives the numbers in increasing order.

To find a number, start at the top. If the number you want is smaller than the current one, go left; if it is larger, go right. Stop when you find it or there is nowhere to go. insert searches the same way and attaches the new number where the search stopped.

lower_bound(x) walks the same way, with one addition. A number that is at least $x$ is remembered as the best answer so far, and the walk goes left to look for a smaller one. A number less than $x$ sends the walk right. When there is nowhere to go, the last number remembered is the answer, or s.end() if none was.

s.find(8) compares 8 with 10: 8 is smaller, so the search goes left.

s.find(8) compares 8 with 5: 8 is larger, so the search goes right.

s.find(8) compares 8 with 8: equal, so 8 is found.

s.lower_bound(4) compares 4 with 10: 10 is at least 4, so it is the best answer so far, and the walk goes left.

s.lower_bound(4) compares 4 with 5: 5 is at least 4, so it is the best answer so far, and the walk goes left.

s.lower_bound(4) compares 4 with 3: 3 is less than 4, so the walk goes right.

There is nowhere to go from 3, so s.lower_bound(4) returns 5, the last number remembered.

1/7

Fig. 3. The blue ring is the number being compared, the light blue number with a tick is the best answer so far, and green is the answer.

Each call looks at one number per level. After an insert or an erase, the library rebalances the tree by relinking a few numbers near the path (C++ uses a red-black tree). The levels stay few, at most about 34 for 10^5 numbers, so every call is O(\log n). Without rebalancing, numbers inserted in increasing order would form a chain, and a search would walk all of it.

Fig. 5. Numbers 1 to 7 inserted in increasing order, without rebalancing (left) and in a set (right).

In C++

The set is in the header <set>, and set<int> s; declares an empty one. find and lower_bound return a position in the set, which C++ calls an iterator, not a number. Read the number at position it with *it. s.end() is the position after the last number and holds nothing. s.begin() is the position of the smallest number; on an empty set it equals s.end().

This program reads q (1 \le q \le 2 \cdot 10^5), then q commands, each run with its call: add x (s.insert(x)), del x (s.erase(x)), has x (s.count(x), prints YES or NO), geq x (s.lower_bound(x), prints the number or -1) and all (prints the set in increasing order), with |x| \le 10^9.

11
add 5
add 2
add 8
add 5
add 6
has 6
del 5
has 5
geq 7
geq 9
all

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

int main() {
    int q;
    cin >> q;
    set<int> s;

    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "all") {
            for (int x : s) cout << x << ' ';   // increasing order
            cout << '\n';
            continue;
        }
        int x;
        cin >> x;
        if (cmd == "add") {
            s.insert(x);
        } else if (cmd == "del") {
            s.erase(x);
        } else if (cmd == "has") {
            cout << (s.count(x) ? "YES" : "NO") << '\n';
        } else if (cmd == "geq") {
            auto it = s.lower_bound(x);         // auto: the compiler writes the type
            if (it == s.end()) cout << -1 << '\n';
            else cout << *it << '\n';
        }
    }
}

set<int, greater<int>> compares with $>$ instead of $<$, so it keeps the numbers in decreasing order. A set of pairs orders them by .first, and pairs with equal .first by .second.

Repeated numbers: multiset

A multiset<int>, also in <set>, keeps repeated numbers: inserting 4, 1, 4, 3 gives 1 3 4 4, and count(4) gives 2. count(x) takes O(\log n + k) for $k$ copies.

unordered_set

unordered_set has the same calls except lower_bound and upper_bound, and keeps no order. It is a hash table: a formula on the key picks one of many buckets, and the key is stored there. Each call takes $O(1)$ on average. Use set by default; switch only when order is not needed and the O(\log n) calls are too slow for the limits.

Examples of use

Remembering what has been seen: count tells whether a value came before, and insert records it. After all insertions, s.size() is the number of different values, even when they are too large to index an array.

The nearest value: lower_bound(x) gives the closest value $\ge x$, and prev of it the closest value $<x$, while values keep being added and removed.

The smallest and the largest at once: *ms.begin() and *prev(ms.end()) of a multiset, for example the heights of the buildings over the current point while buildings start and end.

Common mistakes

• Calling std::lower_bound(s.begin(), s.end(), x), std::count or std::find on a set, which steps through the set one number at a time, $O(n)$ per call. Use s.lower_bound(x), s.count(x) and s.find(x).

Similar structures

When the numbers don't change once they are read, sort them in a vector and find them with binary search.

When the numbers are non-negative integers up to about 10^6, an array indexed by the number marks which ones are present.

When each key carries a value, use a map.

When you only need the smallest or only the largest number and never remove the others, a priority queue is simpler and faster than a multiset.

Practice