Статья Автор: Деникина Н.В., Деникин А.В.

Множества в C++

Множество (set) в С++
  • Хранит только уникальные элементы (никаких повторов!)
  • Автоматически сортирует элементы по возрастанию
  • Очень быстро ищет, добавляет и удаляет элементы (за O(log n))

Как создать множество?

Подключаем библиотеку и создаём:
#include <set>
set<int> mySet;                    // пустое множество
set<int> nums = {5, 2, 8, 1, 9};   // сразу с элементами → {1,2,5,8,9}

Основные операции

Добавление — insert():
s.insert(5);  // добавить 5
s.insert(5);  // повтор — ничего не произойдёт
Удаление — erase():
s.erase(5);   // удалить 5
s.clear();    // удалить ВСЁ
Поиск — find() и count():
if (s.find(5) != s.end()) { /* найден */ }
if (s.count(5) > 0) { /* найден — проще! */ }
Размер — size() и empty():
cout << s.size();     // количество элементов
if (s.empty()) { }    // пустое ли?
Перебор всех элементов:
for (int x : s) {
    cout << x << " ";
}
Минимум и максимум:
int minVal = *s.begin();   // первый = минимум
int maxVal = *s.rbegin();  // последний = максимум
Бинарный поиск — lower_bound() и upper_bound():
auto it = s.lower_bound(x);  // первый >= x
auto it = s.upper_bound(x);  // первый > x

Таблица сложности операций

Операция Что делает Сложность
insert(x) Добавить элемент O(log n)
erase(x) Удалить элемент O(log n)
find(x) Найти элемент O(log n)
count(x) Есть ли элемент? (0/1) O(log n)
lower_bound(x) Первый >= x O(log n)
upper_bound(x) Первый > x O(log n)
size() Количество O(1)
empty() Пустое ли? O(1)
begin()/rbegin() Мин/Макс O(1)
clear() Очистить всё O(n)
 

Операции над двумя множествами

В математике есть специальные операции для работы с множествами. Давай разберём их на примере двух множеств: A = {1, 2, 3, 4} и B = {3, 4, 5, 6}.
Операция Символ Описание Пример
Объединение A ∪ B Всё, что есть хотя бы в одном {1,2,3,4,5,6}
Пересечение A ∩ B Только общие элементы {3, 4}
Разность A \ B В A, но не в B {1, 2}
Симм. разность A △ B Ровно в одном {1, 2, 5, 6}
Подмножество A ⊆ B Все A есть в B? {3,4} ⊆ B = да

Шаблоны кода

Объединение (A ∪ B):
set<int> result;
for (int x : a) result.insert(x);
for (int x : b) result.insert(x);
Пересечение (A ∩ B):
set<int> result;
for (int x : a) {
    if (b.count(x) > 0)
        result.insert(x);
}

Разность (A \ B):
set<int> result;
for (int x : a) {
    if (b.count(x) == 0) result.insert(x);
}

Симметрическая разность (A △ B):
set<int> result;
for (int x : a) if (b.count(x) == 0) result.insert(x);
for (int x : b) if (a.count(x) == 0) result.insert(x);

Проверка подмножества (A ⊆ B):
bool isSubset = true;
for (int x : a) {
    if (b.count(x)==0) {
        isSubset = false;
        break;
    }
}
 
Печать