std::map — ассоциативный контейнер, хранящий пары "ключ-значение", отсортированные по ключу. Основан на красно-черном дереве. Время доступа, вставки и удаления элементов логарифмическое (O(log n)).
std::unordered_map — ассоциативный контейнер, хранящий пары "ключ-значение" в хэш-таблице. Элементы не отсортированы. В среднем время доступа, вставки и удаления элементов константное (O(1)), но в худшем случае может быть линейным (O(n)) при наличии коллизий. Требует наличия хэш-функции для типа ключа и оператора сравнения на равенство (operator==).
| Характеристика | std::map | std::unordered_map |
|---|---|---|
| Основа | Красно-черное дерево | Хэш-таблица |
| Сортировка элементов | По ключу | Нет |
| Средняя сложность операций (доступ, вставка, удаление) | O(log n) |
std::map — ассоциативный контейнер, хранящий пары "ключ-значение", отсортированные по ключу. Основан на красно-черном дереве. Время доступа, вставки и удаления элементов логарифмическое (O(log n)).
std::unordered_map — ассоциативный контейнер, хранящий пары "ключ-значение" в хэш-таблице. Элементы не отсортированы. В среднем время доступа, вставки и удаления элементов константное (O(1)), но в худшем случае может быть линейным (O(n)) при наличии коллизий. Требует наличия хэш-функции для типа ключа и оператора сравнения на равенство (operator==).
| Характеристика | std::map | std::unordered_map |
|---|---|---|
| Основа | Красно-черное дерево | Хэш-таблица |
| Сортировка элементов | По ключу | Нет |
| Средняя сложность операций (доступ, вставка, удаление) | O(log n) |
Register or sign in to get access to full answers for all questions from the question bank.