1. Введение
Когда вы начинаете писать программы, очень легко подсесть на std::vector: положил значения в список, пробежался циклом, всё красиво. Но довольно быстро появляются задачи из серии «проверить, встречалось ли уже такое значение», «убрать дубликаты», «есть ли такой элемент в списке разрешённых/запрещённых». Делать это через vector можно, но чаще всего вы либо пишете линейный поиск руками, либо случайно получаете “скрытую квадратичную боль”, когда внутри цикла ещё один поиск.
Множество в программировании — это как список гостей на вечеринке, где охрана работает строго: «одного и того же гостя два раза не пускаем». И ещё охрана умеет отвечать на главный вопрос очень быстро: «Этот человек уже внутри?». В C++ такими «списками гостей» являются std::set и std::unordered_set.
std::set и std::unordered_set: что это и чем отличаются
Если говорить максимально по-человечески, то оба контейнера решают одну и ту же задачу: хранят элементы без повторов и позволяют быстро проверить принадлежность. Отличаются они “внутренней организацией” и тем, как ведут себя при обходе.
std::set<T> хранит элементы в отсортированном порядке (по правилу сравнения, чаще всего — по <). Поэтому если вы идёте по set циклом, элементы будут приходить по возрастанию (для строк — по лексикографическому порядку).
std::unordered_set<T> хранит элементы «в хеш-таблице». Порядок обхода там не считается “по возрастанию”, и на него нельзя полагаться. Зато проверка “есть ли элемент” обычно очень быстрая.
Небольшая табличка, чтобы картинка закрепилась:
| Контейнер | Уникальность | Порядок при обходе | Типичный смысл |
|---|---|---|---|
|
да | упорядоченный (по ключу) | «мне важен порядок» или «мне удобно, что оно само сортируется» |
|
да | не фиксирован | «мне важна скорость проверки, порядок не важен» |
И да, оба контейнера — часть стандартной библиотеки, включая unordered_set.
2. Базовые операции: insert, contains/find, erase
Любой контейнер становится “вашим другом”, когда вы уверенно делаете три вещи: добавляете, проверяете наличие и удаляете. У множеств это как раз самые частые операции, и в C++ они выглядят довольно дружелюбно, если не пугаться итераторов.
Добавление: insert и что он возвращает
Когда вы добавляете элемент в set или unordered_set, контейнер либо вставляет его (если такого ещё не было), либо тихо ничего не делает (если элемент уже есть). И чтобы вы не гадали “а что произошло?”, insert возвращает пару: итератор и флаг bool. Флаг говорит: “вставка реально произошла или элемент уже был”.
Пример на std::set:
#include <iostream>
#include <set>
int main() {
std::set<int> s;
auto [it1, ok1] = s.insert(10);
auto [it2, ok2] = s.insert(10);
std::cout << ok1 << ' ' << ok2 << '\n'; // 1 0
}
Здесь ok1 == true, потому что 10 впервые появилась в множестве. А ok2 == false, потому что второй раз “такой гость уже внутри”.
Проверка “есть ли элемент”: contains, find и count
Проверять наличие элемента можно разными способами. В современном C++ (C++20+) есть удобный метод contains, который возвращает true/false. Если ваш компилятор поддерживает C++23 (а курс у нас именно такой), contains — отличный выбор для “просто проверить”.
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::unordered_set<std::string> banned{"spam", "ads"};
std::cout << banned.contains("spam") << '\n'; // 1
std::cout << banned.contains("news") << '\n'; // 0
}
Если по какой-то причине contains недоступен (или вам нужно не просто “да/нет”, а доступ к итератору), используйте find. Он возвращает итератор: либо на найденный элемент, либо end().
#include <iostream>
#include <set>
int main() {
std::set<int> s{1, 2, 3};
if (auto it = s.find(2); it != s.end()) {
std::cout << "found: " << *it << '\n'; // found: 2
} else {
std::cout << "not found\n";
}
}
Есть ещё метод count(x). Для множества он возвращает 0 или 1 (потому что повторов нет). Иногда это удобно, но в учебном коде чаще читаемее выглядит contains.
Удаление: erase(value) возвращает “сколько удалили”
Удаление из множества по значению — это erase(value). Он возвращает число удалённых элементов. Для set/unordered_set это почти всегда 0 или 1, и это приятно: можно сразу понять, удаление “сработало” или элемента не было.
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> s{1, 2, 3};
std::size_t removed1 = s.erase(2);
std::size_t removed2 = s.erase(42);
std::cout << removed1 << ' ' << removed2 << '\n'; // 1 0
}
4. Практические приёмы: убрать дубли и не ломать set
Убираем дубли: “фильтр уникальности”
Почти магический трюк: вы берёте список с повторяющимися значениями (например, vector), и за одну строчку превращаете его в набор уникальных значений. Это не только “удобно”, но и помогает голове: вы буквально говорите коду, что вам нужно множество, а не список.
#include <iostream>
#include <set>
#include <vector>
int main() {
std::vector<int> v{3, 1, 3, 2, 1};
std::set<int> uniq(v.begin(), v.end()); // сконструировали set из диапазона
for (int x : uniq) {
std::cout << x << ' '; // 1 2 3
}
std::cout << '\n';
}
Почему здесь set, а не unordered_set? Потому что set ещё и отсортировал. Если сортировка не нужна, можно сделать unordered_set. Но в таком случае порядок печати будет “какой получится”, и это нормально (если вы не пытаетесь сделать из этого логику).
Почему элементы set нельзя “просто взять и поменять”
На первый взгляд это может удивить: в vector мы могли менять v[i], а в set — нет. Причина логичная: в set элемент одновременно является ключом, а структура данных внутри контейнера зависит от ключей. Если вы “втихаря” поменяете ключ, контейнер сломает сам себя: элементы окажутся “не там”, поиск начнёт врать, и мир станет чуть более грустным.
Поэтому итератор set ведёт себя как итератор к const T. Попытка менять элемент напрямую обычно не компилируется — и это хорошо: компилятор спасает вас от очень хитрого бага.
Мини-демонстрация идеи:
#include <set>
int main() {
std::set<int> s{1, 2, 3};
auto it = s.find(2);
// *it = 10; // так нельзя: элемент в set "как ключ", менять его нельзя
}
Если вам нужно “заменить” элемент, вы делаете это как взрослый человек: удаляете старое значение и вставляете новое. Да, это две операции, зато структура остаётся корректной.
5. Учебное приложение TaskBox: теги через unordered_set
Чтобы множества не остались абстрактной теорией, давайте продолжим развивать наше маленькое консольное приложение “TaskBox” (условное название): оно хранит задачи, а мы хотим добавлять задачам теги и гарантировать, что тег не повторяется.
Представим, что задача у нас — это struct Task, а у каждой задачи есть заголовок и набор тегов. Теги — идеальный кандидат на unordered_set<std::string>: нам важнее быстро проверять “есть ли уже тег”, чем выводить теги отсортированными.
Модель задачи с тегами как unordered_set
#include <string>
#include <unordered_set>
struct Task {
int id{};
std::string title;
std::unordered_set<std::string> tags; // теги без повторов
};
Здесь важно, что unordered_set хранит уникальные строки. Если пользователь десять раз добавит тег "study", внутри всё равно будет один "study".
Добавляем тег и читаем результат insert
Теперь напишем маленькую функцию, которая добавляет тег и говорит, был ли он добавлен реально.
#include <string>
#include <unordered_set>
bool AddTag(std::unordered_set<std::string>& tags, const std::string& tag) {
auto [it, inserted] = tags.insert(tag);
return inserted; // true, если тега раньше не было
}
Обратите внимание на дизайн: мы возвращаем bool, потому что для логики приложения важен именно факт “был новый тег или нет”. Итератор it нам здесь не нужен, но insert всё равно его возвращает — просто потому, что API контейнера универсальное.
Использование в main: без дублей и без лишней драмы
#include <iostream>
#include <string>
#include <unordered_set>
bool AddTag(std::unordered_set<std::string>& tags, const std::string& tag) {
auto [it, inserted] = tags.insert(tag);
return inserted;
}
int main() {
std::unordered_set<std::string> tags;
std::cout << AddTag(tags, "study") << '\n'; // 1
std::cout << AddTag(tags, "study") << '\n'; // 0
}
Это очень “чистая” логика: нам не нужно писать if (!contains) push_back, не нужно вручную бежать по вектору. Контейнер делает то, для чего он создан.
6. Как выбрать: set или unordered_set
Выбор между set и unordered_set в начале обучения часто вызывает ощущение: “я должен принять судьбоносное архитектурное решение”. На практике всё проще: задайте себе вопрос, важен ли вам порядок обхода и нужен ли вам “автоматический сортированный вывод”.
Если вам хочется, чтобы элементы при печати шли “красиво” (по возрастанию), или вы заранее знаете, что порядок нужен как часть поведения программы (например, вы выводите “список разрешённых команд” в отсортированном виде), берите set.
Если вам нужно много быстрых проверок “есть/нет” и порядок не важен (например, проверка запрещённых слов, тегов, id-шников), берите unordered_set. В большинстве прикладных задач “проверка принадлежности” — как раз то место, где unordered_set ощущается очень естественно.
Небольшая схема-решалка (не идеальная, но честная) может выглядеть так:
flowchart TD
A["Нужен контейнер уникальных значений"] --> B{"Важен порядок обхода?"}
B -->|Да| C["std::set<T> (упорядоченный)"]
B -->|Нет| D{"Часто проверяем contains?"}
D -->|Да| E["std::unordered_set<T> (обычно быстрее)"]
D -->|Нет / не принципиально| E
Смысл здесь не в “математической строгости”, а в том, чтобы ваш мозг каждый раз не начинал заново изобретать колесо.
7. Типичные ошибки при работе с set и unordered_set
Ошибка №1: ожидать, что unordered_set хранит элементы в “стабильном” или “отсортированном” порядке.
Это одна из самых частых ловушек: вы распечатали unordered_set два раза, увидели одинаковый порядок, и мозг радостно сделал неверный вывод “значит, так будет всегда”. Порядок обхода у unordered_set не должен использоваться как часть логики. Если вам нужен порядок — выбирайте set, и тогда порядок будет частью контракта контейнера.
Ошибка №2: игнорировать bool из insert, хотя логике важно знать, вставилось ли значение.
Новичок часто делает s.insert(x) и думает “ну вставилось и вставилось”. А потом пишет код, где нужно отличить “мы впервые увидели этот тег” от “тег уже был”. В таких местах auto [it, ok] = insert(...) — это не бюрократия, а информация, которую контейнер специально вам отдаёт, чтобы вы не гадали.
Ошибка №3: разыменовывать результат find без проверки it != end().
Паттерн с итераторами одинаков почти везде: find либо возвращает итератор на элемент, либо end(). Если сразу делать *it, вы получаете неопределённое поведение (а оно, как известно, иногда работает… чтобы потом сделать вам внезапно больно). Поэтому сначала проверка, потом доступ.
Ошибка №4: пытаться “изменить элемент” в set, как будто это vector.
В set элемент — это ключ. Менять ключ “на месте” нельзя, и компилятор обычно не даст это сделать. Правильный подход — удалить старый элемент и вставить новый. Да, чуть больше строк, зато вы сохраняете корректность структуры данных и уважаете контракт контейнера.
Ошибка №5: использовать set там, где вам на самом деле нужна частота (сколько раз встретилось).
Иногда человек видит “уникальность” и думает: “О, значит set поможет посчитать, сколько раз слово встретилось”. Но set хранит только факт присутствия. Если вам нужна частота, обычно это уже задача словаря: “значение → счётчик” (то есть map/unordered_map). В сегодняшней лекции мы это не углубляем, но важно не путать “уникальность” и “частотность”.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