Element aus Vektor löschen und Speicher freigeben

SeppJ

davie schrieb:

die standardlösung dafür ist
vector<T>().swap(other_vector);

Man sollte aber betonen, dass dies nicht die Standardlösung zum Löschen der Vectorelemente ist, sondern die Standardlösung für den eher speziellen und seltenen Fall in dem man die capacity des Vectors ebenfalls auf 0 setzen möchte.

snOOfy

SeppJ schrieb:

Und was hat das miteinander zu tun?
(Tipp: Nichts)

Im Laufe der Zeit werden in meinem Vektor immer mehr Elemente erstellt und alte gelöscht. Die Anzahl der Elemente bleibt ungefähr gleich. Trotzdem verbraucht das Programm aber immer mehr Arbeitsspeicher, bis es bei 2GB schließlich abstürzt. Wie hat das jetzt nichts damit zu tun, dass der Speicher meiner Vektorelemente nicht freigegeben wird? Genau das führt doch zu dem Problem, oder nicht?

Vielleicht stelle ich mich ja ein bisschen blöd an, aber was genau muss ich denn jetzt machen, damit immer gleich viel Arbeitsspeicher belegt bleibt (nämlich genau der, der für die vorhandenen Elemente des Vektors benötigt wird)?

Tachyon

snOOfy schrieb:

Im Laufe der Zeit werden in meinem Vektor immer mehr Elemente erstellt und alte gelöscht. Die Anzahl der Elemente bleibt ungefähr gleich. Trotzdem verbraucht das Programm aber immer mehr Arbeitsspeicher, bis es bei 2GB schließlich abstürzt.

Dann hast Du an anderer Stelle ein Speicherleck. Solange die Kapazität nicht wachsen muss, werden die Elemente eines Vektors immer recycled. Vielleicht machst Du bei der Freigabe des Freispeichers mittels delete was falsch.

snOOfy

Das hier ist der gesamte Code:

#include <vector>;
using namespace std;

class CTest {
	double asd;
};

int main() {
	vector<CTest*> test;
	for (int i = 0; i < 2000000; ++ i)
		test.push_back(new CTest());
	system("PAUSE");

	for (int i = 2000000 - 1; i >= 0; -- i)
		delete test[i];
	system("PAUSE");
}

Mache ich da bei delete was falsch?

Tachyon

snOOfy schrieb:

Das hier ist der gesamte Code:

#include <vector>;
using namespace std;

class CTest {
	double asd;
};

int main() {
	vector<CTest*> test;
	for (int i = 0; i < 2000000; ++ i)
		test.push_back(new CTest());
	system("PAUSE");

	for (int i = 2000000 - 1; i >= 0; -- i)
		delete test[i];
	system("PAUSE");
}

Mache ich da bei delete was falsch?

Der Code verbaucht auf typischen 32 Bit Systemen knapp 23 MB. Wie Du damit 2 GB voll bekommst, erschließt sich mir nicht.

SideWinder

Jedenfalls ist klar, warum du beim zweiten system("PAUSE") immer noch einiges an Speicher benötigst (laut TaskMgr). Da du zwar die Objekte gelöscht hast, aber immer noch alle Zeiger im Speicher hast (auch wenn diese Zeiger jetzt auf ungültigen Speicher zeigen). Nach der for-Schleife musst du noch vec.clear() bzw. zum endgültigen Bereinigen (= vec.capacity() ==0) musst du die Zeile mit dem swap einfügen.

MfG SideWinder

krümelkacker

snOOfy schrieb:

Mache ich da bei delete was falsch?

Sollte so klappen, sofern 'int' solch große Zahlen fassen kann (was nicht garantiert ist, btw). Es ist aber eher sinnfrei in diesem Fall konkreten Beispiel new/delete zu verwenden. Ich frage micht, was Dir diese Indirektion bringt. Du kannst doch auch gleich die CTest-Objekte im Vektor speichern, statt Zeiger...

Viele kleine "popelige" Objekte per new Erzeugen, würde ich vermeiden, wenn's geht. So verbrätst Du wahrscheinlich 20 Bytes pro Objekt (nur geraten, 8 Bytes für's double, 8 bytes für Freispeicher-Verwaltungsoverhead und 4 bytes für ein Zeiger, 32bit-System angenommen) und das Speicher anfordern/freigeben kostet auch Zeit. Da ist das Kopieren im Vergleich dazu bei einem "popeligen" double nicht schlimm.

weicher

Hallo Tachyon,

dass Du alles löschtst ist ja nur in Deinem Beispiel so. Im effektiven Code willst Du ja einzelne Elemente löschen.

for (int i = 2000000 - 1; i >= 0; -- i)
   {
     CTest* heapItem = test[i];
     test.erase (test.begin () + i);
     delete heapItem;
   }

Ich habe das mit dem 'heapItem' absichtlich so gemacht damit ersichtlich wird, dass zwei Dinge gelöscht werden müssen.

1. Das Item im Vector
2. Das Item auf dem Heap

Herzliche Grüsse
Walter

snOOfy

@Tachyon: 2GB verbraucht es nicht hier im Beispiel sondern in meinem richtigen Programm, in dem die Elemente des Vektors Instanzen einer deutlich komplexeren Klasse sind.

@weicher: Danke, so funktioniert es

@krümelkacker: Danke für den Hinweis, ich habe nicht bedacht, was das für einen Overhead produziert. Jetzt habe ich es auch mal ohne Zeiger umgesetzt und verglichen, der Unterschied ist wirklich gigantisch.

