std::vector Specherfreigabe



  • Hallo

    Ich frage mich gerade:
    Wieso gibt std::vector kein Speicher frei, wenn Elemente entfernt werden? Was ist der Grund für dieses Design? Ist das vom Standard vorgeschrieben? Ich meine man könnte ja problemlos machen, dass der Speicherverbrauch exponentiell sinkt, so wie er auch wächst, um die Deallokationen zu minimieren. Oder ist das eine Eigenschaft des default-Allokators?



  • Das ist so beabsichtigt. Man kann in der Regel reservierte Speicherbereiche nicht stückweise freigeben, deshalb hätte eine Verkleinerung des reservierten Platzes eine neue Allokation und ein Kopieren der Elemente zur Folge.
    Möchte man den Vector trotzdem verkleinern, gab es bis C++11 das Idiom

    vector<T>(v.begin(), v.end()).swap(v)
    

    Seit C++11 hat vector dafür die Memberfunktion shrink_to_fit .


  • Mod

    Weil es effizient ist, ohne nennenswerte Nachteile zu haben. Es ist aus zwei Gründen effizient:
    1. Wenn der Speicher freigegeben werden sollte, so wäre eine Kopieraktion aller verbliebenen Elemente nötig. Ganz übel.
    2. Meistens wird der Vektor kurz danach wieder gefüllt.

    Die Vorgaben im Standard bezüglich Effizienz der Operationen und die Gültigkeit von Iteratoren diktieren indirekt, dass solch eine Freigabe nicht erlaubt wäre.

    Falls du aus irgendeinem Grund wirklich (bist du ganz sicher?) den Speicher freigeben musst, dann gibt es in C++11 shrink_to_fit (nicht bindend!) und ohne C++11 den swap-Trick (Efficient C++, Trick 17):

    mein_vector.swap(vector<T>(mein_vector));
    

    Achtung: Dies ist, wie oben angedeutet, eine teure Kopieraktion!

    P.S.: Mal wieder zu langsam...



  • Ok, aber beim Wachsen kann ein Umkopieren in einen neuen Speicherbereich auch durchaus notwendig sein. Ein vorübergehender Peak bezüglich Speicherverbrauch lässt sich da nicht vermeiden. Ausserdem werden Iteratoren beim Wachsen sowieso ungültig. Dürfen sie etwa beim Schrumpfen nicht ungültig werden? Nur dann wäre das Neuallozieren von kleineren Speicherblöcken verboten, oder?


  • Mod

    Beim Wachsen lässt sich Reallokation nicht vermeiden. Beim Schrumpfen schon. wieso sollte man sich selber behindern? Wo wäre der Vorteil?

    Du kannst auch jede Membermethode noch ein dickes sleep einbauen. Kann man machen. Wieso sollte man?



  • Bevor ich jetzt einen neuen Thread aufmache poste ich mal hier rein passt ja 😉
    Also ich habe gerade gelesen (in einem C++ Buch) das es sehr viel Rechenzeit kostet Elemente zu löschen, daher wird in einem Beispiel (zu dem das stand) aus dem Buch auch kein Element gelöscht (erase) sonder einfach bei der Durchsuchung des Vectors der Bereich nicht angesprochen.
    Daher es gibt eine Variable "Anzahl" welche die Anzahl der Elemente des Vectors verwaltet.
    Beispiel:
    Der Vector hat 5 Elemente, Anzahl = 5.
    Element 3 wird gelöscht.
    Jetzt wird Element 5 nach 3 kopiert und die variable Anzahl auf 4 geändert.
    So dass nur noch 4 Elemente durchsucht werden.

    Aber jetzt schreibt ihr ja das beim löschen eines Elementes gar keins gelöscht wird.
    Daher ist jetzt die Rechenzeit / Speicherplatz bei der Variante aus dem Buch günstiger?

    Danke 😃



  • Grundsätzlich kann std::vector::erase() teuer sein, weil es alle nachfolgenden Elemente umkopiert. Häufig sieht man erase() in einer Iterationsschleife, was wahnsinnig ineffizient ist, da für jedes zu löschende Element sämtliche Nachfolger verschoben werden müssen. Daher sollte man in solchen Fällen std::remove() oder std::remove_if() verwenden.

    Für einzelne Elemente gibts den swap() -and- pop_back() -Trick, das kannst du nämlich automatisch haben. Zuerst vertauschst du das zu löschende Element mit dem letzten, dann entfernst du das letzte. So ist das Löschen quasi gratis. Geht aber nur, wenn die Reihenfolge egal ist.

    std::swap(*itr, vec.back());
    vec.pop_back();
    

    Wenn man externe Variablen für sowas erstellt, hat man was ganz Wichtiges nicht verstanden...



  • Ah danke 😃
    Macht es denn einen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze?

    Und hab ich das richtig verstanden, das pop_back() einfach size() verkleinert? daher theoretisch ist das "gelöschte" Element immer noch über vec[vec.size()] erreichbar?

    Danke auf jeden Fall 🙂
    MfG
    derFer



  • derFer schrieb:

    Ah danke 😃
    Macht es denn einen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze?

    Und hab ich das richtig verstanden, das pop_back() einfach size() verkleinert? daher theoretisch ist das "gelöschte" Element immer noch über vec[vec.size()] erreichbar?

    Danke auf jeden Fall 🙂
    MfG
    derFer

    Auf das letzte Element wird der Dekonstruktor aufgerufen, d.h. das wäre undefiniert. Du wirst natürlich meistens noch die gleichen bytes dort vorfinden, aber Standard ist das nicht.



  • Ah OK, das habe ich mir schon gedacht... Danke 🙂
    Aber es macht keinen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze, oder?
    MfG,
    derFer



  • derFer schrieb:

    Aber es macht keinen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze, oder?

    Bei komplexen Objekten kann swap() effizienter sein, weil keine Kopie benötigt wird. Für int s ist die Zuweisung schneller.

    Übrigens solltest du wenn schon operator[] statt at() verwenden. In C++11 kannst du zudem das Objekt verschieben, was ebenfalls sehr effizient ist, allerdings einen Move-Zuweisungsoperator erfordert:

    vec[x] = std::move(vec.back());
    

    GorbGorb schrieb:

    Dekonstruktor

    Uuh.. 😮 Destruktor!



  • wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector. nutze dieses kleine Testprogramm zum Prüfen, welche unnötigen Kopieroperationen im Hintergrund ablaufen. verschiedene Stdlib Implementierungen liefern da übrigens unterschiedliche Ergebnisse (MSVC, gcc usw.)

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class MyInt
      {
    public:
      MyInt()
        { m_Value = 0;
          cout << "MyInt() "; Cout(); }
      MyInt(const MyInt& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "MyInt(c& " << &myCopy << ") "; Cout(); }
      MyInt(MyInt&& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "MyInt(&& " << &myCopy << ") "; Cout(); }
      MyInt(int i)
        { m_Value = i;
          cout << "MyInt(" << i << ") "; Cout(); }
      ~MyInt()
        { cout << "~MyInt() "; Cout(); }
      MyInt& operator=(const MyInt& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "operator=(c& " << &myCopy << ") "; Cout();
          return *this; }
      MyInt& operator=(MyInt&& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "operator=(&& " << &myCopy << ") "; Cout();
          return *this; }
      void setValue(int i)
        { m_Value = i;
          cout << "setValue(" << i << ") "; Cout(); }
    private:
      void Cout()
        { cout << m_Value << " " << this << endl; }
      int m_Value;
      };
    
    int main ()
      {
      {
      vector <MyInt> myVector;
      cout << "--- vector <MyInt> myVector;" << endl;
      MyInt myInt;
      cout << "--- MyInt myInt;" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      vector<MyInt>::iterator it = myVector.begin();
      myVector.erase(it);
      cout << "--- myVector.erase(it);" << endl;
      myVector.shrink_to_fit();
      cout << "--- myVector.shrink_to_fit();" << endl;
      }
      cout << "--- ~myInt(); ~myVector();" << endl;
      return 0;
      }
    


  • wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Worauf willst Du hinaus? vector hat doch supergeringen Overhead. Das Einzige, was mir einfällt, ist, dass der vector häufig wächst, wenn man sehr viele Elemente einfügt und das kann man durch reserve doch umgehen.


  • Mod

    dd++ schrieb:

    wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Das halte ich für einen gefährlichen Tipp. Denn viele Leute wissen nicht, warum sie Kopien vermeiden sollten, sondern finden einfach nur, dass das toll klingt. Sehen aber nicht die Nachteile. Dann nehmen sie am Ende std::list oder ähnliches und wundern sich, warum ihr Programm so lahm ist.

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.



  • SeppJ schrieb:

    dd++ schrieb:

    wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Das halte ich für einen gefährlichen Tipp. Denn viele Leute wissen nicht, warum sie Kopien vermeiden sollten, sondern finden einfach nur, dass das toll klingt. Sehen aber nicht die Nachteile. Dann nehmen sie am Ende std::list oder ähnliches und wundern sich, warum ihr Programm so lahm ist.

    Der Tipp ist ja nicht std::list verwenden. Wer das aus Versehen macht, findet schnell raus, dass der operator[] fehlt. Die std::deque ist schon besser, da wird nie etwas kopiert bei push_* (ausser ev. das einzufügende Element, aber dafür gibt es emplace).



  • SeppJ schrieb:

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.

    Performance? 😃

    Ich meine, einerseits beschäftigen sich viele hier mit nichts anderem, als der Fragestellung, wie man unnötige Kopien vermeidet
    und im gleichen Atemzug wird für fast jeden Anwendungsfall der vector empfohlen... Da beißt sich die Katze ja irgendwo in den Schwanz. 😃


  • Mod

    It0101 schrieb:

    SeppJ schrieb:

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.

    Performance? 😃

    😮 Eben drum vector benutzen? Performance ist doch gerade der Grund, deque & Co. wirklich nur dann zu benutzen, wenn man die speziellen Eigenschaften (zum Beispiel löschen am Anfang) ganz dringend braucht. Bei Normalbenutzung hängt ein vector eine deque ganz locker ab.



  • Es wäre super wenn jemand mal genau schreiben könnte wann man Vector benutzt, wann list und wann deque.
    Damit das immer wiederkehrende Fragen danach ein Ende hat 😉

    MfG



  • 😮 Eben drum vector benutzen? Performance ist doch gerade der Grund, deque & Co. wirklich nur dann zu benutzen, wenn man die speziellen Eigenschaften (zum Beispiel löschen am Anfang) ganz dringend braucht. Bei Normalbenutzung hängt ein vector eine deque ganz locker ab.[/quote]Naja, was man halt so Normalbenutzung nennt.

    int main()
    {
        typedef std::array<int, 999> data;
        std::vector<data> container; // bzw. deque
        for (int i=0; i<40000; ++i)
           container.push_back(data{});
    }
    

    Vektor: 0.39s
    Deque: 0.15s



  • Bevor jetzt der Kommentar kommt, man könne auch reserve benutzen: In diesem Fall ist Vektor einem Dynarray unterlegen. Das kann nämlich bei einer moderaten Anzahl Elemente auf dem Stack allokieren, was oft um EINIGES schneller ist.


Log in to reply