vector-container und die Speicherfreigabe

rain

Hallo,
kann mir vielleicht jemand von Euch helfen und einen Tipp geben, wie man einen in einem Container allokierten Speicher wieder freigeben kann.

Es geht hierbei um Folgendes:
Ich möchte einen Strings dynamsich (d.h. in beliebiger Länge und Anzalh) in einem Container verwalten. Also, so was wie einen String-Array in VB nachbilden.

Dabei kann ich also mit der Methoder pop_back ein Element am Ende anhängen und mit push_back wieder von Ende entfernen.

Entferne ich ein Element, so ist es zwar inhaltlich weg - jedoch nicht der dafür zuvor reservierte Speicher.

Im Prinizp bedeutet das für mich, dass ich die Strings zwar dynamisch verwalten kann - nicht jedoch den reservierten speicher.

Wie kann ich diesen Speicher, vollkommen freigeben und die Vector-Größe auf die tatsächliche Größe begrenzen?

Muß man den gesamten "Array" umkopieren..?
Wie geht man in solch einer Situation vor..?

Danke schön
RAIN

Fux

Ich hab schon im C-Forum darauf geantwortet, ausser mit swap oder Zuweisung, bekommte man den (vor-)reservierten Speicher nicht frei. Und selbst diese beiden Dinge müssen nicht funken:

vector<char> orig;
...
vector<char> tmp( orig );
tmp.swap( orig ); // nun könnte orig wieder geschrumpft sein

cu

PS: wenn ein vector<char> als String betrachtet wird, nicht die End-Null vergessen.

[ Dieser Beitrag wurde am 09.03.2003 um 13:14 Uhr von Dimah editiert. ]

tunichtgut

So als überlegung: Was wäre denn mit einem deque? Der zugriff ist zwar um einiges langsamer - man bekommt dafür aber eine bessere speicherverwaltung.

RPD

Hallo,

vector, speicherverwaltung, dynamisch?
kein problem:
vector::resize
- Reallocates memory for vector, preserves its contents if new size is larger than existing size.

ps
mit vector::capacity bekommst du die anzahl der elemente für die im augenblick speicher reserviert ist

**********
Gruß
RPD
**********

[Diese Nachricht wurde von RPD am 19-06-2001 editiert.]

Fux

resize kann nur die Elemente im Container verringern (vielleicht meinte RAIN das), jedoch nicht den angeforderten Speicher, mit anderen Worten die Kapazität wird nicht kleiner.

RPD

@Fux

ähm, da muß ich widersprechen!
bei meinem PC funkt das so... http://www.c-plusplus.net/ubb/ubb/biggrin.gif

kann das jemand bestätigen?

verwechselst du vielleicht capacity mit max_size???

[Diese Nachricht wurde von RPD am 19-06-2001 editiert.]

tunichtgut

Laut standard gibt ein resize auf einen kleineren wert bei einem vector keinen speicher freigeben. Es fordert nur neuen speicher an, wenn die augenblickliche kapazität nicht ausreicht.

Die kapazität eines vectors kann man unabhängig von der anzahl der gültigen elemente mit reserve steuern. Aber selbst hier muß kein speicher freigegeben werden wenn der neue reservierte bereich kleiner als der alte reservierte bereich ist. Ich weiß allerdings nicht ob es den jeweiligen implementierungen in diesem fall erlaubt ist trotzdem speicher freizugeben.

ufh

hallo,

habe ich da was falsch verstanden ? meiner meinung nach kann man erase() sagen. das objekt wird aus dem vector entfernt und sein konstruktor aufgerufen. dann sollte doch der speicher freigegeben sein. der platz im vector ist nun frei. um auch den vector kleiner zu kriegen wird resize() benutzt.
nachfolgen ein auszug aus der VC-Hilfe.

gruss
uli
-------------------------------
vector::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

Erasing N elements causes N destructor calls and an assignment for each of the elements between the insertion point and the end of the sequence. No reallocation occurs, so iterators and references become invalid only from the first element erased through the end of the sequence.

RPD

@ufh

...genau so denk ich mir das auch...
destruktor wird aufgerufen, also wird der speicher freigegeben.

aber die "fachwelt" ist da anscheinend noch geteilter meinung... http://www.c-plusplus.net/ubb/ubb/confused.gif

Fux

Nur weil der Destruktor aufgerufen wird, heisst das nicht, dass auch der Speicher freigegeben wird. (Stichwort "placement-new" und "expliciter Destruktoraufruf"). zB:

