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