Есть ли преимущество использования карты над неупорядоченной картой в случае тривиальных ключей?

Если вы хотите сравнить скорость ваших реализаций std::map и std::unordered_map, вы можете использовать Google sparsehash проект, который имеет программу time_hash_map для их времени. Например, с gcc 4.4.2 на x86_64 Linux system

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

Я бы повторил примерно ту же точку GMan: в зависимости от типа использования, std::map может быть (и часто является) быстрее, чем std::tr1::unordered_map (используя реализацию, включенную в VS 2008 SP1).

есть несколько осложняющих факторов, чтобы иметь в виду. Например, в std::map, вы сравниваете ключи, что означает, что вы только когда-либо смотрите на достаточное количество начала ключа, чтобы различать правую и левую под-ветви дерева. По моему опыту, почти единственный раз, когда вы смотрите на весь ключ, если вы используете что-то вроде int, что вы можете сравнить в одной инструкции. С более типичным типом ключа, таким как std::string, вы часто сравниваете только несколько символов или около того.

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

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

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

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

меня заинтриговал ответ от @Jerry Coffin, который предположил, что упорядоченная карта будет демонстрировать увеличение производительности на длинных строках после некоторых экспериментов (которые можно загрузить с сайт Pastebin), я обнаружил, что это справедливо только для коллекций случайных строк, когда карта инициализируется отсортированным словарем (который содержит слова со значительным количеством префикса-перекрытия), это правило ломается, предположительно из-за увеличенного дерева глубина, необходимая для извлечения значения. Результаты показаны ниже, 1-ый столбец номера время вставки, 2-ое время выборки.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

Я бы просто указал на это... есть много видов unordered_map s.

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

и это то, что беспокоит меня больше всего с добавлением unordered_map к STL: им придется выбрать конкретную реализацию, поскольку я сомневаюсь, что они спустятся Policy дороге, и так мы будет застрять с реализацией для среднего использования и ничего для других случаев...

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

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

так что на данный момент я, как правило, предпочитают std::map или loki::AssocVector (для замороженных наборов данных).

не поймите меня неправильно, я хотел бы использовать std::unordered_map и я могу в будущем, но трудно "доверять" переносимости такого контейнера, когда вы думаете обо всех способах его реализации и различных исполнениях, которые в результате этого возникают.

хэш-таблицы имеют более высокие константы, чем обычные реализации карт, которые становятся значимыми для небольших контейнеров. Максимальный размер составляет 10, 100 или даже 1000 или больше? Константы те же, что и всегда, но O(log n) близко к O(k). (Помните, что логарифмическая сложность все еще действительно хорошо.)

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

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

существенные различия, которые на самом деле не были адекватно упомянуты здесь:

• map сохраняет итераторы для всех элементов стабильными, в C++17 вы даже можете перемещать элементы из одного map к другому без аннулирования недействительных итераторов для них (и если они правильно реализованы без какого-либо потенциального выделения).
• map тайминги для одиночных операций, как правило, более последовательны, так как они никогда не нуждаются в больших распределения.
• unordered_map используя std::hash как реализовано в libstdc++ уязвим для DoS, если подается с ненадежным вводом (он использует MurmurHash2 с постоянным семенем - не то, что посев действительно поможет, см. https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/).
• упорядочивание позволяет эффективно искать диапазон, например, перебирать все элементы с ключом >= 42.

Я недавно сделал тест, который делает 50000 слияния и сортировки. Это означает, что если строковые ключи одинаковы, объедините байтовую строку. И конечный результат должен быть отсортирован. Таким образом, это включает в себя поиск для каждой вставки.

на map реализации, занимает 200 мс, чтобы закончить работу. Для unordered_map + map, Она занимает 70 мс unordered_map вставка и 80 мс для map вставки. Таким образом, гибридная реализация на 50 мс быстрее.

мы должны подумать дважды, прежде чем мы используем map. Если вам нужно только отсортировать данные в конечном результате вашей программы, гибридное решение может быть лучше.

причины были даны в других ответах; вот еще один.

СТД::МАП (сбалансированное бинарное дерево) операции амортизированной o(зарегистрируйте N) и худшем случае o(зарегистрируйте N). std:: unordered_map (хэш-таблица) операции амортизируются O(1) и в худшем случае O(n).

Как это происходит на практике, так это то, что хэш-таблица "икота" каждый раз в то время с операцией O(n), которая может быть или не быть чем-то, что ваше приложение может терпеть. Если он не может терпеть это, вы бы предпочли std::map over std:: unordered_map.

в большинстве языков неупорядоченная карта (aka словари на основе хэша) является картой по умолчанию, однако в C++ вы получаете упорядоченную карту в качестве карты по умолчанию. Как это случилось? Некоторые люди ошибочно полагают, что комитет C++ принял это решение в своей уникальной мудрости, но правда, к сожалению, уродливее этого.

широко считал что C++ в конечном итоге с упорядоченной картой по умолчанию, потому что есть не слишком много параметров о том, как они могут быть реализованы. С другой рука, реализация на основе хэша имеет массу вещей, о которых нужно говорить. Так что чтобы избежать заторов в стандартизации они просто ладили С заказать карту. Примерно в 2005 году многие языки уже имели хорошие реализации реализации на основе хэша, и поэтому комитету было легче принять новые std::unordered_map. В идеальном мире std::map были бы неупорядоченными, и мы бы std::ordered_map как отдельный тип.

ниже два графика должны говорить сами за себя (источник):

резюме

предполагая, что заказ не важно:

• если вы собираетесь построить большую таблицу один раз и сделать много запросов, используйте std::unordered_map
• если вы собираетесь построить небольшую таблицу (может быть менее 100 элементов) и сделать много запросов, используйте std::map. Это потому, что читает на нем O(log n).
• если вы собираетесь изменить таблицу много, то может бытьstd::map это хороший вариант.
• если вы сомневаетесь, просто использовать std::unordered_map.

небольшое дополнение ко всему выше:

лучше использовать map, когда вам нужно получить элементы по диапазону, так как они отсортированы, и вы можете просто перебирать их от одной границы к другой.

от: http://www.cplusplus.com/reference/map/map/

"внутренне, элементы в карте всегда сортируются по ее ключу после определенного строгого критерия слабого упорядочения, указанного его внутренним объектом сравнения (типа Compare).

контейнеры map обычно медленнее, чем контейнеры unordered_map для доступа к отдельным элементам по их ключу, но они позволяют прямую итерацию на подмножествах на основе их порядка."