интерактивный урок
set в C++
Представь коробку, в которую можно бросать числа, но повторы исчезают, а всё внутри само сортируется. Это и есть std::set.
История: журнал посещений
Ты пишешь систему для школьной библиотеки. Ученики заходят и называют свой номер. Но один и тот же ученик может зайти несколько раз за день. Тебе нужен список уникальных посетителей.
Без set пришлось бы каждый раз проверять «а он уже был?» — это O(n) на каждую проверку. С set — O(log n).
💡 set = «коробка уникальных элементов, всегда в порядке».
| Контейнер | Повторы? | Порядок | find(x) | insert(x) |
|---|---|---|---|---|
| vector | Да | Как добавили | O(n) | O(1)* |
| set | Нет | Отсортирован | O(log n) | O(log n) |
* — O(1) амортизированное для push_back, но поиск всё равно O(n).
Первый взгляд: бросаем числа в set
Создали пустой set целых чисел. Внутри пока ничего.
Мы добавляли 5 и 2 по два раза, но в set каждый элемент один раз. Порядок всегда по возрастанию.
Все операции set и их Big O
У set четыре главные операции — и все работают за O(log n), потому что внутри это сбалансированное красно-чёрное дерево.
| Операция | Код | Сложность | Что делает |
|---|---|---|---|
| insert | s.insert(x) | O(log n) | Добавляет x, если его нет |
| erase | s.erase(x) | O(log n) | Удаляет x, если есть |
| find | s.find(x) | O(log n) | Итератор на x или end() |
| count | s.count(x) | O(log n) | 0 или 1 |
| size | s.size() | O(1) | Количество элементов |
| обход | for (int x : s) | O(n) | Все элементы по порядку |
Создали set и добавили три элемента — {3, 7, 10}.
Задача 1: есть ли дубликаты?
Условие. Дан массив из n чисел. Определи, есть ли хотя бы один повторяющийся элемент.
Пример:[3, 1, 4, 1, 5] → YES (1 встречается дважды)[1, 2, 3, 4] → NO
Идея: идём по массиву. Для каждого числа — видели ли мы его раньше? Если да → дубликат. Если нет → добавляем в set.
seen — множество чисел, которые мы уже встретили.
Сложность: O(n log n) по времени, O(n) по памяти.
🏆 Контестный шаблон «seen» — встречается почти в каждом контесте. Запомни.
Задача 2: запросы присутствия
Условие. n чисел, потом q запросов. Для каждого x — ответь YES или NO.
Считываем n и q.
Сложность: построение O(n log n), запросы O(q log n), итого O((n + q) log n).
Задача 3: сколько уникальных?
Условие. Дан массив. Сколько различных чисел?
Решение в 2 строки:
Конструктор set из итераторов — добавляет все элементы, дубликаты убираются.
💡 Конструктор
set<int>(begin, end)— мощный приём, не нужен цикл.
Контестные приёмы с set
Минимум и максимум за O(1):
begin() — итератор на наименьший элемент.
lower_bound — первый элемент >= x:
s = {1, 5, 10, 20, 50}. Ищем >= 8.
| Задача | Код | Сложность |
|---|---|---|
| Минимум | *s.begin() | O(1) |
| Максимум | *prev(s.end()) | O(1) |
| Первый >= x | s.lower_bound(x) | O(log n) |
| Первый > x | s.upper_bound(x) | O(log n) |
| Удалить мин. | s.erase(s.begin()) | O(log n) |
set vs unordered_set
| set | unordered_set | |
|---|---|---|
| Порядок | Отсортирован | Без порядка |
| insert / find | O(log n) всегда | O(1) в среднем |
| Худший случай | O(log n) | O(n) при коллизиях |
| lower_bound | Есть | Нет |
| Контесты | Надёжнее | Быстрее, но рискованнее |
Правило: нужен порядок или lower_bound →
set. Только вставка/поиск и скорость →unordered_set. При сомнении →set.
Проверь себя
Какова сложность s.find(x) для std::set?
Что выведет код?
set<int> s;
s.insert(3);
s.insert(1);
s.insert(3);
cout << s.size();
s = {2, 5, 8, 12}. Что вернёт *s.lower_bound(6)?
Как получить максимум set за O(1)?
Итог
std::set — когда нужны:
- Уникальные элементы — дубликаты убираются автоматически
- Отсортированный порядок — обход по возрастанию
- O(log n) на insert, find, erase
- O(1) на минимум / максимум
- lower_bound / upper_bound за O(log n)
Три паттерна:
- Фильтр дубликатов —
set(a.begin(), a.end())+size() - Seen-паттерн — проверяй и вставляй, ищи повторы
- Membership-запросы — построй set, отвечай на q запросов
Эти паттерны покрывают 80% задач на set в контестах!