Зачем нужен контейнер std::set?

std::set — это ассоциативный контейнер стандартной библиотеки C++, который хранит уникальные элементы, автоматически упорядочивая их по возрастанию (с использованием оператора < по умолчанию). Его основная реализация — самобалансирующееся бинарное дерево поиска (чаще всего красно-чёрное дерево).

Ключевые преимущества и сценарии использования:

• Гарантия уникальности: Все элементы в set различны. Попытка вставить дубликат игнорируется.
• Автоматическая сортировка: Элементы всегда хранятся в отсортированном порядке, что позволяет эффективно выполнять операции, требующие порядка (например, обход в sorted order, поиск диапазонов).
• Логарифмическая сложность ключевых операций: Поиск (find, count), вставка (insert) и удаление (erase) выполняются за O(log n), где n — количество элементов.
• Стабильность итераторов: Вставка и удаление элементов не инвалидируют итераторы, указывающие на другие элементы (кроме удаляемого).

Пример использования:

#include <set>
#include <iostream>
#include <string>

int main() {
    // Хранение уникальных, отсортированных строк
    std::set<std::string> uniqueWords = {"orange", "apple", "banana", "apple"};
    // uniqueWords содержит: {"apple", "banana", "orange"}

    // Проверка наличия элемента
    if (uniqueWords.find("banana") != uniqueWords.end()) {
        std::cout << "Found banana!n";
    }

    // Итерация в отсортированном порядке
    for (const auto& word : uniqueWords) {
        std::cout << word << ' '; // Вывод: apple banana orange
    }
    std::cout << 'n';

    // Поиск нижней границы (первый элемент >= ключа)
    auto it = uniqueWords.lower_bound("apricot");
    if (it != uniqueWords.end()) {
        std::cout << "First word >= 'apricot': " << *it << 'n'; // banana
    }
}

Альтернативы и выбор контейнера:

• std::unordered_set: Используйте, когда порядок не важен, а нужна максимальная скорость поиска/вставки в среднем за O(1). Реализация — хеш-таблица.
• std::multiset: Если нужны дубликаты элементов.
• std::vector + std::sort + std::unique: Может быть эффективнее по памяти, если коллекция создаётся один раз и потом только читается.