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 реализует ассоциативный массив на основе красно-черного дерева. Элементы хранятся в отсортированном порядке по ключу. Операции вставки, удаления и поиска имеют логарифмическую сложность (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) и == оператор сравнения |
| Использование п |
Зарегистрируйтесь или войдите, чтобы получить доступ к полным ответам на все вопросы из банка вопросов.