Когда следует использовать 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:

c

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

c