MyClass* mk = new MyClass; // Speicher anfordern
mk->~MyClass(); // Destruktor aufrufen, aber nicht Speicher freigeben
new (mk) MyClass; // Placement-new: nur kontruieren, kein Speicher anfordern
delete mk; // Destruktor + Speicherfreigabe

Genau das macht die Klasse vector beim Löschen von Elementen. Er deinitialisiert den Eintrag, gibt dessen Speicher nicht frei.
Da deinitialisiert doof kling, sagt man löschen oder "remove" - auch wenn sich dies nach Speicherfreigabe anhört.

cu

[ Dieser Beitrag wurde am 09.03.2003 um 13:14 Uhr von Dimah editiert. ]

HumeSikkins

Hallo,
kommt man in eine solche Situation häufiger (bezüglich des löschens von Elementen), sollte man sich überlegen, ob man nicht einfach den Container-Typ wechselt.
Es muß ja nicht immer vector sein.
List z.B. gibt beim Entfernen eines Objekts auch immer den Speicher wieder frei.

Gruß

RPD

also jetzt versteh ich gar nix mehr...
destruktor gibt den speicher nicht frei http://www.c-plusplus.net/ubb/ubb/confused.gif
also komm, du willst mich veräppeln... http://www.c-plusplus.net/ubb/ubb/biggrin.gif
ich verwende doch auch kein delete wenn ich ein prog beende, da ruf ich halt den destruktor auf. warum sollte man das machen wenn der speicher nicht freigegeben wird???

zu list:
The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

Erasing N elements causes N destructor calls. No reallocation occurs, so iterators and references become invalid only for the erased elements.

...komisch genau die gleiche info wie bei vector, aber hier wird jetzt doch der speicher freigegeben...

hiiiilllllfffeeeee..... http://www.c-plusplus.net/ubb/ubb/frown.gif

------------------
**********
Gruß
RPD
**********

Stefan Dreckmann

@RPD:
Das ist kein Scherz, der Destuktor gibt tatsächlich nicht den Speicher frei. Das ist einfach nur eine Funktion, wie jede andere auch, nur daß sie halt (normalerweise) nur zu besonderen Gelegenheiten aufgerufen wird.

Stell Dir vor, Du hast ein Objekt nicht mit new(), sondern auf dem Stack angelegt. Irgendwann wird für das Objekt natürlich auch der Destruktor aufgerufen. Wenn der jetzt Speicher freigeben wollte, wäre das ein ziemliches Chaos!

Es ist übrigens keine gute Idee, den Destruktor explizit aufzurufen, wie Du das in Deinem Beitrag andeutest. Das ist nur was für sehr spezielle Angelegenheiten. Lösche das Objekt mit delete() und laß den Compiler den Destruktor aufrufen. Warum solltest Du das unbedingt selbst machen wollen?!

Stefan.

ufh

guten morgen,
die vectoren haben mir keine ruhe gelassen und ich habe es mal getestet: es wird definitiv der destruktor der klasse, die im vector verwaltet wird aufgerufen !
vielleicht eins zur klärung : die initialisierung von vector stellt speicherplätze für die zu speichernden klassen zur verfügung. dieser wird mit resize verwaltet. um nicht ständig speicer allokieren zu müssen ändert vektor nicht von selbst seine größe. wird beispielsweise ein vector mit 7 elementen angelegt, so wird der speicher allokiert und bleibt allokiert, auch wenn elemente enfernt werden. der vector muß expolizit mit resize() auf eine neue größe gesetzt werden. zu unterscheiden sind also der speicher für vectorplatz und klasse. vector stellt genug speicher auf einem vectorplatz zur verfügung um dort eine klasse hinzuseten. die - absolute - größe des vectors ändert sich also nicht. wird ein element eingefügt wird es echt auf den vector kpopiert und an seiner alten stelle deleted !!! (das hae ich getestet)wird das element entfernt, wird der destruktor aufgerufen und das element deleted. der speicherplatz im vector bleibt aber erhalten., aber wahrscheinlich durch ein dummy-element oder null-pointer ersetz (schätze, das sind implementierungsdetails)
falls jemand anderer meinung ist, können wir das ganze ja auch noch mit capacity() überprüfen :-))

ciao
uli

p.s.: wie war das mit dem code einfügen ??

-----------------
info : die klasse abc gibt im constructor und im destructor eine meldung aus.

vector<abc> abc_vector;
vector<abc>::iterator iter;

