Как выбрать между картой и неупорядоченной картой?

Question

Как выбрать между картой и неупорядоченной картой?

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

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

предполагая, что я буду использовать STL unordered_map С haser по умолчанию Vs. map. строку-ключ.

если я собираюсь перебирать элементы, а не обращаться к отдельному элементу каждый раз, должен ли я предпочесть map?

639 4

dictionary c++stl data-structures

4 ответов:

Comments

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

ypnos · Accepted Answer · 2016-03-31 12:55:51

на практике, если память не вопрос, unordered_map всегда быстрее, если вы хотите получить доступ к одному элементу.

худший случай является теоретическим и связан с одним хэшем, учитывающим все элементы. Это не имеет практического значения. Элемент unordered_map становится медленнее, как только у вас есть по крайней мере журнал n элементов, принадлежащих к тому же хэшу. Это также не имеет практического значения. В некоторых особых случаях может использовать определенный алгоритм хэширования, который обеспечивает более равномерное распределение. Для обычных строк, которые не используют определенный шаблон, общие хэш-функции поставляются с unordered_map Так же хорошо.

если вы хотите пересечь карту (используя итераторы) в отсортированном виде, вы не можете использовать unordered_map. Наоборот,map не только позволяет это, но и может предоставить вам следующий элемент на карте, основанный на приближении ключа (см. lower_bound и upper_bound методов).

score 178 · Accepted Answer · 2012-12-10 13:26:39

                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|

Pubby · Accepted Answer · 2012-12-10 13:09:10

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

профиль, а затем решить. unordered_map обычно быстрее, но это зависит от случая.

в каких случаях он доберется до O (n)?

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

когда является ли карта более эффективной по времени, чем unordered_map? Это происходит, когда n мал?

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

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

zaufi · Accepted Answer · 2012-12-10 13:07:04

в каких случаях он доберется до O(n)?

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

какой контейнер я должен был выбрать, map или unordered_map?

это всегда вопросы требований и вид / количество данных у вас есть.

когда карта становится более эффективной по времени, чем unordered_map?

Это просто разные структуры. Вам лучше сделать chiose, чтобы использовать один из них в зависимости от ваших типичных случаев использования (принимая во внимание, какие данные у вас есть и их количество)

Это hppaen, когда n мало?

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