Когда выбирать std::map, а когда std::unorderedmap?
C++Уровень: ПрактикаSTL Containers & Iterators
Когда выбирать std::map, а когда std::unordered_map?
Подсказки
- Уточните типы, время жизни объектов и то, что определяется на этапе компиляции.
- Проверьте гарантии стандарта отдельно от поведения конкретного компилятора.
Ответ
map поддерживает упорядоченный обход и операции O(log n); типичная реализация — сбалансированное дерево, ключи сравниваются по порядку. unordered_map использует хеширование и равенство: операции в среднем O(1), в худшем случае O(n), порядок обхода не задан. map полезен для диапазонов, отсортированных результатов и предсказуемой худшей оценки; unordered_map — для быстрого поиска при хорошем хеше без требований к порядку. Расход памяти различается: узлы дерева против бакетов и элементов хеш-таблицы.
Материалы источника:
Источник и лицензия: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT · перевод: Quantoros