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

Question

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

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

---

@ wesc: я уверен, что std :: map реализован STL, хотя я уверен, что std :: hash_map НЕ находится в STL (я думаю, что более старая версия Visual Studio поместила его в пространство имен stdext).

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

Answer 1

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

Answer 2

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

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

Попробуйте Boost.MultiIndex или Boost.Intrusive . Я не использовал это таким образом, но я думаю, что это возможно.

Answer 3

Увеличение документации неупорядоченных контейнеров

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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