std::set

In one sentence

A set keeps its elements sorted and without duplicates, and every insert, erase and lookup costs only \(O(\log N)\), so "how many different things have I seen?" is just st.size().

1. What problem does it solve?

Example — 1791D · Distinct Split (3-set · B, rating 1000)

Let \(f(x)\) be the number of different letters in a string \(x\). Given a string \(s\) of length \(n\), cut it into two non-empty parts \(a\) and \(b\) (so \(a + b = s\)) to make \(f(a) + f(b)\) as large as possible. Print that maximum.

Limits: \(t \le 10^4\) test cases, \(2 \le n \le 2 \cdot 10^5\), sum of \(n\) over all tests \(\le 2 \cdot 10^5\).

Input          Output
5
2
aa             2
7
abcabcd        7
5
aaaaa          2
10
paiumoment     10
4
aazz           3

The naive way. Try each of the \(n - 1\) cut positions and count the different letters on both sides from scratch: \(O(n)\) work per cut, \(O(n^2)\) in total, which is \(4 \cdot 10^{10}\) for \(n = 2\cdot10^5\). Too slow.

The fix. As the cut moves one step right, the left part gains one letter and the right part loses one. "Different letters of the left part" only ever grows, and a set can track it: insert the new letter and read size().

2. How it works

2.1 What a set stores

insert 3, 1, 4, 1, 5, 9, 2, 6      set = {1, 2, 3, 4, 5, 6, 9}
                                          ^                 ^
                                      *begin()       *prev(end())

The second 1 is ignored. The elements are always in increasing order, so the smallest is *st.begin() and the largest is *prev(st.end()). Inside, a set is a balanced search tree of height about \(\log_2 N\), which is why each operation costs \(O(\log N)\).

2.2 Prefix and suffix counts

Let pre[i] be the number of different letters in \(s_0 \dots s_i\) and suf[i] the number in \(s_i \dots s_{n-1}\). Cutting after position \(i\) gives

\[ f(a) + f(b) = \texttt{pre}[i] + \texttt{suf}[i+1], \qquad 0 \le i \le n-2 . \]

Both arrays are filled by one pass each: left to right inserting into a set for pre, right to left into a fresh set for suf.

2.3 Trace on abcabcd

\(i\)	0	1	2	3	4	5	6
\(s_i\)	a	b	c	a	b	c	d
pre[i]	1	2	3	3	3	3	4
suf[i]	4	4	4	4	3	2	1
pre[i] + suf[i+1]	5	6	7	6	5	4	—

Cutting after \(i = 2\) (abc + abcd) gives \(3 + 4 = 7\).

Cost. \(2n\) inserts at \(O(\log 26)\) each: \(O(n)\) per test, and the sum of \(n\) is bounded, so the whole input is fast.

3. Quick notes on std::set

Core Properties

• Unique: Elements only exist once. Duplicates are ignored.
• Sorted: Elements are automatically sorted in ascending order.

1. Basic Operations

C++

std::set<int> s;

// Add elements
s.insert(3);
s.insert(1);
s.insert(2); 
// s is now {1, 2, 3}

s.size();       // Returns the number of elements
s.empty();      // Returns true if the set is empty

2. Iteration (Looping)

Method A: Range-based for loop (Easiest)

C++

for (auto si : s) {
    cout << si << " ";
}

Method B: Using Iterators

C++

for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << "\n"; // Use * to get the value
}

3. Iterators & Pointers

• s.begin(): Points to the first (smallest) element.
• s.end(): Points to the position after the last element.
• *s.begin(): Gets the value of the smallest element.
• *prev(s.end()): Gets the value of the largest element.

⚠️ Iterator Warnings:

• Never call prev() on s.begin() (there is nothing before it).
• Never call next() or * on s.end() (there is nothing there).

4. Find and Erase

C++

int x = 5;

// Finding an element
if (s.find(x) == s.end()) {
    // x does not exist in the set
} else {
    // x exists in the set
}

// Removing elements
s.erase(x);          // Erase by value
s.erase(s.begin());  // Erase by iterator (removes the smallest element)

5. Time Complexity

• Insert / Erase / Find: \(O(\log N)\). Extremely fast. Even with \(10^9\) elements, it takes at most ~32 operations.
• Empty / Size / Iterator moves: \(O(1)\). Instantaneous.

4. Worked solution — Distinct Split

This problem has many test cases, so main reads T.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    vector<int> pre(n), suf(n);
    set<char> st;
    for (int i = 0; i < n; i++) {
        st.insert(s[i]);
        pre[i] = st.size();
    }

    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        st.insert(s[i]);
        suf[i] = st.size();
    }

    int ans = 0;
    for (int i = 0; i + 1 < n; i++) {
        ans = max(ans, pre[i] + suf[i + 1]);
    }
    cout << ans << "\n";
}

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

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. set, vector or counting array?

You need	Best tool	Why
number of different values, values up to \(10^9\)	set	cannot index an array by \(10^9\)
number of different values, values small (letters, \(\le 10^6\))	counting array vector<int> cnt	\(O(1)\) per update, even faster
smallest / largest while inserting and erasing	set (begin, prev(end))	stays sorted automatically
duplicates must be kept	multiset, or sort a vector	a set throws duplicates away

6. Common mistakes

*st.end() or prev(st.begin())

end() points past the last element; there is nothing there. Use *prev(st.end()) for the largest, and only when the set is not empty.

Erasing from a multiset by value

ms.erase(x) removes every copy of x. To remove one copy write ms.erase(ms.find(x)).

st.size() - 1 on an empty set

size() is unsigned, so 0 - 1 wraps around to a huge number. See Integer Types & Overflow.

Reusing a set across test cases

Call st.clear() (or declare the set inside solve()), otherwise letters from the previous test are still there.

7. Practice

Problem	Set	Rating	Idea
1703B · ICPC Balloons	3-set · A	800	a letter's first appearance is worth 2, later ones 1
1791D · Distinct Split	3-set · B	1000	prefix and suffix distinct counts (this page)
701C · They Are Everywhere	6-TwoPointers · F	1500	a set gives the target number of kinds, then a window
AIO 2023 · TeleTrip	AIO 2023 Q1	—	insert every position you stand on, print size()

---

Credits & licenses

• §3 is our quick-reference sheet on std::set, unchanged apart from heading levels.
• Example choice, tree picture, prefix/suffix derivation, trace, worked solution and mistakes are ours.