[gelöst]Verdammtes std::list::erase des letzten Elementes

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
joggel

[gelöst]Verdammtes std::list::erase des letzten Elementes

Beitrag von joggel »

Hallo,

das Problem ist ziemlich trivial, aber mich interessiert mal wie ihr damit umgeht.

Es geht darum, das ich folgenden code habe:

Code: Alles auswählen

for(std::list<Items*>::iterator iter(mListe.begin()); iter!=mListe.end(); ++iter)
{
	if(eineBedingung( (*iter) ))
	{
		//der Iterator zeigt vor dem Aufruf von <erase> auf das letzte Element
		iter = mListe.erase(iter);
	}
}
Also, es geht darum das beim aufruf von erase der Iterator auf das letzte Element zeigt.
Nach dem Aufruf ist der Iterator dann nämlich ungültig!! Also es zeigt nicht nach den letzten Listen-Element (list::end()), sondern irgendwo ins Nirvana.

Ich könnte mir jetzt "mühsam" etwas schreiben, wo ich diesen Fall abfange, aber ich würde mal gerne wissen wie ihr das handhabt.

Gruß
Zuletzt geändert von joggel am 25.02.2014, 22:30, insgesamt 1-mal geändert.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von CodingCat »

joggel hat geschrieben:Nach dem Aufruf ist der Iterator dann nämlich ungültig!! Also es zeigt nicht nach den letzten Listen-Element (list::end()), sondern irgendwo ins Nirvana.
Nein, da du korrekterweise den zurückgegebenen, garantiert gültigen Iterator entgegennimmst, hast du entweder einen Iterator auf das nachfolgende Element oder auf das Ende der Liste. Dein Problem ist, dass du den zürckgegebenen Iterator danach per for-Anweisung nochmal inkrementierst, was entweder zum Überspringen eines vermeintlichen nachfolgenden Elements führt oder aber zu einem ungütligen Iterator (hinter dem Ende der Liste ist nichts).

Schlussendlich hast du 2 Optionen, entweder den Inkrement aus der for-Anweisung in einen else-Zweig verschieben, oder aber rückwärts iterieren (meine bevorzugte Variante).

Code: Alles auswählen

// Rückwärts
for (auto iter = mListe.end(); iter != mListe.begin(); )
{
        --iter;
        if (eineBedingung(*iter))
                iter = mListe.erase(iter);
}

Code: Alles auswählen

// Bedingter Inkrement
for (auto iter = mListe.begin(); iter != mListe.end(); )
{
        if (eineBedingung(*iter))
                iter = mListe.erase(iter);
        else
                ++iter
}
Nachtrag: Rückwärtsiteration sauber/kompatibel mit Checked Iterators gemacht.
Zuletzt geändert von CodingCat am 26.02.2014, 12:34, insgesamt 1-mal geändert.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
joggel

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von joggel »

Okay, danke. Werde ich probieren.
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von Helmut »

Das mit dem Rückwärtsiterieren ist ne gute Idee, werd ich mir merken!
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von CodingCat »

Helmut hat geschrieben:Das mit dem Rückwärtsiterieren ist ne gute Idee, werd ich mir merken!
Ich sollte vielleicht noch ausführen, warum ich diese Variante bevorzuge: Sie folgt der Destruktionsreihenfolge nacheinander konstruierter Einzelobjekte. Baut man Listen vorwärts auf, dann gilt dabei prinzipiell das Gleiche: Nachfolgend eingefügte Elemente können von zuvor eingefügten Elementen abhängig sein. Somit sollte der Listenabbau in umgekehrter Reihenfolge erfolgen, abhängige Objekte sollten vor ihren Abhängigkeiten gehen.
Zuletzt geändert von CodingCat am 25.02.2014, 21:27, insgesamt 1-mal geändert.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
joggel

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von joggel »

Ich habe es nun so gelöst, nach dem ich mitbekommen habe, dass der Iterator wirklich auf list::end() zeigt..

Code: Alles auswählen

for(std::list<Items*>::iterator iter(mListe.begin()); iter!=mListe.end(); ++iter)
{
	if( eineBedingung(*ter) )
	{
		iter = mListe.erase(iter);
		if(iter == mListe.end()  )
			break;
	}
}
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von BeRsErKeR »

