4.2 Структуры множеств (set)¶

Множество (set) — структура данных, которая хранит набор элементов и поддерживает базовые операции:

• вставка элемента;
• поиск элемента;
• удаление элемента.

В C++ стандартная библиотека предлагает две основные реализации:

• set — на основе сбалансированного бинарного дерева (обычно красно‑чёрное). Все операции работают за O(log n).
• unordered_set — на основе хеш-таблицы. В среднем операции работают за O(1), но в худшем случае могут деградировать.

set vs unordered_set: что выбрать¶

Обычно выбор — вопрос удобства и требований задачи:

• set удобен, когда важен порядок элементов и нужны операции вроде lower_bound/upper_bound.
• unordered_set часто быстрее на практике, когда важны только вставка/проверка/удаление и порядок не нужен.

Базовые операции set¶

Пример: создадим множество целых чисел и выполним типичные операции.

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(10);
    s.insert(4);
    s.insert(7);

    cout << s.count(10) << "\n"; // 1 (элемент есть)
    cout << s.count(6)  << "\n"; // 0 (элемента нет)

    s.erase(10);        // удалить 10
    s.insert(6);        // добавить 6

    cout << s.count(10) << "\n"; // 0
    cout << s.count(6)  << "\n"; // 1
}

Важно про count¶

Для обычного set все элементы уникальны, поэтому:

• s.count(x) возвращает либо 0, либо 1.
• s.insert(x) не добавит элемент, если он уже есть.

set<int> s;

s.insert(5);
s.insert(5);
s.insert(5);

cout << s.count(5) << "\n"; // 1

Итерация и размер¶

У set нельзя обратиться к элементу по индексу через [] (это не массив). Но можно узнать размер и пройтись по элементам.

set<int> s = {3, 9, 1, 9, 5};

cout << s.size() << "\n"; // 4 (дубликат 9 не хранится)

for (int x : s) {
    cout << x << " ";
}
// вывод: 1 3 5 9

Обрати внимание: элементы печатаются в отсортированном порядке.

Множества с повторами: multiset и unordered_multiset¶

Иногда нужно хранить несколько одинаковых элементов (например, частоты без явной map). Тогда подходят:

• multiset (упорядоченный, O(log n) на операции);
• unordered_multiset (хешированный, в среднем O(1)).

Пример multiset¶

multiset<int> ms;

ms.insert(8);
ms.insert(8);
ms.insert(8);
ms.insert(3);

cout << ms.count(8) << "\n"; // 3

Удаление в multiset: все экземпляры или один¶

По умолчанию erase(value) удаляет все вхождения значения:

multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);

ms.erase(5);
cout << ms.count(5) << "\n"; // 0

Если нужно удалить ровно один экземпляр, удаляют по итератору:

multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);

auto it = ms.find(5);   // итератор на один из элементов 5
if (it != ms.end()) {
    ms.erase(it);       // удалит только один
}

cout << ms.count(5) << "\n"; // 2

Мини‑шпаргалка¶

Как выбрать нужный формат:

flowchart TB
    A[Выбор структуры-множества] --> B{Нужен порядок?}

    B -- Да --> C{Нужны повторы?}
    C -- Нет --> D[set]
    C -- Да --> E[multiset]

    B -- Нет --> F[unordered_set]

• insert(x) — добавить элемент.
• erase(x) — удалить элемент (в multiset удалит все вхождения).
• find(x) — итератор на элемент или end(), если нет.
• count(x) — количество вхождений (0/1 для set, любое неотрицательное для multiset).
• size() — число элементов.
• Проход: for (auto x : s).