std: container c++ - "move to front"

Ich bin auf der Suche nach einem container wie std eine std::list, die effizient bewegen können ein element auf der Vorderseite:

a-b-c-d-e

bewegen "b" nach vorne:

a-c-d-e-b

Gibt es keine solche Funktion im std-Container. Dafür, ich glaube, ich muss kombinieren, entfernen und push_front Funktion hat aber kann jemand eine bessere Idee?

Danke im Voraus.

  • Was bedeutet "effizient" bedeuten?
  • goode Frage ... ich meine, besser als zu entfernen es und schaffen es an die Spitze. Wenn ich hatte, es zu implementieren, von Grund auf (in C), ich könnte einfach machen.Nächster Punkt "c", c.prev Punkt "a", b.prev Punkt "e", b.Nächster Punkt die NULL, vorne Punkt "b" und e.Nächster Punkt "b"... das wäre effizient, aber re-Implementierung von container ist ein bisschen zu aufwendig 😉
  • Die "fast" - Liste-Lösung verändert sich viel von Zeigern (8 bytes in 64-bit-code) an zufällige Positionen in potentiell nicht-Cache-Speicher. Ein Vektor mit fünf Elementen (wie im Beispiel), wird sich möglicherweise passen in eine einzige cache-Zeile, und sehr schnell.
InformationsquelleAutor Jav | 2013-01-29
  1. 12

    Wenn Sie nicht haben, um halten Sie die Reihenfolge der anderen Elemente,
    dann die einfachste Lösung ist sicherlich einfach tauschen
    gewünschte element mit dem ersten element in den container. Diese
    werden effizient mit alle Container.

    Ansonsten std::list bietet eine splice Betrieb könnte
    verwendet werden. So etwas wie die folgenden, ich denke: 

    void
moveToFront( 
    std::list<MyType>& list,
    std::list<MyType>::iterator element )
{
    if ( element != list.begin() ) {
        list.splice( list.begin(), list, element, std::next( element ) );
    }
}

    Diese sollten am Ende mit nur ein paar Zeiger-Operationen, und
    keine kopiert. Auf der anderen Seite std::list kann sehr langsam sein in
    allgemein (wegen dem schlechten Lokalität); ich würde Messen sehr
    gezielt gegen die naive Implementierung mit std::vector,
    um sicherzustellen, dass es war ein Sieg weltweit. Die Beseitigung aller Kopien hier
    kann nicht ein Gewinn sein, wenn die Iteration zu finden das element, das Sie möchten
    nach vorne bewegen, ist zehn mal teurer. (Eine Menge von dieser
    hängt davon ab, wie teuer MyType zu kopieren, und wie groß ist es
    ist. Wenn sizeof(MyType) ist nah an die Größe einer Seite, oder
    Zugriff auf MyType landet Zugriff auf eine Menge von indirekt
    zugewiesenen Objekte, die Lokalität argument nicht halten.)

    Mit einem std::vector, anstatt die offensichtliche erase/insert

    void
moveToFront( 
    std::vector<MyType>& list,
    std::vector<MyType>::iterator element )
{
    MyType tmp( *element );
    std::copy_backwards( list.begin(), std::prev( element ), element );
    *list.begin() = tmp;
}

    Dadurch werden weniger Exemplare als von den erase (die Kopien
    alle folgenden Elemente) insert (der kopiert auch alles
    die folgenden Elemente, was bedeutet, dass alle Elemente,
    weil wir das einfügen am Anfang) Muster.

    • Irgendeinem Grund nicht zu verwenden list.front() = tmp statt *list.begin() = tmp?
    InformationsquelleAutor James Kanze
  2. 16

    Auf std::vector könnten Sie std::rotate, die hat lineare Komplexität 

    #include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

std::vector<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   //swap ranges [1, 2) and [2, 5)
   auto it = std::next(v.begin(), 1); //O(1)
   auto rb = std::next(it);
   auto re = v.end();
   std::rotate(it, rb, re); //O(N)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));   
   std::cout << "\n";
}

    Auf eine std::list Sie könnte verwenden Sie die member-Funktion splice, die (gegebenen Iteratoren) hat Konstante Komplexität

    #include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

std::list<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   auto it = std::next(v.begin(), 1); //O(N)
   auto rb = std::next(it);
   auto re = v.end();   
   v.splice(it, v, rb, re); //O(1)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
   std::cout << "\n";   
}

    HINWEIS: das Letzte element ist conventially bezeichnet als back im STL-Containern, und das erste element als front. Für std::vector bekommen Iteratoren zu einem bestimmten element ist in konstanter Zeit, und tauschen ist die lineare Zeit. Für std::list bekommen Iteratoren ist die lineare Zeit, aber Spleißen in der gleichen Liste ist in konstanter Zeit. Allerdings viel besser, memory-caching-Verhalten des Vektors ist auch wichtig, da dieser benchmark von Stroustrup zeigt.

    UPDATE: Mehrere Kommentatoren erwähnten Austausch der Elemente: dies gilt nur, wenn Sie transformieren möchten a-b-c-d-e in a-e-c-d-b. Verwenden Sie In diesem Fall std::iter_swap auf alle container, die Sie mögen. Für die transformation von a-b-c-d-e in a-c-d-e-b verwenden std::rotate oder list::splice.

    • Mit std::list und ein entfernen-und-push " - operation haben Konstante Komplexität...
    • Ist, dass mehr effiziente, dann einen entfernen und einfügen ein einzelnes element?
    • Aber mit einem Konstanten Faktor so viel höher, dass es wahrscheinlich langsamer. (Natürlich hängt dies von der Größe des Behälters und der Art verschoben wird.)
    • Entfernen eines Links aus einem std::list und einfügen woanders ist wirklich sehr Billig. Ich wäre sehr überrascht, wenn die std::vector Umsetzung war schneller außer für pathologische Fälle.
    • tnx, finden Sie in den aktualisierten Antworten. Beachten Sie auch den Vortrag von Stroustrup, die gibt überraschende Ergebnisse, die das tun, fügt sich auf einer std::vector.
    • Lassen Sie sich überraschen. Löschen Sie ein element aus einer std::list, dann einsetzen in den Kopf, werden zwei Kopien des Elements, plus, eine freie und eine Zuteilung. Freigeben und zuweisen von Speicher können leicht Kosten mehr Zeit als es dauert, das kopieren von ein paar hundert int oder double. Für eine Sammlung von weniger als tausend int, std::vector wird wahrscheinlich schlagen std::list für diese operation. Auch eine Lösung mit Würze wird wahrscheinlich berühren mehrere verschiedene Seiten, wo wie bei kleineren Datensätzen, die Lösung mit vector vielleicht nie verlassen haben, ein cache-miss.
    • Die rotate Lösung ändert sich die Reihenfolge der übrigen Elemente. Wenn dies akzeptabel ist, nur vertauschen mit dem ersten element ist wesentlich effizienter.
    • Nein das ist nicht richtig: std::rotate dreht sich das gesamte Teilbereiche. siehe liveworkspace.org/code/QItmN$17 0,1,2,3,4 Sequenz gedreht, in 0,2,3,4,1. Dies ist genau die Art von transformation, die die OP beantragt. Siehe update zu beantworten.
    • Siehe update zu beantworten.

    InformationsquelleAutor TemplateRex
Schreibe einen Kommentar