Зачем нужен Set?

Назначение Set (std::set и std::unordered_set)

Set — это контейнер, который хранит уникальные значения без дубликатов. Это основная его отличительная особенность от Vector и List.

Основное назначение

Set решает задачу: "Нужно быстро проверять наличие элемента и хранить только уникальные значения"

// Пример: Отслеживание посещённых ID
vector<int> visited_ids;  // Проблема: может быть дублирование

set<int> visited_ids;     // Решение: только уникальные значения
visited_ids.insert(123);  // O(log n)
visited_ids.insert(123);  // Не добавится, уже есть

if (visited_ids.count(123)) {  // Быстро проверить наличие O(log n)
    cout << "Already visited";
}

std::set vs std::unordered_set

std::set — сбалансированное бинарное дерево поиска (Red-Black Tree):

set<int> s = {3, 1, 2};
for (int val : s) {
    cout << val << " ";  // Выведет: 1 2 3 (ОТСОРТИРОВАНО!)
}

s.insert(0);
for (int val : s) {
    cout << val << " ";  // Выведет: 0 1 2 3
}

Характеристики std::set:

• Поиск: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)
• Память: O(n)
• Порядок: Отсортирован по компаратору (по умолчанию < оператор)

std::unordered_set — хеш-таблица:

unordered_set<int> s = {3, 1, 2};
for (int val : s) {
    cout << val << " ";  // Порядок случайный (зависит от хеш-функции)
}

Характеристики std::unordered_set:

• Поиск: O(1) в среднем, O(n) в худшем
• Вставка: O(1) в среднем, O(n) в худшем
• Удаление: O(1) в среднем, O(n) в худшем
• Память: O(n)
• Порядок: Не гарантирован

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

1. Удаление дубликатов из массива

vector<int> arr = {1, 2, 2, 3, 3, 3, 4, 1};

// С set
set<int> unique(arr.begin(), arr.end());
vector<int> result(unique.begin(), unique.end());
// result = {1, 2, 3, 4}

// С unordered_set (если порядок не важен)
unordered_set<int> unique_hash(arr.begin(), arr.end());

2. Проверка наличия элемента

set<string> forbidden_words = {"admin", "root", "system"};

string user_input = "admin";
if (forbidden_words.count(user_input)) {  // O(log n)
    cout << "This word is forbidden!";
}

// С unordered_set было бы O(1) в среднем

3. Пересечение двух множеств

set<int> set_a = {1, 2, 3, 4, 5};
set<int> set_b = {3, 4, 5, 6, 7};

set<int> intersection;
set_intersection(
    set_a.begin(), set_a.end(),
    set_b.begin(), set_b.end(),
    inserter(intersection, intersection.begin())
);
// intersection = {3, 4, 5}

4. Первое появление каждого элемента

vector<int> stream = {1, 2, 3, 2, 1, 4, 5, 1};
set<int> seen;

for (int val : stream) {
    if (seen.find(val) == seen.end()) {
        cout << val << " ";  // Выведет: 1 2 3 4 5
        seen.insert(val);
    }
}

Custom компаратор

// Сортировка по убыванию
set<int, greater<int>> s = {3, 1, 2};
for (int val : s) {
    cout << val << " ";  // Выведет: 3 2 1
}

// Custom компаратор для структур
struct Person {
    string name;
    int age;
};

auto comp = [](const Person& a, const Person& b) {
    return a.age < b.age;
};
set<Person, decltype(comp)> people(comp);
people.insert({"Alice", 25});
people.insert({"Bob", 20});
// Отсортирован по возрасту

Когда использовать какой Set

Используй std::set когда:

• Нужна сортировка элементов
• Нужны операции range queries (find all elements < X)
• Частые итерации в порядке
• Требуется стабильность (O(log n) гарантированно)

Используй std::unordered_set когда:

• Порядок не важен
• Нужна максимальная производительность (O(1))
• Не нужны range операции
• Достаточно хеш-функции для типа

Резюме

Set нужен для:

1. Проверки уникальности — быстрая вставка с проверкой дубликатов
2. Быстрого поиска элемента — лучше чем в vector O(n)
3. Хранения множеств — пересечения, объединения, разности
4. Сортировки с уникальностью — std::set автоматически сортирует
5. Фильтрации дубликатов — с сохранением уникальности

Выбор между set и unordered_set зависит от того, важен ли порядок и гарантии производительности.