Самый эффективный ассоциативный контейнер с std :: string в качестве ключа?

Question

Я где-то читал, что std :: map с текущими компиляторами по-прежнему является самым эффективным ассоциативным контейнером в STL, даже с std :: unsorted_map, который - из того, что я где-то читал, я неуверен, где-- становится более эффективным в find (), только если есть много записей, например, более 40 тыс.

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

Короче говоря:

Если мне нужно выбрать ассоциативный контейнер с неизвестным количеством записей и с std :: string как ключи , что будет (по крайней мере в теории) более эффективным (по скорости) выбором для поиска?

Answer 1

Профиль, профиль, профиль ...

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

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

Answer 2

Если у вас 40 или более записей, строки (или списки элементов и т. Д.) Не должны использоваться в качестве ассоциативных ключей в стандартных контейнерах.Вместо этого гораздо раньше наступает момент, когда три или тройное дерево становятся лучшими вариантами.Оба из них могут создавать ассоциативные структуры, которые сравнивают каждый символ вашей строки (или элемент вашего списка и т. Д.) Один раз.Упорядоченные карты сравниваются в каждом узле (как и O (m log n) - размер строки m, n количество элементов), и неупорядоченные карты страдают от гораздо большего числа столкновений при этих размерах.

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