Dynamisch sortiert STL-Containern

StackOverflow https://stackoverflow.com/questions/67426

  •  09-06-2019
  •  | 
  •  

Frage

ich in die STL ziemlich neu bin, so dass ich frage mich, ob es irgendwelche dynamisch sortierbar Behälter sind? Im Moment sind meine derzeitigen Überlegungen einen Vektor in Verbindung mit den verschiedenen Sortieralgorithmen zu verwenden, aber ich bin mir nicht sicher, ob es eine entsprechende Auswahl der (vermutlich) lineare Komplexität des Einsetzens Einträge in eine sortierten Vektor gegeben.

„dynamisch“ Um zu klären, ich bin auf der Suche für einen Behälter, den ich die Sortierreihenfolge zur Laufzeit geändert werden kann - zum Beispiel sortiert sie in aufsteigender Reihenfolge, dann später neu zu sortieren in absteigender Reihenfolge.

War es hilfreich?

Lösung

Wenn Sie wissen, dass Sie auf einem einzigen Wert aufsteigend zu sortieren und absteigend, dann gesetzt ist dein Freund. Verwenden Sie einen Reverse-Iterator, wenn Sie wollen „sort“ in der entgegengesetzten Richtung.

Wenn Sie Ihre Objekte komplex sind und Sie gehen auf viele verschiedene Arten auf die Mitglieds Felder innerhalb der Objekte zu beruhen Sortierung, dann sind Sie wahrscheinlich besser dran mit einem Vektor und sortieren. Versuchen Sie, Ihre Einsätze auf einmal zu tun, und dann sortieren einmal anrufen. Wenn das nicht möglich ist, dann für große Sammlungen von Objekten deque kann eine bessere Option als der Vektor sein.

Ich glaube, wenn Sie daran interessiert sind in , die Optimierungsgrad, sollten Sie besser Ihren Code werden Profilierungs tatsächlichen Daten. (Das ist wahrscheinlich der beste Rat jemand hier geben kann. Es kann keine Rolle, dass Sie nach jedem Einsatz sortieren rufen, wenn Sie es nur einmal in einem blauen Mond tun)

Andere Tipps

Sie werden std suchen möchten :: map 

std::map<keyType, valueType>

Die Karte sortiert basiert auf dem Operator

oder 

std::set<valueType>

Auch auf dem Operator

Es gibt 

std::multiset<valueType>

was macht das Gleiche wie std :: gesetzt, sondern ermöglicht identische Elemente.

I "The C ++ Standard Library" sehr empfehlen von Josuttis für weitere Informationen. Es ist die umfassendste Übersicht über die std Bibliothek, sehr gut lesbar, und voll von dunklen und nicht so obskuren Informationen.

Auch nach 17 von 26 erwähnt wie effektive Stl von Meyers ist lesenswert.

Es klingt wie Sie einen Multi-Index wollen Container . Auf diese Weise können Sie einen Container erstellen und dieser Behälter die verschiedenen Möglichkeiten, sagen Sie können die Elemente in es zu durchqueren. Der Behälter hält dann mehrere Listen der Elemente, und diese Listen werden auf jedem Einsatz aktualisiert / gelöscht werden.

Wenn Sie wirklich den Behälter neu sortieren möchten, können Sie die std::sort Funktion auf jedem std::deque, std::vector, oder sogar einem einfachen C-style-Array. Diese Funktion nimmt ein optionales drittes Argument, um zu bestimmen, wie der Inhalt zu sortieren.

Die stl bietet keinen solchen Behälter. Sie können Ihre eigenen, unterstützt von entweder einem set/multiset oder vector definieren, aber Sie gehen zu müssen, jedes Mal, wenn die Sortierfunktion Änderungen entweder telefonisch sort neu zu sortieren (für eine vector) oder durch Erstellen einer neuen Kollektion (für set/multiset) .

Wenn Sie nur von ändern mögen steigende Sortierreihenfolge Sortierreihenfolge zu abnimmt, können Sie den Reverse-Iterator auf dem Behälter durch den Aufruf rbegin() und rend() statt begin() und end() verwenden können. Sowohl vector und set/multiset sind reversible Behälter, so würde dies entweder arbeiten.

std::set ist im Grunde ein sortierter Behälter.

Sie sollten auf jeden Fall einen Satz / Karte verwenden. Wie hazzen sagt, erhalten Sie O insert / finden (n log). Sie werden nicht mit einem sortierten Vektor erhalten; Sie können mit O (log n) binäre Suche erhalten finden, aber Insertion ist O (n), weil das Einfügen (oder Löschen) ein Element alle vorhandenen Elemente im Vektor kann dazu führen, verschoben werden.

Es ist nicht so einfach. Meiner Erfahrung nach Einfügen / Löschen wird weniger häufig verwendet als finden. Vorteil des sortierten Vektor ist, dass es dauert weniger Speicher und ist mehr Cache freundlich. Wenn passieren Version haben, die mit STL-Karten (wie ich sie zuvor verknüpft) kompatibel ist es einfach hin und her wechseln und für jede Situation optimal Behälter verwenden.

in der Theorie ein assoziativer Container (set, multiset, Karte, multimap) sollte Ihre beste Lösung sein.

In der Praxis kommt es durch die durchschnittliche Anzahl der Elemente, die Sie in setzen. für weniger als 100 Elemente ist ein Vektor wahrscheinlich die beste Lösung durch: - Vermeidung kontinuierliche Zuweisung-Freigabe - Cache freundlich durch Datenlokalität Diese Vorteile werden wohl doch kontinuierliche Sortierung übertreffen. Offensichtlich hängt es auch ab, wie viele einschub deletation Sie zu tun haben. Werden Sie pro Frame Insertion / deletation tun?

Generell: sprechen Sie über eine leistungskritische Anwendung

denken Sie daran, nicht vorzeitig zu optimieren ...

Die Antwort ist wie immer es abhängig ist.

set und multiset sind für Elemente sortiert zu halten, sind aber für eine ausgewogene Gruppe von Add allgemein optimiert, entfernen und holen. Wenn Sie männlich Suchoperationen haben dann eine sortierte vector besser geeignet sein können und dann lower_bound verwenden Sie das Element zum Nachschlagen.

Auch Ihre zweite Anforderung an in einer anderen Reihenfolge zur Laufzeit zurückzugreifen bedeutet eigentlich, dass set und multiset nicht geeignet ist, weil das Prädikat nicht eine Laufzeit geändert werden kann.

würde ich daher eine sortierte Vektor empfehlen. Aber denken Sie daran das gleiche Prädikat passieren lower_bound, dass Sie zur vorherige Art bestanden, da die Ergebnisse nicht definiert werden und höchstwahrscheinlich falsch, wenn Sie das falsche Prädikat übergeben.

Set und multiset Verwendung einen zugrunde liegenden binären Baum; Sie können den <= Operator für den eigenen Gebrauch definieren. Diese Behälter halten sie sortieren, damit vielleicht nicht die beste Wahl, wenn Sie Sortierparameter wechseln. Vektoren und Listen sind wahrscheinlich am besten, wenn Sie ziemlich viel gehen, gekommen zu sein; im allgemeinen Liste hat eigene Art ist es (in der Regel ein mergesort) und Sie den stl binären Suchalgorithmus auf Vektoren verwenden können. Wenn Einsätze dominieren, Liste trifft Vektor.

STL Karten und Sets sind beide sortiert Container.

Ich zweite Doug T Buch Empfehlung - die Josuttis STL Buch ist das Beste, was ich jemals sowohl als Lern- und Nachschlagewerk gesehen haben

.

Effective STL ist auch ein hervorragendes Buch zum Erlernen der inneren Details STL und was Sie sollten und nicht tun sollten.

Für "STL-kompatibel" sortiert Vektor siehe A. Alexandrescu des AssocVector von Loki .

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top