cout << "----------------------------------------" << endl;
cout << " generating classes and store them" << endl;
cout << " in a vector..." << endl;
cout << "----------------------------------------" << endl;
abc a1(1,1), a2(2,2), a3(3,3), a4(4,4);

abc_vector.push_back(a1);
abc_vector.push_back(a2);
abc_vector.push_back(a3);
abc_vector.push_back(a4);

cout << "-----------------------------------------" << endl;
cout << " searching in vector for element with x=3" << endl;
iter = abc_vector.begin();
while (iter != abc_vector.end())
{
    if ((*iter).GetX() == 3)
    {
        cout << " found element - erasing now... " << endl;
        abc_vector.erase(iter);
    }
    iter++;
}

cout << "-----------------------------------------" << endl;
cout << " erasing element with pop_back" << endl;
abc_vector.pop_back();

[ Dieser Beitrag wurde am 09.03.2003 um 13:16 Uhr von Dimah editiert. ]

RPD

...eine welt bricht zusammen!
ihr habt recht, der speicher wird nicht freigegeben (capacity). da bin ich dann wohl auf dem holzweg gewesen. da kriegt jetzt die STL aber ein dickes -- bei mir http://www.c-plusplus.net/ubb/ubb/biggrin.gif

aber wieso soll das bei list dann anderst sein (hab ich nicht probiert, aber HumeSikkins sagt das sei so)???

HumeSikkins

Hallo,
der List-Container verwendet ein anderes Prinzip als der vector. Beim vector liegt der Speicher am Stück vor (wie bei einem Array). List hingegen fordert für jedes neue Element neuen Speicher an und gibt diesen dann beim Entfernen des Elements wieder frei. Der Speicher in einer List ist nicht zusammenhängend.

Eine Übersicht:
Vector: gibt Speicher nicht frei
List: gibt Speicher frei.
Deque: gibt Speicher manchmal frei.
Set: gibt Speicher frei (ebenso Multiset).
Map: gibt Speicher frei (ebenso Multimap)

Habe mich aber selbst noch nicht mit Deques beschäftigt und kann deshalb nicht sagen wann manchmal genau zutrifft.

Gruß

ufh

* liste soll dynamisch elemente aufnehmen können, wobei performance nicht so wichtig ist, sondern optimierter speicherbedarf im vordergrund steht. wird ein element aus der liste entfernt, wird folgerichtig sofort der speicher freigegeben...
zugriff auf bestimmtes element ist hier nicht möglich, sondern du mußt per iterator jedes element abfragen...
* bei vector, wird davon ausgegangen, daß du ungefähr weißt, wiviel elemente du brauchst. der kluge vektor, legt schon mal entsprechend speicher an. wenn du ein element hinzufügst (und es ist noch ein plätzchen frei) braucht kein speicher allokiert zu werden. zugriff kann über index geschehen. konzept wie vektor in mathe. es gibt eine feste anzahl plätze (z.B. dimensionen . vector (x,y,z))

bei bjarne stehen auch noch ein paar lustige sachen, die man mit vektoren machen kann, wie z.B. matrizen implementieren (z.B. für 2D oder 3D world), wobei irgendwo auch noch maskierfunktionen vorhanden sind. habe ich aber noch nicht getestet...

danke für die idee, sich mal wieder mit vectoren zu beschäftigen

schönen tach noch
uli

Fux

zu ufh's Beitrag

Ist schon richtig, ich will nur ein paar Dinge klarstellen
resize(x) erhöht oder veringert die Anzahl der Elemente im vector. Notfalls muss Speicher angefordert werden. Mit size() zu testen.
reserve(x) erhöht die Kapazität falls benötigt, verringert sie jedoch nicht. Mit capacity() zu testen.

Die absolute Größe ändert sich beim Einfügen meistens nicht, außer es ist kein Platz für ein neues Element da, dann doch.

Zitat

der speicherplatz im vector bleibt aber erhalten., aber wahrscheinlich durch ein dummy-element oder null-pointer ersetz (schätze, das sind implementierungsdetails)

Kein dummy-Element - dann müsste dafür ja ein Konstruktor aufgerufen werden. Es ist eher "verwilderter" Speicher, in etwa wie der freie Speicher in Windows oder Linux. Der Wert den dieser Speicher hat ist zufällig - meist sind es die Überreste des ehemaligen Objekts. Erst durch ein Konstruktoraufruf wird dieser Speicher wieder strukturiert.

