Was ist eine gute Möglichkeit, einen Vektor * vorübergehend * zu sortieren?

Ich habe einen Std :: Vektor, den ich nach ausgewählten Algorithmen für bestimmte Operationen sortieren muss, aber den Rest der Zeit seinen ursprünglichen Zustand beibehalten muss (z. B. Artikel geordnet nach, als sie eingegeben wurden).Was ist eine gute Möglichkeit, einen Vektor * vorübergehend * zu sortieren?

Offensichtlich kann ich std :: copy verwenden, um einen temporären Vektor zu erstellen und das zu sortieren, aber ich frage mich, ob es einen besseren Weg gibt, möglicherweise durch Zeitstempeln der eingegebenen Elemente.

Prost

Quelle

2010-02-22 deworde

Warum? Sortierung ist "O (N log N)", ganz zu schweigen vom konstanten Faktor; Kopieren ist direkt 'N * sizeof (T) 'Speicher schreibt unter der Annahme von POD-Elementen. Außerdem könnte man die Kopierzeit vom Benchmarking leicht ausschließen. – kennytm

Unter der Annahme von POD-Elementen ist das Kopieren eine konstante Zeit (Hinweis: think * memcpy *) und ziemlich schnell. –

Kopieren ist nicht konstante Zeit, @Stingray. Ist Zustand). –

Sie könnten ein std :: vector erstellen, die alle Indizes des ersten Vektors hält. Sie können dann den Indexvektor nach Ihren Wünschen sortieren. Dies sollte schnell und vor allem bedeutet nicht, dass Sie den ersten Vektor kopieren müssen (was wahrscheinlich teurer ist!).

Quelle

2010-02-22 17:33:05 monoceres

+1 für schnellste Finger, passte mehr oder weniger die gleiche Antwort. –

Ich hätte ein altmodisches Malloc'd Array von Zeigern verwendet und qsort genannt, aber das funktioniert auch. – Joshua

@Joshua: Die meiste Zeit wird das besser funktionieren - qsort ist normalerweise ein bisschen langsamer als std :: sort. –

Jeder gegebene Vektor wird zu jeder Zeit in höchstens einer Richtung einsortiert.

Es gibt zwei Alternativen:

Kopie in einem temporären Vektor und Art, dass nach Wunsch. Wenn der Vektor nicht sehr groß ist und Sie nur wenig Platz haben, ist dies mit ziemlicher Sicherheit der beste Weg. Selbst wenn Sie sich Gedanken über die Leistung machen, werden die Kosten für das Erstellen einer Kopie geringer sein als die Sortierkosten, und wenn die Kosten für das Kopieren erheblich sind, wird die Sortierung viel langsamer sein als das Kopieren.

Alternativ könnten Sie einen Weg (der von Ihnen erwähnte Zeitstempel?) Behalten, um den Vektor wieder in die ursprüngliche Reihenfolge sortieren zu können. Dies wird langsam sein, da Sie dies nur tun möchten, wenn der Vektor sehr groß ist. Wenn Sie jedoch keinen temporären Vektor erstellen können, ist dies der einzige Weg, dies zu tun.

Quelle

2010-02-22 17:33:12

Kopieren kann teuer sein, wenn es kein Zeigervektor ist, hängt auch davon ab, wie die Kopie ctor implemented ist. –

@Binary Worrier: Ich denke, Davids Standpunkt ist, dass die Sortieroperation auf dem Vektor eine Reihe von Kopien erstellt, wenn Elemente verschoben werden. Wenn die Sortierung O (n log n) ist, ändert das Hinzufügen einer O (n) Kopieroperation anfänglich nicht die gesamte Zeitkomplexität. –

Wenn Kopieren teuer ist, dann ist das Sortieren mehr. Wie erwarten Sie einen sortierten Vektor, ohne jedes Element an seinen neuen Platz zu kopieren? (Eigentlich könnte der Kopierkonstruktor viel teurer sein als der Zuweisungsoperator, in diesem Fall ist es das Richtige, den Kopierkonstruktor zu reparieren. Ich denke nicht an irgendeinen Fall, in dem der Kopierkonstruktor so viel teurer sein sollte.) –

Welches Element Sie auch sortieren, Sie können es in eine Struktur mit mehreren Sortierfeldern einfügen.

struct someThing 
{ 
    int sortOrder1; 
    int sortOrder2; 
    ... 
    int sortOrderN; 
    //payload data object here 
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(oder vielleicht die Sortierreihenfolgen an der Basisstruktur fügen Sie selbst?)

Dann, wenn Sie die verschiedenen Sortierreihen berechnen müssen, können und erneut um Ihre Liste je nachdem, welche Art Ordnung Sie brauchen .

Quelle

2010-02-22 17:33:57 FrustratedWithFormsDesigner

Wenn Sie etwas Boost brauchen, können Sie die MultiIndex-Bibliothek verwenden. Siehe this answer von mir, wo Sie einen Beispielcode finden.

Im Grunde erlaubt es Ihnen, mehrere "Ansichten" der gleichen Daten zu speichern, jede mit einer anderen Reihenfolge. In Ihrem Fall können Sie eine "Sequenz" -Ansicht behalten, in der die Daten in der Reihenfolge der Einfügung sind (wie ein Vektor) und eine "sortierte" Ansicht, in der die Daten nach einem Kriterium sortiert sind (wie eine Karte) .

Quelle

2010-02-22 17:42:22 Manuel

Ich empfehle, intelligente Zeiger zu den ursprünglichen Daten in jedem vector zu speichern. std::vector können Sie verschiedene Methoden zum Sortieren liefern. Mit intelligenten Zeigern werden sie automatisch gelöscht, wenn alle Referenzen auf das Objekt entfernt werden.

Quelle

2010-02-22 18:12:46

Was ist eine gute Möglichkeit, einen Vektor * vorübergehend * zu sortieren?

Antwort

Verwandte Themen