В чем разница между std::map и std::unordered_map в C++?

std::map:

• Хранит элементы в отсортированном порядке по ключам.
• Реализована на основе красно-черного дерева.
• Время доступа, вставки и удаления в среднем логарифмическое: O(log n).
• Ключи должны иметь оператор <.
• Подходит, когда важен упорядоченный обход элементов или частые операции поиска диапазона.

std::unordered_map:

• Не хранит элементы в каком-либо определенном порядке.
• Реализована на основе хэш-таблицы.
• Среднее время доступа, вставки и удаления: O(1). В худшем случае (при плохом хэшировании и большом количестве коллизий): O(n).
• Ключи должны быть хэшируемыми (предоставлять хэш-функцию) и иметь оператор ==.
• Подходит, когда главный приоритет — быстрое присутствие (lookup) элементов по ключу и порядок неважен.

Сравнительная таблица: