Как устроен std::set?

Устройство std::set

std::set — это контейнер стандартной библиотеки C++, который хранит уникальные элементы в отсортированном порядке. Понимание его внутреннего устройства критично для написания эффективного кода.

Внутренняя структура: красно-чёрное дерево

std::set реализован на основе красно-чёрного дерева (red-black tree) — сбалансированного бинарного дерева поиска:

// Упрощённая структура узла
template<typename T>
struct Node {
    T value;
    Node* left;
    Node* right;
    Node* parent;
    Color color;  // RED или BLACK
};

Свойства красно-чёрного дерева

• Каждый узел окрашен в красный или чёрный цвет
• Корень всегда чёрный
• Листья (nullptr) считаются чёрными
• Красный узел имеет только чёрных детей (нет двух красных подряд)
• Все пути от корня к листьям имеют одинаковое количество чёрных узлов

Эти свойства гарантируют, что высота дерева всегда O(log n).

Сложность операций

std::set<int> s;

// Все операции O(log n)
s.insert(5);        // O(log n) — поиск позиции + балансировка
s.erase(5);         // O(log n) — удаление + балансировка
auto it = s.find(5); // O(log n) — поиск элемента
int count = s.count(5); // O(log n) — проверка наличия

Пример работы insert

std::set<int> s;
s.insert(10);
s.insert(5);
s.insert(15);
s.insert(3);
s.insert(7);

// Дерево будет выглядеть примерно так:
//        10 (B)
//       /  \
//      5    15 (B)
//     / \
//    3   7
//
// Элементы всегда в отсортированном порядке!
for (int val : s) {
    std::cout << val << " "; // 3 5 7 10 15
}

Итератор и обход

Итератор std::set — это двунаправленный итератор (bidirectional), но НЕ случайный доступ:

std::set<int> s = {10, 5, 15, 3, 7};

// Итерация вперёд O(n)
for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " "; // 3 5 7 10 15
}

// Итерация назад O(n)
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    std::cout << *it << " "; // 15 10 7 5 3
}

// Случайный доступ НЕВОЗМОЖЕН!
// s[2] — ошибка компиляции!

Сравнение с std::unordered_set

Пользовательский компаратор

std::set использует компаратор для сравнения элементов (по умолчанию less<T>):

// По убыванию
std::set<int, std::greater<int>> s;
s.insert(10);
s.insert(5);
s.insert(15);

for (int val : s) {
    std::cout << val << " "; // 15 10 5
}

// Пользовательский компаратор
struct CustomCompare {
    bool operator()(int a, int b) const {
        return std::abs(a) < std::abs(b);
    }
};

std::set<int, CustomCompare> customSet;
customSet.insert(-10);
customSet.insert(5);
customSet.insert(3);

for (int val : customSet) {
    std::cout << val << " "; // 3 5 -10
}

Практические примеры

// Удаление дубликатов
std::vector<int> vec = {1, 2, 2, 3, 3, 3};
std::set<int> unique(vec.begin(), vec.end());
// unique содержит: {1, 2, 3}

// Поиск элемента
if (unique.find(2) != unique.end()) {
    std::cout << "Найдено";
}

// Диапазонные операции
auto range = unique.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it; // всегда один элемент или ноль
}

// Получение k-го наименьшего элемента
auto kth = std::next(unique.begin(), k);
std::cout << *kth;

Когда использовать std::set

• Нужен отсортированный порядок элементов
• Частые операции вставки/удаления в середину
• Нужны операции диапазонного поиска (lower_bound, upper_bound)
• Гарантированная сложность O(log n) важнее среднего случая

std::set — это фундаментальный контейнер для многих алгоритмических задач.