std::map:
- Хранит элементы в отсортированном порядке по ключам.
- Реализована на основе красно-черного дерева.
- Время доступа, вставки и удаления в среднем логарифмическое: O(log n).
- Ключи должны иметь оператор
<.
- Подходит, когда важен упорядоченный обход элементов или частые операции поиска диапазона.
std::unordered_map:
- Не хранит элементы в каком-либо определенном порядке.
- Реализована на основе хэш-таблицы.
- Среднее время доступа, вставки и удаления: O(1). В худшем случае (при плохом хэшировании и большом количестве коллизий): O(n).
- Ключи должны быть хэшируемыми (предоставлять хэш-функцию) и иметь оператор
==.
- Подходит, когда главный приоритет — быстрое присутствие (lookup) элементов по ключу и порядок неважен.
Сравнительная таблица:
| Признак | std::map | std::unordered_map |
|---|
| Порядок | Сортированный | Неупорядоченный |
| Структура данных | Красно-черное дерево | Хэш-таблица |
| Средняя сложность | O(log n) | O(1) |
| Требования к ключу | Оператор < | Хэшируемость, == |
| Использование | Упорядоченный доступ, диапазоны | Быстрый поиск по ключу |
Пример использования std::map:
cpp
Пример использования std::unordered_map:
cpp