ALLE
Gibt es in STL einen sortierten Container? Was ich meine, ist folgendes:
Ich habe einen std :: Vektor wo Foo eine benutzerdefinierte Klasse ist. Ich habe auch einen Vergleicher, der die Felder der Klasse Foo vergleicht.
Nun, irgendwo in meinem Code mache ich:
%Vor%sortiert den Vektor nach den Regeln, die ich im Komparator definiert habe.
Nun möchte ich ein Element der Klasse Foo in diesen Vektor einfügen. Wenn ich könnte ich möchte nur schreiben:
%Vor%und was passieren würde ist, dass der Vektor dieses neue Element entsprechend dem Komparator an seinen Platz setzen wird.
Stattdessen muss ich jetzt schreiben:
%Vor%was nur eine Verschwendung von Zeit ist, da der Vektor bereits sortiert ist und alles was ich brauche ist, das neue Element passend zu platzieren.
Nun kann ich wegen der Art meines Programms nicht std :: map & lt; & gt; da ich keine Schlüssel / Wert-Paare habe, nur einen einfachen Vektor.
Wenn ich stl :: list verwende, muss ich nach jedem Einfügen erneut sortieren.
Vielen Dank für Ihre Vorschläge.
Ja, std::set , std::multiset , std::map , und std::multimap werden alle mit std::less als Standardvergleichsoperation. Die zugrunde liegende Datenstruktur ist typischerweise ein ausgewogener binärer Suchbaum, beispielsweise ein Rot-Schwarz-Baum. Wenn Sie also ein Element zu diesen Datenstrukturen hinzufügen und dann über die enthaltenen Elemente iterieren, wird die Ausgabe in sortierter Reihenfolge angezeigt. Die Komplexität des Hinzufügens von N Elementen zu der Datenstruktur ist O (N log N) oder das gleiche wie das Sortieren eines Vektors von N Elementen unter Verwendung einer beliebigen gemeinsamen O (log N) -Komplexitätssortierung.
In Ihrem spezifischen Szenario, da Sie keine Schlüssel / Wert-Paare haben, ist std::set oder std::multiset wahrscheinlich Ihre beste Wette.
Ich denke nicht, dass die Funktionalität in STL existiert, ein std :: vector kann nur mit partition , nth_element , stable_partition , < strong> partial_sort , stable_sort und sort .
Sie könnten jedoch einen Wrapper für std :: vector
erstellen %Vor%Tags und Links c++ stl sorting containers