Ich verstehe nicht, std::tr1::unordered_map

Question

Ich brauche eine assoziative container, macht mich index ein bestimmtes Objekt, das durch einen string, aber das hält auch den Auftrag von einfügen, damit ich sehen kann für ein bestimmtes Objekt über seinen Namen oder einfach nur Durchlaufen, auf und abrufen von Objekten in der gleichen Reihenfolge, die ich eingefügt Ihnen.

Ich denke, dass dieses hybrid-verkettete Listen und hash-Karte sollte die Arbeit tun, aber bevor ich versucht zu verwenden std::tr1::unordered_map denken Sie, dass es funktioniert, in, dass Weg, den ich beschrieben, war es aber nicht.So könnte jemand erklären Sie mir den Sinn und das Verhalten der unordered_map?

---

@wesc:Ich bin mir sicher, dass std::map implementiert STL, während ich bin sicher, dass std::hash_map ist NICHT in der STL (finde ich ältere version von Visual Studio setzen Sie Sie in einen namespace mit dem Namen stdext).

@Christoph:also, wenn ich es richtig, der Unterschied liegt in der Implementierung (und damit Leistungen), nicht in der Weise verhält es sich nach außen.

Answer 1

Boost-Dokumentation von ungeordneten Behältern

Der Unterschied liegt in der Methode, wie man erzeugen die nach oben schauen.

In der Karte anzeigen/festlegen Behälter der operator< wird verwendet, um eine geordnete Struktur.

In den ungeordneten Containern, eines operator( key ) => index verwendet wird.

Siehe hashing-eine Beschreibung, wie das funktioniert.

Answer 2

Sie haben gefragt, für die kanonischen Grund, warum Boost::MultiIndex gemacht wurde:Liste einfügen, um mit der schnell-Suche nach Schlüssel. Boost MultiIndex-tutorial:Liste schnelle lookup

Answer 3

Sie müssen den index eines assoziativen container zwei Möglichkeiten:

• Insertion order
• String Vergleich

Versuchen Sie es Boost.MultiIndex oder Boost.Aufdringlich.Ich habe nicht verwendet es auf diese Weise, aber ich denke, es ist möglich.

Answer 4

Sorry, lese deine Letzte Bemerkung falsch.Ja, hash_map ist nicht in der STL-map.Aber unordered_map und hash_map sind, das gleiche von dem, was ich gelesen habe.

Karte -> log (n) insertion, retrieval, iteration ist effizient (und bestellt key comparison)

hash_map/unordered_map -> konstanter Zeit einfügen und abrufen, iteration, Zeit ist nicht Garantie zu sein, effizient

Weder diese Arbeit für Sie von selbst, da die map ordnet die Dinge basierend auf die Taste Inhalt, und nicht die insertion sequence (es sei denn, Ihr Schlüssel enthält info über das einfügen-Sequenz enthält).

Sie haben entweder zu tun, was Sie beschrieben haben (Liste + hash_map), oder erstellen Sie ein Schlüssel-Typ, der die insertion sequence number zuzüglich einer angemessenen Vergleich-Funktion.

Answer 5

Ich denken dass eine unordered_map und hash_map sind mehr oder weniger die gleiche Sache.Der Unterschied ist, dass die STL nicht offiziell eine hash_map (was Sie verwenden, ist wahrscheinlich eine compiler-spezifische Sache), so unordered_map ist die Lösung für die Lücke.

unordered_map ist nur, dass...ungeordnet.Sie können nicht hängen es unter Beibehaltung der Bestellung auf iteration.

Answer 6

Sie sicher, dass std::hash_map existiert in alle STL-Implementierungen?SGI STL implementiert, jedoch GNU-g++ nicht haben es (Sie liegt in __gnu_cxx namespace) als 4.3.1 sowieso.Soweit ich weiß, hash_map hat immer nicht-standard, und jetzt tr1 liegt Festsetzung.

Answer 7

@wesc:STL hat std::map...also, was ist der Unterschied mit unordered_map?Ich glaube nicht, dass STL umsetzen würden zweimal die selbe Sache und nennen Sie es anders.