Чем unordered_map отличается от map? Что быстрее?

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

map подходит для обхода по порядку и запросов диапазона. unordered_map удобен для точечного поиска при хорошем распределении хешей; его накладные расходы зависят от числа корзин и загрузки.

Учитывайте стоимость сравнения или хеширования ключа, объём памяти и размер данных. rehash у unordered_map инвалидирует итераторы, хотя ссылки на сохраняющиеся элементы остаются действительными. Выбирайте по требуемым операциям и измерениям.