Я не понимаю std::tr1::unordered_map

Question

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

Я думаю, что это гибрид связанного списка и хэш-карты должен выполнить эту работу, но до того, как я попытался использовать std::tr1::unordered_map я думал, что это работает именно так, как я описал, но это было не так.Итак, не мог бы кто-нибудь объяснить мне значение и поведение unordered_map?

---

@wesc:Я уверен, что std::map реализован STL, в то время как я уверен, что std:: hash_map ОТСУТСТВУЕТ в STL (я думаю, что более старая версия Visual Studio поместила его в пространство имен с именем stdext).

@кристофер:итак, если я правильно понимаю, разница заключается в реализации (и, следовательно, в производительности), а не в том, как она ведет себя внешне.

Answer 1

Повышение документации по неупорядоченным контейнерам

Разница заключается в методе генерации поиска.

В контейнерах map / set operator< используется для создания упорядоченного дерева.

В неупорядоченных контейнерах используется operator( key ) => index.

См. хэширование для описания того, как это работает.

Answer 2

Вы спросили, по какой канонической причине был создан Boost :: MultiIndex: порядок вставки списка с быстрым поиском по ключу. Руководство по ускорению MultiIndex: быстрый просмотр списка

Answer 3

Вам нужно проиндексировать ассоциативный контейнер двумя способами:

• Порядок вставки
• Сравнение строк

Попробуй Повышение.Мультииндекс или Повышение.Навязчивый.Я не использовал его таким образом, но я думаю, что это возможно.

Answer 4

Извините, прочитайте ваш последний комментарий неправильно. Да, hash_map отсутствует в STL, карта есть. Но unordered_map и hash_map совпадают с тем, что я читал.

карта - > log (n) вставка, поиск, итерация эффективны (и упорядочены путем сравнения ключей)

hash_map / unordered_map - > постоянное время вставки и извлечения, время итерации не гарантирует эффективности

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

Вам нужно будет либо выполнить то, что вы описали (list + hash_map), либо создать тип ключа с порядковым номером вставки и соответствующей функцией сравнения.

Answer 5

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

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

Answer 6

Вы уверены, что std :: hash_map существует во всех реализациях STL? SGI STL реализует его, однако в GNU g ++ его нет (он находится в пространстве имен __gnu_cxx) в 4.3.1 в любом случае. Насколько я знаю, hash_map всегда был нестандартным, и теперь tr1 исправляет это.

Answer 7

@wesc: STL имеет std :: map ... так в чем же разница с unordered_map? Я не думаю, что STL реализовал бы дважды одно и то же и назвал бы это по-другому.