Какая сложность вставки, удаления и поиска элементов в структурах set и unordered_set и как они реализованы в C++

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

Понимаете ли вы разницу между деревом и хэш-таблицей глубже таблицы сложностей: что происходит с итераторами, памятью и худшим случаем. Следом часто спрашивают, когда unordered_set проиграет set и что такое рехэширование.

Как отвечать

• std::set: стандарт требует упорядоченность и логарифмические гарантии, а libstdc++, libc++ и MSVC реализуют это красно-чёрным деревом. insert, erase по ключу и find стоят O(log n) в худшем случае, erase по итератору амортизированно O(1). Обход идёт в отсортированном порядке, есть lower_bound и upper_bound;
• std::unordered_set: хэш-таблица с цепочками, массив корзин и узлы в каждой. В среднем O(1), в худшем O(n), когда ключи попадают в одну корзину;
• рехэширование: когда load_factor() превышает max_load_factor() (по умолчанию 1.0), таблица перестраивается. Это O(n) на одной вставке, все итераторы инвалидируются, хотя ссылки и указатели на элементы остаются валидными. Если размер известен заранее, вызовите reserve;
• итераторы set: вставка их не портит, удаление портит только итератор на удалённый элемент.

Дальше практика. Оба контейнера хранят элемент в отдельном узле, и обход плохо ложится в кэш. Для строк хэш считается по всей строке, поэтому на небольших наборах set или отсортированный std::vector с std::binary_search бывает быстрее. Когда нужна именно скорость хэш-таблицы, смотрят на реализации с открытой адресацией вроде boost::unordered_flat_set. С C++20 у обоих контейнеров есть contains.

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

Утверждают, что стандарт требует красно-чёрное дерево. Он требует интерфейс и сложности, а дерево это выбор реализаций.

Считают, что unordered_set всегда быстрее. Средний O(1) не учитывает стоимость хэша, промахи кэша и паузу на рехэширование.

Забывают про худший случай. std::hash для целых в libstdc++ возвращает само число, и подобранные ключи сваливаются в одну корзину. Для данных от пользователя это реальный вектор атаки.