Выбор между std:: map и std:: unordered_map

Ответ 1

Как уже упоминалось , map позволяет перебирать элементы отсортированным образом, но unordered_map - нет. Это очень важно во многих ситуациях, например, для отображения коллекции (например, адресной книги). Это также проявляется в других косвенных способах, таких как: (1) Начать итерацию с итератора, возвращаемого find(), или (2) существование функций-членов, таких как lower_bound().

Кроме того, я думаю, что существует некоторая разница в сложности поиска наихудшего случая.

• Для map это O (lg N)

• Для unordered_map это O (N) [Это может случиться, когда хеш-функция не хороша, что приводит к слишком большому числу хэш-коллизий.]

То же самое применимо для сложности удаления наихудшего случая.

Ответ 2

В дополнение к приведенным выше ответам вы также должны заметить, что только потому, что unordered_map - постоянная скорость (O(1)), не означает, что она быстрее, чем map (порядка log(N)). Константа может быть больше, чем log(N), особенно, поскольку N ограничена 2 ³² (или 2 ⁶⁴).

Таким образом, в дополнение к другим ответам (map поддерживает порядок, а хеш-функции могут быть трудными), может быть, что map более совершенен.

Например, в программе, которую я запускал для сообщения , я увидел, что для VS10 std::unordered_map было медленнее, чем std::map (хотя boost::unordered_map был быстрее, чем оба).

Заметьте от 3-го по 5-й бары.

Ответ 3

Я думаю, что очевидно, что вы использовали бы std::map, чтобы перебирать элементы на карте в отсортированном порядке.

Вы также можете использовать его, если вы предпочитаете писать оператор сравнения (который является интуитивным) вместо хеш-функции (что обычно очень неинтуитивно).

Ответ 4

_{Это из-за Google Chandler Carruth в его лекции CppCon 2014}

std::map (считается многими) не полезен для работы, ориентированной на производительность: если вам нужен O (1) -амортированный доступ, используйте правильный ассоциативный массив (или из-за отсутствия одного, std::unorderded_map); если вы хотите отсортировать последовательный доступ, используйте что-то на основе вектора.

Кроме того, std::map является сбалансированным деревом; и вы должны пройти его или перебалансировать, невероятно часто. Это операции кэширования и кэширования-апокалипсиса соответственно... поэтому просто скажите NO std::map.

Вам может быть интересно этот вопрос SO об эффективных реализациях хэш-карты.

(PS - std::unordered_map является недружественным в кэше, потому что он использует связанные списки как ведра.)

Ответ 5

Скажите, что у вас очень большие ключи, возможно, большие строки. Чтобы создать хеш-значение для большой строки, вам нужно пройти всю строку от начала до конца. Это займет как минимум линейное время на длину ключа. Однако при поиске только двоичного дерева с помощью оператора > ключа каждое сравнение строк может возвращаться, когда найдено первое несоответствие. Это обычно очень рано для больших строк.

Это рассуждение может быть применено к функции find от std::unordered_map и std::map. Если характер ключа таков, что для получения хэша требуется больше времени (в случае std::unordered_map), чем требуется для определения местоположения элемента с использованием двоичного поиска (в случае std::map), он должен быстрее найти ключ в std::map. Очень легко думать о сценариях, где это было бы так, но на практике они будут довольно редко встречаться.