recover last element and pop it effectively



  • was ist bei einem std::vector dir effizienteste Methode um das letzte Element aus des Vektors zu fetchen und es danach nicht mehr im Vector zu haben?

    std::vector<int> vec{1,2,3};
    auto e = vec.back();
    vec.pop_back();
    

    hier muss ich ne Kopie anlegen, da durch den pop der Eintrag im Speicher gelöscht wird.

    std::vector<int> vec{1,2,3};
    auto& e = vec.back();
    vec.resize(vec.size() -1)
    

    hier brauche ich keine Kopie

    gibt es bessere/effizientere Wege?



  • resize(n) löscht die Elemente hinter n.
    Deine Referenz ist also Schrott.



  • Sewing schrieb:

    std::vector<int> vec{1,2,3};
    auto& e = vec.back();
    vec.resize(vec.size() -1)
    

    hier brauche ich keine Kopie

    Aber nur, weil der Speicherinhalt zufällig noch intakt ist.

    Wenn das nicht int wäre, sondern ein Objekt, was einen Destruktor hat, dann könntest du das nicht machen, das ist dir schon klar, oder?



  • ja ist mir klar 🙂

    aber ist das wirlich nicht besser zu machen?


  • Mod

    Sewing schrieb:

    was ist bei einem std::vector dir effizienteste Methode um das letzte Element aus des Vektors zu fetchen und es danach nicht mehr im Vector zu haben?

    hier muss ich ne Kopie anlegen, da durch den pop der Eintrag im Speicher gelöscht wird.

    Du bist witzig. Wie sollen denn deiner Meinung nach die Bedingungen "nicht mehr im Vector haben" und "keine Kopie machen" vereinbar sein?



  • vielleicht indem der speicherebreich des vectors am ende um ein element verkleinert wird?



  • Und was passiert mit dem letzten Element, wenn keine Kopie davon angelegt wird?



  • auf das verweist dann meine referenz



  • Speicher von vormals letztem Element nach vec.resize(vec.size() -1) nicht mehr dem vector /Dir gehören. Du verstehen? Referenz dann verweisen auf Gaga.



  • Da kannst hier Move Semantics verwenden.



  • Sewing schrieb:

    auf das verweist dann meine referenz

    Eine weak-reference, die nicht lebenszeitverlängernd wirkt. Du referenzierst etwas, was niemandem mehr gehört und was daher theoretisch abgeräumt werden könnte.

    Dass der vector das beim Verkleinern nicht tut, solltest du nicht ausnutzen. Was, wenn jemand, der von diesem Hack nichts weiß, den vector durch einen anderen Container ersetzt? Oder wenn der Code so umgebaut wird, dass er nicht mehr ints speichert, sondern Objekte mit Destruktor, die beim resize zerlegt werden? Oder wenn der Container mit einem anderen resize verlängert wird (und den ganzen Speicher verschiebt), während du deine Referenz noch gültig wähnst?

    Es gibt tausend Möglichkeiten, wie dir sowas auf die Füße krachen kann.



  • Es gibt drei Möglichkeiten:

    1. move verwenden: auto e = std::move(vec.back());
    Das ist in 99% der Fälle die richtige Lösung.

    Wenn der Typ nicht günstig move-bar ist, gibt es noch:
    2. vector aus unique_ptr verwenden.
    3. Die Elemente im vector in Ruhe lassen und separat merken, wie viele Elemente du als "verwendet" ansehen möchtest.
    Beim "Entfernen" dekrementierst du diesen Zähler und weiter nichts.



  • Sewing schrieb:

    std::vector<int> vec{1,2,3};
    auto e = vec.back();
    vec.pop_back();
    

    hier muss ich ne Kopie anlegen, da durch den pop der Eintrag im Speicher gelöscht wird.

    std::vector<int> vec{1,2,3};
    auto& e = vec.back();
    vec.resize(vec.size() -1)
    

    hier brauche ich keine Kopie

    (1) Bei int s muss man keine Kopien sparen. Da solltest Du eher unnötige Hüpfereien im Speicher per Zeiger/Referenz-Verfolgung sparen.

    (2) vector::resize invalidiert Referenzen. Das heißt, vec.resize(...); macht dein e zu einer baumelnden Referenz. Das ist ein Fehler.

    (3) Bei int s mag dieser "Trick" augenscheinlich noch "funktionieren" (trotzdem nicht im Sinne des Erfinders!), aber bei den komplizierteren Typen, wo es gerade darauf ankommt, Kopien zu sparen, weil das Kopieren teuer ist und Destruktoren irgendwelche nicht-trivialen Aufräumarbeiten erledigen, würdest Du über dein e auf die Speicherüberseste eines schon zerstörten Objekts zugreifen! Schon zerstört im Sinne von, der Destruktor lief da schon drauf und du solltest den Speicher nicht mehr anfassen.

    Sewing schrieb:

    gibt es bessere/effizientere Wege?

    Ja, klar. Richtig ist immer besser als falsch. 😉 Siehe sergeys Antwort, also

    vector<T> vec = ...;
    assert(!vec.empty());
    T last = std::move(vec.back());
    vec.pop_back();
    

    So ein "Move-Request" kann in Genzfällen dazu führen, dass eine Ausnahme geworfen wird. Und wenn ein Move fehlschlägt, dann kann man sich nicht drauf verlassen, dass das Quellobjekt noch so aussieht, wie es vorher war. Wenn Dir die "strong exception safety" in diesem Fall wichtig ist, kannst Du auch std::move_if_noexcept statt std::move benutzen:

    vector<T> vec = ...;
    assert(!vec.empty());
    T last = std::move_if_noexcept(vec.back());
    vec.pop_back();
    

Log in to reply