К содержанию
Quantoros

Когда выбирать 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

Похожие вопросы