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