wie beachtet der multimap-einschub der stl die ordnungen?

Question

Ich habe einige Daten, die mit einem ganzzahligen Index kommen. Ich erschaffe ständig neue Daten, die zu der Sammlung von Daten, die ich habe, hinzugefügt werden müssen, sortiert nach diesem Index, gleichzeitig möchte ich leicht in der Lage sein, den Anfang der Daten zu machen und sie zu durchlaufen. Das klingt wie std :: multimap ist genau das, was ich brauche.

Ich brauche aber auch Daten mit dem gleichen Index in der Reihenfolge, in der es eingefügt wurde, in diesem Fall bedeutet, dass, wenn ich durch die Daten iteriere ich die früheren Daten vor den späteren Daten.

Macht dies multimap?

Ich habe keine Garantien gefunden, dass dies der Fall ist. Im SGI-Handbuch habe ich nicht erwähnt, ob. Ich habe es auf der gcc 4.3.4-Implementierung versucht und es schien für einige begrenzte Testfälle wahr zu sein, aber natürlich fragte ich mich, ob der Standard dies erfordert und ich kann mich auf diese Tatsache verlassen.

Bearbeiten: Um in Antwort auf einige der Antworten klarer zu sein, wollte ich die Daten zuerst nach (nicht eindeutigen) Index und zweitens nach Einfügezeit sortiert. Ich hatte gehofft, dass vielleicht der zweite Teil kostenlos mit Multimap kam, aber es scheint so, als ob es nicht wäre.

Answer 1

Sofern ich etwas nicht verpasst habe, bietet der Standard keine solche Garantie.

Die offensichtlichste Problemumgehung wäre, eine Sequenznummer als Sekundärschlüssel einzubeziehen. Fügen Sie in Ihrer Klasse z. B. ein statisches vorzeichenloses long ein, und jedes Mal, wenn Sie ein Objekt zum Einfügen in die Multimap erstellen, geben Sie den aktuellen Wert in Ihr Objekt ein und inkrementieren Sie es. Verwenden Sie in der Vergleichsfunktion Ihres Objekts den Zähler als den entscheidenden Faktor für die Reihenfolge, wenn die Daten, die Sie derzeit als Schlüssel verwenden, gleich sind. Beachten Sie, dass in diesem Fall jeder Schlüssel eindeutig ist, sodass Sie eine Map anstelle einer Multimap verwenden können.

Answer 2

Nein, wird es nicht. Wenn Sie das wollen, sollten Sie einen "Sequenzcontainer" wie einen Vektor verwenden. Sie können zum Beispiel einen Vektor mit std :: pairs laden?

Answer 3

Es ist wie multimap klingt, ist, was Sie brauchen ...

Ich brauche aber Daten mit dem gleichen Index auch in der Reihenfolge, in gehalten werden, die es in diesem Fall Bedeutung eingeführt, dass, wenn ich durch iterate die Daten ich die früheren Daten vor den späteren Daten erhalten.

Es wird in der Reihenfolge des Index sein. Wenn der Index im Laufe der Zeit zunimmt, wenn Sie weitere Elemente einfügen, werden die "früheren" Daten aufgrund der Art Ihres Indexes zuerst angezeigt.

Ansonsten, nein. Sie könnten zwei Multimaps für dieselben Daten behalten. Ein gehalten, um den Index, der andere in der Reihenfolge der Einführungszeit:

std::multimap<index, T*> orderedByIndex; 
std::multimap<time, T*> orderedByInsertionTime; 

Gibt Ihnen die Möglichkeit, die Karte in beiden Richtungen durchlaufen.

() Bearbeiten Ich lese das zu bedeuten, dass Sie manchmal nach Index iterieren oder manchmal durch Insertionszeit iterieren, aber sehen Sie die obige Antwort, wenn Sie zuerst Index und dann Insertionszeit bedeuten.)

Answer 4

Die Elemente, die zu dem gleichen Schlüssel gehört von lower_bound und upper_bound Funktionen ordened, wenn Sie die Informationen abrufen, daher müssen Sie nicht die Garantie, dass Sie (von equal_range), um die Elemente in der Reihenfolge zugreifen wird, dass sie eingefügt.

Answer 5

Boost multi_index unterstützt, was Sie versuchen zu tun, wenn Sie nicht die von Jerry Coffin gegebene Problemumgehung nehmen möchten.

Answer 6

Wenn ich dich richtig verstanden habe - du brauchst die Daten nach einem Schlüssel sortiert. Immer wenn Sie zwei Dinge mit demselben Schlüssel einfügen, müssen Sie sie in der Reihenfolge des Einfügens abrufen.

Wenn das der Fall ist, dann müssen Sie sich die Implementierung Ihrer Multimap ansehen. Je nachdem, wie es den Fall von mehreren Einfügungen mit dem gleichen Schlüssel handhabt, kann es oder kann nicht diese Garantie haben. Ich schätze, der Standard bietet keine solche Garantie, da dies die Implementierung für einen speziellen Fall einschränken würde.

Ein weiterer Ansatz ist für eine Karte gehen (nicht Multi) und eine Verbindung Schlüssel erstellen. Der Schlüssel besteht aus dem normalen Schlüssel, den Sie wählen, und einem immer größer werdenden Zähler. Beim Vergleich mit gleichen Schlüsseln macht die Einfügungsnummer den Schlüssel einzigartig. Auf diese Weise erzwingen Sie eindeutige Schlüssel und die Reihenfolge auf gleichen "normalen" Schlüsseln (ich hoffe, das war verständlich).

Ich denke, der letzte Ansatz ist am einfachsten zu implementieren.

---

Option: (nicht bevorzugt)

können Sie immer für eine selbstgemachte Datenstruktur mit dieser Garantie. Ich würde für einen Baum (Rot-Schwarz oder AVL zum Beispiel) mit einem Vektor gehen, um die eingefügten Daten zu halten. Bei der Iteration müssen Sie den Knoten finden, zum Vektor gehen und auf seinen Inhalt iterieren. Wenn Sie mit dem Vektor fertig sind, fahren Sie mit dem nächsten Knoten fort.

Answer 7

Es scheint, den neuen Standard (C++ 11) änderte sich das:

Die Reihenfolge der Schlüsselwertpaare, deren Schlüssel vergleichen entspricht die Reihenfolge des Einsetzens und ändert sich nicht. ^{[cppreference]}

Ich zögere es aber zu verwenden, da dies wie ein Detail scheint leicht übersehen, wenn die Standard-Bibliothek zu modifizieren C++ 11-kompatibel sein und es ist die Art von Detail, die Fehler leise verursachen, wenn Die Bibliothek Ihres Compilers konnte nicht ordnungsgemäß implementiert werden.