@Stefan
[quote]Es ist übrigens keine gute Idee, den Destruktor explizit aufzurufen, wie Du das in Deinem Beitrag andeutest[quote]
Meinst du damit mich? Ich wollte damit nur den Unterschied zwischen new und placemant-new darstellen und wie <vector> intern arbeitet. Natürlich sollte das keine Programmierempfehlung sein http://www.c-plusplus.net/ubb/ubb/biggrin.gif

Also liebe Kinder, was Onkel Fux da gemacht hat - macht es bitte nicht nach

@RAIN
Inzwischen sind wir von deiner Frage >etwas< abgekommen. Ich hoffe meine Antwort konnte dir dennoch helfen. Wenn nicht darfst du uns gern stören http://www.c-plusplus.net/ubb/ubb/smile.gif

cu

tunichtgut

Noch mal zur erläuterung was es mit new, delete, konstruktor, destruktor usw. auf sich hat.

Konstruktoren (ctor) und destruktoren (dtor) sind im prinzip ganz normale funktionen mit nur wenigen besonderheiten. Die besonderheiten sind, das sie keine rückgabewerte haben und im fall des destruktors auch keine übergabeparameter. Außerdem können konstruktoren nie virtuell sein.

Das ctor und dtor keine rückgabewerte haben liegt daran, das sie zu einem großteil implizit vom compiler automatisch aufgerufen werden und es so keine möglichkeit gibt diese auszuwerten. Beim destruktor gibt es noch nicht einmal parameter weil diese auch wenig sinn hätten. Das ist allerdings nicht ganz richtig! Einen parameter erhalten diese funktionen doch! Es ist der this-pointer! Der this-pointer zeigt im falle des ctors auf den speicherbereich, wo das objekt konstruiert werden soll (bis dahin ist es nicht initialisiert), der speicher muß aber bereits zur verfügung stehen! Wird z.b. ein objekt auf dem stack angelegt, wird von der aufgerufenen funktion platz auf dem stack dafür reserviert. erst an der stelle wo die variable definiert wird, wird auch der konstruktor aufgerufen und das objekt initialisiert.

class A;

void f()
{ // <= hier wird bereits platz für vara und
  // varb auf dem stack bereitgestellt!

  ... tu irgendwas
  ... tu nochmehr

  A vara;  // <= hier geschehen zwei dinge:
           // vara wird dem compiler bekannt
           // gemacht und kann ab hier im
           // quellcode genutzt werden.
           // Außerdem wird zur laufzeit der
           // konstruktor von A aufgerufen
           // und der speicher auf dem stack
           // der für vara reserviert wurde
           // initialisiert.
  A varb;  // das gleiche in grün...

  ... tu noch viel mehr

  // automatischen aufruf der destruktors
  // von A für varb
  // automatischen aufruf der destruktors
  // von A für vara
}
// nach dem ablauf der eigentlichen funktion
// erfolgt erst die wirkliche
// speicherfreigebe für vara und varb

Der operator new ist auch etwas besonderes. Er erledigt im allgemeinen zwei sachen. Als erstes erstes wenn er ein objekt erzeugen soll, holt er sich freispeicher, der groß genug ist, um ein objekt der angegebenen klasse darin unterzubringen (stichwort sizeof). Ok, soweit ist es nur roher speicher. In einem zweiten schritt ruft er jetzt der konstruktor für die angeebene klasse auf um den erhaltenen speicher zu initialisieren und somit daraus ein richtiges objekt zu machen.

Das delete arbeitet genau umgekehrt. Es ruft erst den zuständigen destruktor auf. Der speicherbereich an dem sich vorher ein objekt befand ist jetzt quasi wieder roher speicher. Erst jetzt wird dieser rohe speicher dem system wieder zurückgegeben.

konstruktion und destruktion haben mit der eigentlichen speicherverwaltung im prinzip nichts zu tun (außer das für die konstruktion eines objektes natürlich speicher zur verfügung stehen muß). Sie liegen jedoch immer sehr nahe beieinander, was zu verwirrungen sorgen kann.

Der explizite aufruf eines destruktors ist eigentlich nie nötig - meist sogar tödlich. Speicher wird dadurch schonmal garnicht freigegeben. Die einzige ausnahme (wie Fux schon angedeutet hat) ist die verwendung von placement-new (bzw. delete). Das kommt aber im normalen anwendercode so gut wie nie vor und ist auch nicht einfach zu handeln. Das placement-new erzeugt ein objekt (d.h. ruft den konstruktor auf) an einer bestimmten speicherstelle, ohne selber speicher zu reservieren! Da hier kein delete funktionieren würde (wer weiß was für speicher das ist?) muß tatsächlich der destruktor explizit aufgerufen werden.

