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 Idiomvector<T>(v.begin(), v.end()).swap(v)
Seit C++11 hat
vector
dafür die Memberfunktionshrink_to_fit
.
-
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?
-
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 manerase()
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ällenstd::remove()
oderstd::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
derFerAuf 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ürint
s ist die Zuweisung schneller.Übrigens solltest du wenn schon
operator[]
stattat()
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.
-
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 deroperator[]
fehlt. Diestd::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.
-
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 hatMfG
-
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{}); }
-
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.