Iteration und löschen in std::map

Hi!
Ich iteriere durch eine std::map um nicht mehr benötigte Elemente zu löschen. Allerdings beginne ich nach jedem Löschvorgang am Anfang, ziemlich uneffektiv... Nach einem löschen ist das Verhalten des Iterators undefiniert, oder?

std::map<const Key*, Value*>::iterator itr = myMap.begin();

while (itr != myMap.end())
{
	Value* v = itr->second;

	v->count++;

	if (v->count > 1000)
	{
		myMap.erase(itr);
		itr = myMap.begin(); //ist itr++ sicher?
	}
}

Ach ja, wird bei einem st::map.erase() auch sicher der Destruktor des Value-Objekts aufgerufen?

Danke schön!

Nexus

Ja, Iteratoren auf gelöschte Elemente sind ungültig, und der Zugriff darauf undefiniert.

Bei assoziativen Containern kannst du allerdings

myMap.erase(itr++);

schreiben, und itr bleibt gültig (oder zeigt auf end() ). Denk aber dran, keine zusätzliche Inkrementierung mehr vorzunehmen.

minastaros

Ich bin nicht 100% sicher, aber muss ich, wenn der Value-Typ ein pointer ist, nicht zuerst ein delete auf den Pointer aufrufen? Erase löscht doch nur den Pointer an sich aus der Map, oder?
Etwas anderes ist es, wenn die eigentlichen Elemente woanders verwaltet werden und die Map nur den Zugriff darauf über die Pointer wiederspiegelt. Wie ist das hier gemeint?

SeppJ

zuse schrieb:

Nach einem löschen ist das Verhalten des Iterators undefiniert, oder?

Nein. Die Iteratoren funktionieren fein auch nach Löschen eines Elements. Nimm den Rückgabewert von erase als Startpunkt um weiter durch die map zu iterieren.

Ach ja, wird bei einem st::map.erase() auch sicher der Destruktor des Value-Objekts aufgerufen?

Selbstverständlich.

edit: Oh, viel zu langsam. Zuviel Youtube im Hintergrund .

minastaros schrieb:

Ich bin nicht 100% sicher, aber muss ich, wenn der Value-Typ ein pointer ist, nicht zuerst ein delete auf den Pointer aufrufen?

Das kommt drauf an, was du willst. Wenn du willst, dass der Speicher, auf den der Pointer zeigt, freigegeben wird, dann ja. Aber für so etwas hat man smart Pointer erfunden. Oder Pointer Container.

minastaros

SeppJ schrieb:

Nimm den Rückgabewert von erase als Startpunkt um weiter durch die map zu iterieren.

Bei map ist erase anders, geht leider nicht wie bei vector : Rückgabewert ist void oder ANzahl der gelöschten Elemente.
http://www.cplusplus.com/reference/stl/map/erase/

SeppJ schrieb:

Wenn du willst, dass der Speicher, auf den der Pointer zeigt, freigegeben wird, dann ja.

DEswegen die Frage an zuse, wie es hier gemeint ist, also: auf was zeigen die Pointer, und wer hat sie erzeugt?

Hey ich danke euch! Ja ich habe das Gefühl, die stl::map ist nicht wirklich durchdacht, gerade das Entfernen von Paaren ist umständlich/tricky (je nach Situation)...

Nein. Die Iteratoren funktionieren fein auch nach Löschen eines Elements. Nimm den Rückgabewert von erase als Startpunkt um weiter durch die map zu iterieren.

In der Doku hat erase() void als Rückgabetyp, schade. Gerade wenn man noch mit dem Value-Objekt etwas vor dem Löschen machen möchte, wirds kompliziert.

Gut, ich schau mal ob die Umsetzung klappt. Merci!

Nein die Pointer werden nicht in einer anderen Struktur verwaltet. Zum Glück, sonst hätte ich wieder ein Problem mehr. Wie gesagt, die stl::map ist irgendwie nicht durchdacht entworfen worden. Und nur wegen einigen kleinen Funktionen externe Bibliotheken einbinden möchte ich auch nicht unbedingt...

Gruß
zuse

Nexus

zuse schrieb:

gerade das Entfernen von Paaren ist umständlich/tricky (je nach Situation)...

Inwiefern ist myMap.erase(itr++); "tricky"?

zuse schrieb:

In der Doku hat erase() void als Rückgabetyp, schade.

Nicht schade. Lies meinen Post.

zuse schrieb:

Wie gesagt, die stl::map ist irgendwie nicht durchdacht entworfen worden.

Jaja, weil du das Gefühl hast, manuelle Speicherverwaltung benutzen zu müssen, ist die Map schlecht designt. Alles klar.

