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

Мне интересно, в каком случае я должен использовать unordered_map вместо std:: map.

Мне нужно использовать unorderd_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)), поэтому выбирайте сложность, которая наилучшим образом соответствует вашим потребностям. Кроме того, не все ключи могут быть помещены в оба вида карты.