std::vector Specherfreigabe



  • 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.


  • Mod

    @abweichler:
    Super. Du hast eine der beiden Sachen gemessen, die deque besser als vector kann. Einfügen. 🙄

    Nun miss mal die Zugriffszeiten.

    Was kommt in normalen Programmen häufiger vor? Einfügen oder Zugriff?

    Falls dein Programm tatsächlich nur Daten in Container speichern soll (write only 🙂 ), dann ist deque natürlich der richtige Container. Das ist einer der erwähnten guten Gründe, bei denen man vector nicht nutzen sollte.

    @derFer:
    Das ist doch nun wirklich leicht bei Google zu finden. Unter anderem:
    http://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11
    Das Bild und die Antworten von Matthieu M. und Nicol Bolas (diese Antwort ganz besonders!) sollten alle Fragen beantworten.



  • Im Zweifelsfalle kann man ja zum shared_ptr greifen, wenn das Objekt wirklich viel hin und her kopiert werden soll. Wenn man so wie ich einen Anwendungsfall mit einem Durchsatz von 80.000 pro Sekunde hat, überlegt man sich zwei mal ob man die Objekte nackig in einen Container ( egal welcher ) knallt, oder doch lieber smartpointer nutzt 😉



  • SeppJ schrieb:

    @abweichler:
    Super. Du hast eine der beiden Sachen gemessen, die deque besser als vector kann. Einfügen. 🙄

    Nun miss mal die Zugriffszeiten.

    Was kommt in normalen Programmen häufiger vor? Einfügen oder Zugriff?

    Klar, Zugriff kommt häufiger vor. Aber der ist ungefähr gleich schnell. Das Einfügen ist das, was Zeit braucht.

    10*2^12 Elemente, 2^18 Zugriffe:
    Vektor: 0.55s
    Deque: 0.23s

    10*2^12 Elemente, 2^20 Zugriffe:
    Vektor: 0.72s
    Deque: 0.43s

    10*2^12 Elemente, 2^24 Zugriffe:
    Vektor: 4.78s
    Deque: 4.49s


Anmelden zum Antworten