В чем разница между std::map и std::unordered_map и кто быстрее работает

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

Знаете ли вы структуры внутри и понимаете ли, что «быстрее» зависит от размера и шаблона доступа.

Как отвечать

std::map это сбалансированное дерево поиска, обычно красно-чёрное. Ключи хранятся отсортированными, поиск, вставка и удаление за O(log n). Требует отношения строгого порядка, то есть operator< или свой компаратор.

std::unordered_map это хеш-таблица. Те же операции в среднем за O(1), в худшем случае за O(n) при массовых коллизиях. Требует std::hash для ключа и operator==. Порядок обхода не определён и меняется при перехешировании.

Кто быстрее: обычно unordered_map на поиске по ключу, но с оговорками, и они важнее самого ответа:

• на малом числе элементов (десятки) map часто выигрывает: вычисление хеша не бесплатно, а дерево из трёх уровней обходится быстрее;
• локальность памяти: unordered_map хранит корзины со списками узлов, каждый узел отдельная аллокация, отсюда промахи кэша. map тоже разбросан по памяти, но при переборе по порядку ведёт себя предсказуемее;
• плохая хеш-функция превращает O(1) в O(n). Для собственных типов хеш пишут сами, и это реальный источник деградации;
• перехеширование при росте стоит O(n), поэтому при известном размере вызывают reserve.

Когда map нужен независимо от скорости: требуется обход по возрастанию ключа, запросы по диапазону (lower_bound, upper_bound), поиск ближайшего значения, детерминированный порядок.

Про устойчивость ссылок: у map итераторы и ссылки остаются валидными при любых вставках. У unordered_map при перехешировании итераторы становятся недействительными, а ссылки и указатели на элементы остаются.

Вывод для собеседования: правильный ответ это «зависит, и я бы замерил на своих данных».

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

Отвечают «unordered_map всегда быстрее».

Не пишут хеш для своего типа и получают деградацию.

Полагаются на порядок обхода unordered_map.

Не знают про reserve и платят за перехеширование в цикле.