minastaros

zuse schrieb:

Nein die Pointer werden nicht in einer anderen Struktur verwaltet. Zum Glück, sonst hätte ich wieder ein Problem mehr.

Eigentlich hättest Du ein Problem weniger, wenn Du an dieser Stelle gar keine Pointer verwenden, sondern direkt die Elemente in die Map packen würdest.
Und dass erase sich anders verhält wird seinen Grund haben: map (und z.B. set ) sind Container, bei denen die Elemente nicht in einer Reihe angeordnet sind (zumindest von der Logik ihrer Benutzung her).

Edit: um auf den Anfang zurückzukommen: da die Elemente, auf die die Pointer zeigen, nicht woanders verwaltet werden, musst Du so nämlich vor dem erase noch das delete aufrufen.

Ja natürlich ist es nicht tricky, so dass ich da völlig am verzweifeln bin. Eine Map habe ich auch schon lange nicht mehr verwendet. Nur kann man sie auch so designen, dass man sich nicht erst Gedanken über die Verwendung machen muss. Ebenso beim erase(), da wäre es auch bspw. mit einem Flag für die Speicherfreigabe getan.
Ich benutze die STL ganz gerne, manchmal aber wird man mit Kleinigkeiten aufgehalten, schade.

Wie auch immer, es scheint zu funktionieren. Danke!

Nexus

zuse schrieb:

Nur kann man sie auch so designen, dass man sich nicht erst Gedanken über die Verwendung machen muss.

Ich finde die Verwendung eigentlich recht intuitiv, auch Zugriff mit [] und so. Hast du denn ausser erase() ein Beispiel und evtl. sogar einen Verbesserungsvorschlag? Würde mich noch interessieren, denn vielleicht habe ich mich einfach zu fest an sie gewöhnt

zuse schrieb:

Ebenso beim erase(), da wäre es auch bspw. mit einem Flag für die Speicherfreigabe getan.

Die Idee der STL-Container ist, dass sie ihre Objekte verwalten. Sie tun das komplett unabhängig davon, was diese für Typen haben, sofern die Anforderungen (Wertsemantik) erfüllt sind. Sie führen keine typ-spezifischen Aktionen durch. So eine einheitliche Semantik ist von Vorteil. ( std::vector<bool> ist die Ausnahme mit entsprechenden Nachteilen).

Aber warum musst du jetzt unbedingt Zeiger speichern? Warum nicht std::map<Key, Value> ? Übrigens, Schlüssel sind automatisch konstant.

minastaros

@zuse:
Nur nochmal zum Verdeutlichen: Man nehme eine Klasse

struct A
{
    A( int i ) : num( i ) { cout << "Constructor " << num << endl; }
    ~A( )                 { cout << "Destructor " << num << endl; }
    int num;
};

Und erzeuge die Map mit Pointern:

map< int, A* > myMap;

myMap[ 1 ] = new A( 1 );
myMap[ 2 ] = new A( 2 );

myMap.erase( 1 );
delete myMap[ 2 ];
myMap.erase( 2 );

Bei Nr. 1 gibt es ein Speicherleck. Ausgabe:

Constructor 1
Constructor 2
Destructor 2

padreigh

zund das gilt für alle STL Container. Wenn du gespeicherte Pointer aus einem std::vector<DeinTyp*> mit pop_back() wegmachst hast du ein Leck. Das liegt aber nicht an der STL sondern an dir da du der Containerklasse Zeug abverlangst für die sie nicht designed sind. In etwa als würdest du ein Auto kaufen und damit auf dem Grund des Ozeans fahren wollen - tut halt nicht. Wenn du sowas brauchst, wrapp dir die Container, Speicher keine Pointer sondern Objekte oder nutze Pointer die sich merken auf was sie pointen und intern mithalten wer alles darauf pointet und somit sicherstellen das Speicher freigegeben wird wenn der letzte Pointer aufs Objekt zerstört werden soll.

Nexus

Oder noch besser: Benutze Container, die ihren Speicher automatisch freigeben, wie Boost.PointerContainer. Sich einmal in Boost einzulesen schadet sowieso nicht...

Oh ja ihr habt recht, vielleicht wars einfach wieder zuviel gestern. Habe es an den Speicherlecks gesehen, dass ich natürlich den Speicher manuell freigeben muss...

Danke für das Beispiel, hatte mich da in irgendwas verrannt. Wird Zeit für C++0x und Smart Pointer!

Nexus

Du hast immer noch nicht gesagt, warum du überhaupt Zeiger brauchst und nicht direkt automatische Objekte speicherst.