Mit anderen Worten, wenn ich zwei unordered_map, oder unordered_set, Objekte mit genau dem gleichen Inhalt und der gleichen Hashing-Funktion fülle, gibt die Iteration über sie die gleiche Folge von Schlüssel/Wert-Paaren?Ist die Reihenfolge von zwei gleichen unordered_maps gleich?
Wenn ja, was sind die Bedingungen dafür (z. B. gleiche Hash-Funktion, gleiche Schlüssel, nicht unbedingt die gleichen Werte).
Nein, es gibt keine Anforderung, beispielsweise gemeinsam, dass Objekte, die den gleichen Hash haben in einer bestimmten Reihenfolge angeordnet werden. Tatsächlich ist es für eine ungeordnete Karte im Allgemeinen unmöglich, dies zu tun, da die einzige Information, auf die sie zugreifen kann, der Hash-Wert ist.
Wenn Sie Elemente mit denselben Schlüsseln in der gleichen Reihenfolge mit der gleichen Hash-Funktion in derselben Containergröße hinzufügen (d. H. Nichts mit "Reserve" oder was auch immer tun), was könnte sie anders angeordnet werden? –
Ja, also ... darum bitte ich. Obwohl es nicht spezifiziert ist, wird es in der Praxis tatsächlich spezifiziert, oder? :) – pms
@SethCarnegie: Zuerst sagte das OP nicht, dass sie in der gleichen Reihenfolge hinzugefügt werden würden. Zweitens könnte alles dazu führen, dass sie anders geordnet werden. Die Implementierung könnte, falls gewünscht, sie zufällig anordnen oder sogar neu anordnen, um die am häufigsten verwendeten Objekte zuerst in ihren Hash-Ketten zu platzieren. –
Das Verhalten ist in diesem Fall nicht definiert. In einigen Situationen wird die Reihenfolge also gleich sein, in anderen - anders. Sie können in nichts sicher sein. Die von Ihnen erwähnten Typen heißen ungeordnet nicht zufällig. Sie als bestellte zu verwenden ist ein sehr sehr schlechter und extrem gefährlicher Stil.
Sie können feststellen, dass sich Ihr Compiler auf eine spezielle Weise verhält, die Sie verwenden möchten. Aber du kannst dir nicht sicher sein. Du musst nicht sicher sein! Sie wissen nicht, welche Bedingungen ein solches Verhalten des Compilers verursachen. Sie können nie sicher sein, dass eine Änderung der Compiler-Version das von Ihnen benötigte Verhalten nicht ändert.
Was in anderen Sprachen einfach verboten ist, in C/C++ ist nicht angegeben. Aber du solltest es auch als verboten ansehen.
Blick c-faq about the problem of undefined behavior Dieses Konzept ist für alle C/C++
Ja .. aber von dem, was ich [hier] lesen kann (http://stackoverflow.com/questions/3176621/c-is-the-unordered-map-really-ordered) scheint es, dass es möglich ist ... – pms
Es ist möglich, so zu geschehen. Aber es ist möglich, so nicht zu geschehen. Was in anderen Sprachen einfach verboten ist, ist in C/C++ nicht angegeben. Aber du solltest es auch als verboten ansehen. – Gangnus
@pms: Was "ungeordnet" bedeutet, ist "unzuverlässig geordnet". Dies bedeutet, dass die * C++ - Spezifikation * keinen Auftrag definiert. Ihre Implementierung von 'std :: unordered_ *' kann tatsächlich eine konsistente Reihenfolge haben. Aber die Spezifikation erzwingt das nicht. Während es eine bestimmte Reihenfolge auf "std :: map" erzwingt. Wenn Sie also möchten, dass Ihr Code portabel ist, können Sie sich nicht auf die Bestellung verlassen. –
Well Zuerst werde ich MSDN zitieren:
Die tatsächliche Reihenfolge der Elemente in der gesteuerten Sequenz auf der Hash-Funktion abhängt, die Vergleichsfunktion, die Reihenfolge der Einfügung des maximalen Lastfaktor, und die aktuellen Anzahl von Eimern. Sie können die Reihenfolge der Elemente in der kontrollierten Sequenz im Allgemeinen nicht vorhersagen. Sie können jedoch immer sicher sein, dass jede Teilmenge von Elementen mit äquivalenter Ordnung in der kontrollierten Sequenz benachbart ist.
Das obige Zitat ist für unordered_map und unordered_set und wie der Name schon sagt die Sequenz nicht spezifiziert ist, aber sie erwähnen, dass äquivalente Tasten benachbart sind.
Ich denke, das ist nur für MS-Implementierung, oder? Oder ist es eine Anforderung in der Norm? Es scheint so, als würde dies Implementierungen dazu zwingen, lineares Antasten für Kollisionen zu verwenden (oder jedes Element in einem indirekten dynamischen Array zu speichern). –
@SethCarnegie: Es scheint erforderlich, ich fand eine Diskussion [hier] (https://groups.google.com/group/comp.std.c++/tree/browse_frm/month/2006-11/19fc7cb847e9127b?rnum = 1 & _done =/group/comp.std.c% 2B% 2B/browse_frm/Monat/2006-11? & Hl = pt) (siehe Beitrag 6). –
Wenn Sie eine garantierte Bestellung benötigen, ist dies nicht die Datenstruktur für Sie. In der Tat, wenn Sie hauptsächlich Iteration machen, ist unordered_map/set nicht die Datenstruktur für Sie, entweder.
Für die Iteration wird sich eine std::map als die bessere Datenstruktur erweisen, da gonig von einem Knoten zum nächsten weniger algorithmisch komplex ist. Und die Reihenfolge der Iteration für die Objekte in std::mapist garantiert durch die Spezifikation (und ist eigentlich eine definierende Eigenschaft der Struktur selbst). (Dies setzt voraus, dass Sie natürlich denselben Vergleichsoperator verwenden). In std::map ist kein Hashing beteiligt.
Es genügt zu sagen, es klingt, als ob Sie hier den falschen Baum bellen. unordered_map sollte im Allgemeinen für die Vorteile wie O (1) Lookup verwendet werden und nicht zum Speichern einer Liste von Objekten, die dann über sie iterieren. Es definitiv sollte nicht verwendet werden, wenn Sie versuchen, eine deterministische Reihenfolge der Iteration zu erhalten.
Die Hash-Funktion, an die Sie denken, ist nicht die endgültige Hash-Funktion, die verwendet wird. Die Bucket-Größe kann sich dynamisch ändern, und die tatsächliche Hash-Funktion wird * von Ihrer Hash-Funktion abgeleitet (vermutlich in einer Art von Modular-Arithmetik). –