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

Что проверяют

Понимаете ли вы, что за двумя похожими интерфейсами стоят разные структуры данных с разными гарантиями. Следом обычно спрашивают, что происходит при коллизиях и рехешировании и какие требования контейнеры предъявляют к типу элемента.

Как отвечать

• устройство: std::set на практике реализован красно-чёрным деревом, std::unordered_set это хеш-таблица с корзинами-цепочками;
• сложность: у set поиск, вставка и удаление O(log n) гарантированно. У unordered_set O(1) в среднем и O(n) в худшем, когда много элементов попало в одну корзину;
• порядок: set обходится в отсортированном порядке и умеет диапазонные запросы через lower_bound и upper_bound. У unordered_set порядок не определён и может поменяться после рехеширования;
• требования к типу: для set нужен строгий слабый порядок (operator< или свой компаратор), для unordered_set пара std::hash<T> и operator==, согласованные между собой;
• итераторы: вставка в set итераторы не инвалидирует. Вставка в unordered_set может вызвать рехеширование, и тогда инвалидируются все итераторы, хотя ссылки и указатели на элементы остаются рабочими.

Рехеширование происходит, когда size() / bucket_count() превышает max_load_factor(), по умолчанию 1.0. Если размер известен заранее, вызовите reserve(n), и лишних перестроений не будет.

Как выбирать: нужен порядок, минимум, диапазоны или предсказуемое время каждой операции, берите set. Нужна только проверка «есть или нет» на больших объёмах, берите unordered_set. Для небольшого набора, который редко меняется, часто быстрее всего отсортированный std::vector с std::binary_search или std::flat_set из C++23: данные лежат в памяти подряд.

Где спотыкаются

Называют O(1) без оговорки «в среднем». Плохая хеш-функция или подобранные злоумышленником ключи превращают таблицу в список, а для публичного сервиса это вектор атаки.

Пишут свой std::hash для структуры, но забывают согласовать его с operator==: равные объекты с разным хешем ломают контейнер молча.

Уверены, что unordered_set всегда быстрее. На паре десятков элементов хеширование и промахи кэша по узлам съедают выигрыш, это надо мерить.