Предположим, я хотел сопоставить данные со строкой в качестве ключа. Какой контейнер выбрать, mapили unordered_map? unordered_mapзанимает больше памяти, поэтому предположим, что память не является проблемой, а проблема заключается в скорости.
unordered_mapобычно должен давать среднюю сложность O (1) с наихудшим случаем O (n). В каких случаях он достигнет O (n)? Когда время mapстановится эффективнее, чем unordered_map? Бывает, когда n мало?
Предполагая, что я бы использовал STL unordered_mapсо стандартным haser Vs. карта. строка - это ключ.
Если я собираюсь перебирать элементы вместо того, чтобы каждый раз обращаться к отдельному элементу, что я должен предпочесть map?
c++
dictionary
data-structures
stl
unordered-map
StackHeapCollision
источник
источник
unordered_mapиспользует больше памяти?Ответы:
На практике, если память не проблема,
unordered_mapвсегда быстрее, если вам нужен доступ к одному элементу.Худший случай является теоретическим и связан с одним хешем, учитывающим все элементы. Это не имеет практического значения. Работа
unordered_mapстановится медленнее, если у вас есть хотя бы N элементов, принадлежащих одному хешу. Это тоже не имеет практического значения. В некоторых особых сценариях вы можете использовать определенный алгоритм хеширования, который обеспечивает более равномерное распределение. Для обычных строк, которые не имеют определенного шаблона, общие хеш-функцииunordered_mapтакже подходят.Если вы хотите перемещаться по карте (используя итераторы) отсортированным способом, вы не можете использовать
unordered_map. Напротив, этоmapне только позволяет, но также может предоставить вам следующий элемент на карте на основе приближенного значения ключа (см.lower_boundИupper_boundметоды).источник
| 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|источник
log(n)если у вас такая плохая хеш-функция, которая производит одно и то же хеш-значение для всех входных сигналов (то есть создает коллизии) ...
Это всегда вопросы требований и типа / количества имеющихся у вас данных.
Это просто разные конструкции. Лучше сделать выбор в пользу использования одного из них в зависимости от ваших типичных вариантов использования (с учетом того, какие данные у вас есть и их количество)
В случае небольшого количества данных все зависит от конкретной реализации STL ... Так что иногда даже простой вектор / массив может быть быстрее, чем ассоциативные контейнеры ...
источник
Профиль, а затем решайте.
unordered_mapобычно быстрее, но зависит от случая.Когда хеширование неудовлетворительное и несколько элементов назначаются одним и тем же ячейкам.
Наверное, нет, но опишите это, если вам действительно интересно. Использование контейнера небольшого размера в качестве узкого места вашей программы кажется крайне маловероятным. В любом случае простой
vectorлинейный поиск в таких случаях может оказаться более быстрым.Самое главное при принятии решения - это требования к порядку и отсутствие недействительности итератора. Если вам что-то нужно, вам в значительной степени придется воспользоваться
map. В противном случаеunordered_map.источник
std :: map Внутреннее хранение элементов в сбалансированном BST. Таким образом, элементы будут храниться в отсортированном порядке ключей.
std :: unordered_map хранит элементы с помощью хеш-таблицы. Следовательно, элементы не будут храниться ни в каком отсортированном порядке. Они будут храниться в произвольном порядке.
Использование памяти :
Использование памяти больше в unordered_map по сравнению с map, потому что unordered_map также требует места для хранения хеш-таблицы.
Сложность поиска элемента:
Сложность поиска элементов в std :: map равна O (log n). Даже в худшем случае это будет O (log n), потому что элементы хранятся внутри как сбалансированное двоичное дерево поиска (BST).
Принимая во внимание, что в std :: unordered_map лучшая временная сложность для поиска составляет O (1). Где, как, если функция хеш-кода не подходит, тогда сложность наихудшего случая может быть O (n)
источник