Ich suche nach einem std-Container wie eine std :: list, die ein Element effizient nach vorne verschieben kann:
%Vor%verschiebe "b" nach vorne:
%Vor%Es gibt keine solche Funktion in den Standardcontainern. Daher denke ich, ich muss eine remove- und push_front-Funktion kombinieren, aber kann jemand eine bessere Idee finden?
Vielen Dank im Voraus.
Wenn Sie die Reihenfolge der anderen Elemente nicht beibehalten müssen, dann ist die einfachste Lösung zweifellos das Tauschen gewünschte Element mit dem ersten Element im Container. Dies ist effizient mit all Containern.
Ansonsten bietet std::list eine splice -Operation, die dies könnte
verwendet werden. So etwas wie das Folgende, denke ich:
Dies sollte nur mit ein paar Zeigeroperationen enden, und
nein kopiert. Auf der anderen Seite kann std::list sehr langsam sein
allgemein (wegen seiner schlechten Lokalität); Ich würde sehr messen
sorgfältig gegen die naive Umsetzung mit std::vector ,
um sicherzustellen, dass es weltweit ein Gewinn war. Eliminierung aller Kopien hier
Es kann kein Gewinn sein, wenn Sie iterieren, um das gewünschte Element zu finden
nach vorne zu bewegen ist zehnmal teurer. (Eine Menge davon
hängt davon ab, wie teuer MyType zu kopieren ist und wie groß es ist
ist. Wenn sizeof(MyType) nahe an der Größe einer Seite liegt, oder
Der Zugriff auf MyType endet mit dem indirekten Zugriff auf eine Menge
allokierte Objekte, das Argument locality wird nicht gehalten.)
Mit std::vector anstelle des offensichtlichen erase / insert
Dies führt zu weniger Kopien als die erase (welche Kopien
alle folgenden Elemente) insert (die auch alle kopiert)
der folgenden Elemente-was alle Elemente bedeutet,
weil wir am Anfang einfügen) Muster.
Bei std::vector könnten Sie std::rotate verwenden, das eine lineare Komplexität aufweist
Auf einem std::list können Sie die Memberfunktion splice verwenden, die (bei Iteratoren) eine konstante Komplexität
HINWEIS : Das letzte Element wird konventionell in den STL-Containern als back und das erste Element als front bezeichnet. Für std::vector ist das Abrufen von Iteratoren zu einem bestimmten Element eine konstante Zeit und das Tauschen ist eine lineare Zeit. Für std::list ist das Erhalten von Iteratoren eine lineare Zeit, aber das Spleißen in dieselbe Liste ist eine konstante Zeit. Allerdings ist auch das viel bessere Memory-Caching-Verhalten von Vektor wichtig, da dieser Benchmark von Stroustrup zeigt.
AKTUALISIEREN : Mehrere Kommentatoren erwähnen einfach Elemente zu tauschen: Dies gilt nur, wenn Sie a-b-c-d-e in a-e-c-d-b transformieren wollen. In diesem Fall verwenden Sie std::iter_swap für einen beliebigen Container. Verwenden Sie für die Umwandlung von a-b-c-d-e in a-c-d-e-b std::rotate oder list::splice .