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

Question

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

Я думаю, что это hybrid of linked list and hash map должно выполнить эту работу, но прежде чем я попытался использовать std::tr1::unordered_map, думая, что он работает таким образом, я описал это, но это не так. Так может кто-нибудь объяснить мне смысл и поведение unordered_map?

---

@wesc: Я уверен, что станд :: Карта осуществляется STL, в то время как я уверен, что станд :: hash_map НЕ в STL (я думаю, что более ранняя версия Visual Studio положить его в пространстве имен называемый stdext).

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

Answer 1

Boost documentation of unordered containers

Разница заключается в способе, как вы генерировать взгляд вверх.

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

карта -> журнал (п) вставка, поиск, итерация является эффективной (и по заказу сравнения ключей)

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

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

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

Answer 6

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

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

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

Answer 7

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