Когда следует использовать std::set, а когда std::unordered_set в C++?

std::set и std::unordered_set используются для хранения уникальных элементов. Выбор между ними зависит от приоритетов: упорядоченность или производительность доступа/вставки/удаления.

std::set основан на сбалансированном бинарном дереве поиска (обычно красно-черном дереве).

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

• Элементы хранятся в отсортированном порядке.
• Вставка, удаление и поиск элементов занимают время О(log N), где N — количество элементов.
• Подходит, когда важен отсортированный порядок элементов, или когда требуется получение элементов в определенном диапазоне.

std::unordered_set основан на хеш-таблице.

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

• Элементы не хранятся в отсортированном порядке.
• Вставка, удаление и поиск элементов в среднем занимают время О(1), но в худшем случае (при большом количестве коллизий хеш-функции) может достигать О(N).
• Требуется, чтобы тип элемента имел определенную хеш-функцию (std::hash) и оператор сравнения на равенство (operator==).
• Подходит, когда требуется максимально быстрая вставка, удаление и поиск, и порядок элементов не имеет значения.

Сводная таблица:

Критерий	std::set	std::unordered_set
Внутренняя структура	Сбалансированное дерево	Хеш-таблица
Порядок элементов	Отсортированный	Неотсортированный
Время поиска/вставки/удаления (среднее)	O(log N)	O(1)
Время поиска/вставки/удаления (худшее)	O(log N)	O(N)
Требования к типу	Оператор <	std::hash, operator==

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

#include <iostream>
#include <set>

int main() {
    std::set<int> ordered_set;
    ordered_set.insert(5);
    ordered_set.insert(2);
    ordered_set.insert(8);

    // Элементы выведутся в отсортированном порядке: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> unordered_set;
    unordered_set.insert(5);
    unordered_set.insert(2);
    unordered_set.insert(8);

    // Порядок вывода может отличаться
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}