#include <vector>;
using namespace std;

class CTest {
	double asd;
public:
	CTest(double asd) { this->asd = asd; };
};

int main() {
	// Möglichkeit 1 ohne Zeiger (10sec, 20mb Speicher)
	vector<CTest> test1;
	for (int i = 0; i < 2000000; ++ i) {
		test1.push_back(CTest(i));
	}
	for (int i = 2000000 - 1; i >= 0; -- i) {
		test1.erase(test1.begin () + i);
	}

	// Möglichkeit 2 mit Zeigern (5min, 170mb Speicher)
	vector<CTest*> test2;
	for (int i = 0; i < 2000000; ++ i)
		test2.push_back(new CTest(i));
	for (int i = 2000000 - 1; i >= 0; -- i) {
		CTest* heapItem = test2[i];
		test2.erase(test2.begin () + i);
		delete heapItem; 
	}
	system("PAUSE");
}

wx++

Wenn du große Objekte speicherst und der Vektor oft umkopiert wird (z.B. durch wahlfreies Löschen), ist die Heap-Variante aber wieder deutlich schneller.

wx++ schrieb:

Wenn du große Objekte speicherst und der Vektor oft umkopiert wird (z.B. durch wahlfreies Löschen), ist die Heap-Variante aber wieder deutlich schneller.

In so einem Fall könnte man sich Gedanken über eine std::list machen.

krümelkacker

Diese Schleife, in der Du test1.erase(...) aufrufst, ist sinnfrei. Ein einfaches test1.clear(); tut es auch.

Wenn deine Objekte aber im wirklichen Programm "komplex" sind (im Sinne eines zeitaufwändigen Kopierkonstruktors), kannst Du ja auch mal std::deque statt std::vector probieren. Wenn ich mich da nicht vertue, dürfte man sich mit einer deque beim Wachsen einiges an Kopierarbeit sparen. Die Komplexitätsklasse beim push_back ist zwar in beiden Fällen die gleiche, aber ich kann mir vorstellen, dass der Faktor ein anderer ist. Der Extremfall ist dann std::list. Aber damit verlierst Du dann den "random access".

lg,
k

ipsec

wx++ schrieb:

Wenn du große Objekte speicherst und der Vektor oft umkopiert wird (z.B. durch wahlfreies Löschen), ist die Heap-Variante aber wieder deutlich schneller.

In der Regel nicht mal das, dazu müssten die Objekte sehr groß sein. Grade im konrekten Fall ist der Unterschied zwischen einem 4-Byte-Pointer und einem 8-Byte-double minimal im Vergleich zum Allokationsoverhead.
Vielmehr ist die Faustregel, wann immer möglich zuerst die Variante ohne Zeiger probieren (einfacher, sicherer, in der Regel performanter) und erst wenn sich das als Performancebottenleck herausstellen sollte probieren, ob es mit Zeigern schneller geht.

Nexus

wx++ schrieb:

Wenn du große Objekte speicherst und der Vektor oft umkopiert wird (z.B. durch wahlfreies Löschen), ist die Heap-Variante aber wieder deutlich schneller.

Ja, aber bevor man dann sämtliche Nachteile manueller Speicherverwaltung in Kauf nimmt, kann man auch über Alternativen nachdenken. Abgesehen von anderen Containertypen kann man z.B. mit swap() einige Kopien vermeiden. Insbesondere ist damit auch eine Löschung aus std::vector in O(1) möglich, sofern die Reihenfolge unwichtig ist.

weicher

Hallo Krümelkacker

Diese Schleife, in der Du test1.erase(...) aufrufst, ist sinnfrei

Ja, aber nur in seinem Beispiel und nicht im richtigen Leben

Herzliche Grüsse
Walter

pumuckl

snOOfy schrieb:

@Tachyon: 2GB verbraucht es nicht hier im Beispiel sondern in meinem richtigen Programm, in dem die Elemente des Vektors Instanzen einer deutlich komplexeren Klasse sind.

Aha, und an Hand eines Beispiels, was den Fehler nicht produziert, sollen wir jetzt feststellen, warum der Code, den du uns nie gezeigt hast, so viel Speicher frisst? Ein kleines Analogon:

A: "Hilfe ich hab Probleme, ich kann meine Mathehausaufgaben nicht rechnen. Beispiel: 1+1. Kann mir jemand helfen?"
B: "1+1 ist 2, wo ist das Problem?"
A: "Ja 1+1 war ja nur ein Beispiel, meine Hausaufgaben sind viel schwieriger."

Was ich damit sagen will: Nimm deinen Originalcode und reduziere ihn aufs Wesentliche. Das erreichst du, indem du schrittweise unbedeutende Teile auskommentierst und dann guckst ob das Problem noch besteht. Wenns weg ist, hast du die Ursache auskommentiert. Wenn du dann alles auf ~50 Zeilen gekürzt hast stellst du den Code so wie er ist hier ins Forum. Nur so kann man dir auch sagen, wo das Problem liegt.

snOOfy

Hier hätte es doch auch die 2GB erreicht, wenn ich statt der 2 Millionen eine noch größere Zahl eingesetzt hätte. Die Frage war ja nicht, warum es die 2GB erreicht und abstürzt, sondern warum es überhaupt mehr wird. Und das wurde hier mit Hilfe meines Beispiels beantwortet, so dass ich mein Problem nun gelöst habe