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==).