Выбор между использованием std::map и std::неупорядоченный карте

Question

Выбор между использованием std::map и std::неупорядоченный карте

теперь std имеет реальную хэш-карту в unordered_map, почему (или когда) я все еще хочу использовать старый добрый map over unordered_map в системах, где он существует? Есть ли очевидные ситуации, которые я не могу сразу увидеть?

824 5

c++c++11 map hash

5 ответов:

Comments

Ничего не найдено.

Arun · Accepted Answer · 2017-05-23 15:03:02

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

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

на map, Это O (lg N)

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

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

Motti · Accepted Answer · 2016-03-21 13:09:00

в дополнение к ответам выше вы также должны отметить, что только потому, что 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-й бары.

einpoklum · Accepted Answer · 2017-05-23 15:34:39

_{это связано с Carruth Гугл Чендлер в его CppCon 2014 лекция}

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

и std::map - это сбалансированное дерево, и вы должны пересечь его, или ре-баланс это невероятно часто. Это операции Cache-killer и cache-apocalypse соответственно... так что просто скажи "нет"std::map.

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

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

Ken Bloom · Accepted Answer · 2010-10-11 02:32:06

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

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

Martin G · Accepted Answer · 2016-08-19 23:22:45

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

это рассуждение может быть применено к