В чем разница между set и unordered_set в C++?

std::set хранит элементы отсортированными по возрастанию и обеспечивает логарифмическую сложность для операций поиска, вставки и удаления (O(log n)). Реализован на основе сбалансированного бинарного дерева (обычно красно-черного дерева).

std::unordered_set хранит элементы в хеш-таблице. Порядок элементов не гарантируется. Обеспечивает в среднем константное время для операций поиска, вставки и удаления (O(1)), но в худшем случае может достигать линейной сложности (O(n)) при коллизиях хеш-функции.

Ключевые различия:

• Порядок элементов: set – отсортирован, unordered_set – нет.
• Сложность операций (поиск, вставка, удаление): set – O(log n), unordered_set – в среднем O(1), в худшем O(n).
• Реализация: set – дерево, unordered_set – хеш-таблица.
• Требования к типу элементов: set требует наличия операции сравнения (operator<), unordered_set – наличия хеш-функции и операции сравнения на равенство (operator==).