Etwas kürzer wäre das Folgende. Keine Ahnung ob das performant ist. Man hat zwar zwei zusätzliche Operationen falls die Bedingung erfüllt ist, allerdings spart man sich eine Verzweigung. Weiß nicht ob das hier in Hinsicht auf Branch Prediction eine große Rolle spielt. Ist auf jeden Fall kürzer zu schreiben. :D

Ich würde, davon abgesehen, aber auch die Variante von CodingCat mit der Rückwärtsiteration bevorzugen.

Code: Alles auswählen

for (auto iter(begin(mListe)); iter != end(mListe); )
{
	if (eineBedingung(*iter++))
		iter = mListe.erase(prev(iter));
}
Ohne Input kein Output.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Verdammtest std::list::erase des letzten Elementes

Beitrag von CodingCat »

BeRsErKeR hat geschrieben:[...] allerdings spart man sich eine Verzweigung. Weiß nicht ob das hier in Hinsicht auf Branch Prediction eine große Rolle spielt.
Da das Ende nur einmal erreicht wird, sollte die Vorhersage gut funktionieren. Ohnehin wird der umschließende Zweig vermutlich selten ausgeführt.
BeRsErKeR hat geschrieben:Ist auf jeden Fall kürzer zu schreiben. :D
Rein inhaltlich ist es bedeutend komplizierter und somit fehleranfälliger - ohne irgendeinen Mehrwert.

else ist übrigens keine extra Verzweigung, sollte sich jemand in der oben gezeigten Vorwärtsvariante darum sorgen.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von Helmut »

@joggel
Bei deiner Variante wird "eineBedingung" nicht für jedes Element der Liste aufgerufen, falls ein Element mitten in der Liste gelöscht wird.
joggel

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von joggel »

Helmut hat geschrieben:@joggel
Bei deiner Variante wird "eineBedingung" nicht für jedes Element der Liste aufgerufen, falls ein Element mitten in der Liste gelöscht wird.
Stimmt. Erkenne ich jetzt auch... danke!!

Der Iterator zeigt nach <erase> auf das nächste Element, beim nächsten Schleifendurchgang wird aber eben dieses nächste Element übersprungen... :?
Also doch die Variante von Cat!

[Nachtrag]
Diese Rückwärts-Variante knallt bei mir wenn ich nur ein Element in der Liste habe :/

Ich habe es jetzt wie folgende gelöst:

Code: Alles auswählen

	std::list<Items*>::iterator iter(mList.begin());
	while(iter!=mList.end())
	{
		if(eineBedingung(*iter))
			iter = mList.erase(iter);
		else
			++iter;
	}

Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von CodingCat »

joggel hat geschrieben:[Nachtrag]
Diese Rückwärts-Variante knallt bei mir wenn ich nur ein Element in der Liste habe :/
Hm, sicher dass sie dann nicht immer knallt? Ich hatte nicht bedacht, dass hier mehr als Indizes/Zeiger im Spiel sind; insbesondere Checked Iterators vertragen möglicherweise kein Dekrement des ersten Elements, selbst wenn der resultierende Iterator danach nicht mehr angerührt wird. Jetzt kommen wir leider schon wieder an die Grenzen dessen, was sich mit C++ elegant ausdrücken lässt:

Code: Alles auswählen

// Rückwärts
for (auto iter = mListe.end(); iter != mListe.begin(); )
{
        --iter;
        if (eineBedingung(*iter))
                iter = mListe.erase(iter);
}
Ich bleibe übrigens gerne bei der for-Schleife, auch wenn Teile der Anweisung leer bleiben - schlicht weil der Geltungsbereich des Iterators sowie die Bedeutung der ausgefüllten Teile aufrecht erhalten bleiben.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
joggel

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von joggel »

CodingCat hat geschrieben: Hm, sicher dass sie dann nicht immer knallt?
Nein, sicher war ich da nicht. Ich hatte es nur gemerkt als in meinem konkreten Fall nur ein Element in der Liste war....