Und jetzt noch etwas zur speicherfreigabe bei vector und list.

Die STL list speichert ihre elemente in einer verketteten liste ab. dabei wird für jedes element einzelnd neuer speicher angelegt (+ zeiger auf vor und nach). Wird ein element gelöscht, so wird dafür auch der speicher freigegeben. Wird ein neues element angelegt wird wieder neuer speicher angefordert.

Der STL vector arbeitet anders. Ersteinmal wird roher speicher reserviert (für mehrere objekte ausreichend), ohne das überhaupt elemente existieren, d.h. es werden keine konstruktoren für ernthaltenen objekte aufgerufen. Erst wenn ein objekt angehangt wird, erzeugt ein placemnt-new tatsächlich ein objekt im reservierten speicher. Mit reserve(100) wird dem vector mitgeteilt, das er genug speicher für 100 objekte vorhalten soll, das muß dabei in einem stück vorliegen! Bei anschließendem resize(50) werden in diesem speicher 50 elemente mit dem placement-new erzeugt, wobei auch der konstruktor (50*) aufgerufen wird (bei resize ist es der dafaultkonstruktor). Der rest des speichers steht weiter für neue objekte zur verfügung. Werden jetzt die letzten 20 elemente gelöscht, so geschit dieses mit dem explizitem aufruf des destruktors (aber bloß nicht selber machen, geht alles automatisch). Speicher kann nicht freigegeben werden, da er zu beginn in einem stück reserviert wurde -> daher das unterschiedliche verhalten bei vector und list.

[ Dieser Beitrag wurde am 09.03.2003 um 13:16 Uhr von Dimah editiert. ]

tunichtgut

@HumeSikkins:

Für deques ist es implementierungsspezifisch, da gibt es kein vorgegebenes verhalten. Jeder der ein deque implementiert kann das also machen wie er will, damit sein deque effektiv arbeitet. Die deques sind eigentlich sehr interessant und man sollte sie sich ruhig mal ansehen.

@ufh:

Zitat:

* liste soll dynamisch elemente aufnehmen können, wobei performance nicht so wichtig ist, sondern optimierter speicherbedarf im vordergrund steht. wird ein element aus der liste entfernt, wird folgerichtig sofort der speicher freigegeben...

Das kann man so nicht stehen lassen. Die performanz (<= hab nachgesehen, so ist die deutsche schreibweise) ist bei einer liste sogar relativ gut, wenn nicht gerade neue elemente angelegt oder gelöscht werden. Die iteration über eine liste ist kaum schlechter als bei einem vector aber viel besser als z.b. bei einem deque. Das zusammenfügen von listen sollte auf jeden fall schneller als ber vectoren sein. Eine liste hat auf anderen gebieten geschwindigkeitsvortele, wo gerade vectoren schlecht sind (einfügen in der mitte z.b.).

Das mit dem optimierten speicherplatz ist auch nicht ganz richtig. Bei kleinen objekten (z.b. list<int> ) wird speicher für jedes element angelegt. Zusatzlich zum objekt selber müssen listenelemente zusätzlich zwei pointer mitschleppen. In diesem fall wurde ein eintrag in der liste den 3fachen speicher belegen, der für ein einfaches int notwendig wäre. Zusätzlich zu diesem speicherbedarf benötigt das betriebssystem im allgemeinen auch informationen für die einzelnen belegten speicherstellen - nochmehr speicherverschwendung. Unterm strich benötigt die liste ein mehrfaches als eigentlich notwendiger speicher für sehr kleine objekte. Bei sehr großen elementen ist das anders. Dort fallen die verwaltungsinformationen kaum ins gewicht. Wenn ein vector bei großen objekten unnötig viel speicher vorhält spielt die liste hier ihre vorteile aus. Ein weiterer vorteil der liste bei großen objekten ist das wegfallen des kopierens der einzelnen elemente. Ein vector muß um zu wachsen oft alle elemente umkopieren, eine liste nicht.

Will man ein einigermaßen güsnstigen speicherverbrauch bei dynamischer größe -> deque. Ist zwar kein performanzwunder aber bei vielen anwendungen fällt das auch nicht ins gewicht.

[Diese Nachricht wurde von tunichtgut am 20-06-2001 editiert.]