Когда следует использовать unordered_map, а не std:: map

Ответ 1

map

• Обычно используется с красно-черным деревом.
• Элементы сортируются.
• Относительно небольшое использование памяти (для хэш-таблицы не требуется дополнительная память).
• Относительно быстрый поиск: O (log N).

unordered_map

• Обычно реализуется с помощью хэш-таблицы.
• Элементы не отсортированы.
• Требуется дополнительная память для хранения хэш-таблицы.
• Быстрый поиск O (1), но постоянное время зависит от хеш-функции , которая может быть относительно медленной. Также имейте в виду, что вы можете встретить проблему .

Ответ 2

Сравните хеш-таблицу (undorded_map) с бинарным деревом (map), запомните свои классы CS и соответствующим образом настройте.

Карта хэша обычно имеет O (1) для поиска, карта имеет O (logN). Это может быть реальная разница, если вам нужно много быстрых поисков.

Карта хранит порядок элементов, что также полезно иногда.

Ответ 3

map позволяет перебирать элементы по-упорядоченному, но unordered_map нет.
Поэтому используйте std::map, когда вам нужно перебирать элементы на карте в отсортированном порядке.

Ответ 4

Причина, по которой вы выбрали одну из них, - это производительность. В противном случае они создали бы только std::map, так как он делает больше для вас:)

Используйте std::map, когда вам нужно автоматически сортировать элементы. Используйте std::unordered_map другие времена.

См. обоснование спецификации SGI STL с точки зрения сложности.

Ответ 5

unordered_map - O (1), но довольно высокие постоянные накладные расходы для поиска, вставки и удаления. map - O (log (n)), поэтому выбирайте сложность, которая наилучшим образом соответствует вашим потребностям. Кроме того, не все ключи могут быть помещены в оба вида карты.