CodingCat hat geschrieben: Ich bleibe übrigens gerne bei der for-Schleife, auch wenn Teile der Anweisung leer bleiben - schlicht weil der Geltungsbereich des Iterators sowie die Bedeutung der ausgefüllten Teile aufrecht erhalten bleiben.
Ja, deswegen versuche ich bei so etwas auch for-Schleifen zu verwenden.

Aber jetzt funktioniert ja alles.
Benutzeravatar
BeRsErKeR
Establishment
Beiträge: 689
Registriert: 27.04.2002, 22:01

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von BeRsErKeR »

CodingCat hat geschrieben:Jetzt kommen wir leider schon wieder an die Grenzen dessen, was sich mit C++ elegant ausdrücken lässt:

Code: Alles auswählen

// Rückwärts
for (auto iter = mListe.end(); iter != mListe.begin(); )
{
        --iter;
        if (eineBedingung(*iter))
                iter = mListe.erase(iter);
}
Gibt es einen speziellen Grund dafür, dass du den Iterator vor der Bedingung dekrementierst? Wenn ich nicht gerade Tomaten auf den Augen habe, ist das völlig äquivalent zu:

Code: Alles auswählen

for (auto iter = mListe.end(); iter != mListe.begin(); )
{
        if (eineBedingung(*--iter))
                iter = mListe.erase(iter);
}

Eine kleine Anmerkung noch. Ich finde es angenehmer die globalen Funktionen std::begin und std::end zu verwenden. Das hat den Vorteil, dass man keine Code-Änderungen benötigt falls aus der std::list mal ein Array wird. Ist nicht immer sinnvoll, aber ich wollte mal drauf hinweisen.
Ohne Input kein Output.
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [gelöst]Verdammtes std::list::erase des letzten Elemente

Beitrag von CodingCat »

BeRsErKeR hat geschrieben:Gibt es einen speziellen Grund dafür, dass du den Iterator vor der Bedingung dekrementierst? Wenn ich nicht gerade Tomaten auf den Augen habe, ist das völlig äquivalent zu:

Code: Alles auswählen

for (auto iter = mListe.end(); iter != mListe.begin(); )
{
        if (eineBedingung(*--iter))
                iter = mListe.erase(iter);
}
Ja, denn es gibt keinen Zusammenhang zwischen Bedingung und Iterator. Mit dieser Verkürzung versteckst du den Dekrement unsinnig, im schlimmsten Fall geht er bei Änderung der Bedingung versehentlich verloren, wird bei Erweiterung der Bedingung dupliziert oder verschwindet irgendwann in einer Short Circuit Evaluation. Vor der Bedingung ist klar, dass der Dekrement unbedingt am Anfang jeder Iteration durchgeführt wird und die Bedingung lässt sich jederzeit problemlos ändern.
BeRsErKeR hat geschrieben:Eine kleine Anmerkung noch. Ich finde es angenehmer die globalen Funktionen std::begin und std::end zu verwenden. Das hat den Vorteil, dass man keine Code-Änderungen benötigt falls aus der std::list mal ein Array wird. Ist nicht immer sinnvoll, aber ich wollte mal drauf hinweisen.
Stimme ich prinzipiell zu, aber da die Funktionen im <iterator>-Header liegen, der in der MS-Implementierung ungefragt den schlimmsten Teil der STL nach sich zieht, bin ich minimalistisch geworden. :evil: Weiterhin gibt es da ein konzeptuelles Problem, du solltest die Funktionen nämlich dann ohne std::-Qualifizierung aufrufen, d.h. du brauchst entweder global ein using std::begin; using std::end; oder musst das vor jedem Aufruf einfügen (und das nur für Array-Kompatibilität!). Leider wie so oft seitens STL ein winziges Bisschen zu kurz gedacht.

Was lernen wir aus dieser Missorganisation: Häufig genutzte Funktionalität besser nach Nutzungsfrequenz als nach artifiziellen Modulen in Headers einordnen; insbesondere so modularisieren, dass häufig genutzte Funktionalität nicht durch ungeschickte Modulzuordnung indirekt von selten genutzter Funktionalität abhängt.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Antworten