deque iterators incompatible

Hey
Ich möchte aus einem deque unnütze Elemente entfernen.
Leider bekomme ich aber die Meldung "deque iterators incompatible"

if(Units.size()>0){

		deque<cUnit*>::iterator it=Units.begin();
		deque<cUnit*>::iterator it2;

		while(it!=Units.end() ){

			if((*it)->IsAlive()){
				(*it)->Update();
				(*it)->MoveToNextNode();
				++it;
			}
			else{
				it2=it;
				Units.erase(it2);

			}

		}
	}

Den zweiten Iterator habe ich verwendet um zu testen ob ich den Fehler damit umgehen kann. Leider funktioniert dies auch nicht.

So sieht es im Moment aus:

if(Units.size()>0){

		deque<cUnit*>::iterator it=Units.begin();

		while(it!=Units.end() ){

			if((*it)->IsAlive()){
				(*it)->Update();
				(*it)->MoveToNextNode();
				++it;
			}
			else{
				Units.erase(it);

			}

		}
	}

Dieser Code erzeugt den Fehler

SeppJ

Durch das Löschen aus der Mitte der deque werden alle Iteratoren ungültig. Du benutzt danach aber weiterhin den Iterator it, ohne ihn neu zu initialisieren. Daher kommt der Fehler.

volkard

Vielleicht könnte man die toten Leichen ans Ende swappen und danach erst weglöschen.

if(Units.size()>0){//das if würde ich glatt weglassen, vermute ich

		deque<cUnit*>::iterator it=Units.begin();
		deque<cUnit*>::iterator end=Units.end();

		while(it!=end ){

			if((*it)->IsAlive()){
				(*it)->Update();
				(*it)->MoveToNextNode();
				++it;
			}
			else{
				--end;
				swap(*it,*end);
			}
		}
	}
//Jetzt irgendwie alles zwischen end und .end() löschen
//Dafür gibts bestimmt was fertiges

Danke volkard. Funktioniert!

ipsec

Muss man aber nicht. erase gibt als Rückgabewert einen Iterator auf das Element zurück, was dem gelöschten folgte. Also müsste man statt Units.erase(it) nur it = Units.erase(it) schreiben und es dürfte funktonieren (aber ungetestet).

Es gibt dann ja auch noch das "erase-remove-idiom".

hustbaer

krümelkacker schrieb:

Es gibt dann ja auch noch das "erase-remove-idiom".

Das Erase-Remove-Idiom ist genau das was volkard vorgeschlagen hat.

Nexus

hustbaer schrieb:

Das Erase-Remove-Idiom ist genau das was volkard vorgeschlagen hat.

Nicht ganz, denn std::remove() und std::remove_if() swappen nicht, sondern kopieren Elemente nach vorne.

Aber ich hab mir auch schon überlegt, sowas wie von volkard zu basteln. Eventuell sogar eine Art unordered_vector , der einen std::vector wrappt. Ich habe nämlich recht oft eine Kollektion von Elementen, bei denen die Reihenfolge keine Rolle spielt und ich aus der Mitte löschen muss.

hustbaer

Oha, mein Fehler.
Na gut, ist es eben fast das selbe

Hi Nexus,

Nexus schrieb:

hustbaer schrieb:

Das Erase-Remove-Idiom ist genau das was volkard vorgeschlagen hat.

Nicht ganz, denn std::remove() und std::remove_if() swappen nicht, sondern kopieren Elemente nach vorne.

Aber ich hab mir auch schon überlegt, sowas wie von volkard zu basteln. Eventuell sogar eine Art unordered_vector , der einen std::vector wrappt. Ich habe nämlich recht oft eine Kollektion von Elementen, bei denen die Reihenfolge keine Rolle spielt und ich aus der Mitte löschen muss.

Mal ne andere Frage...
Warum verwendest du std::vector und kein std::set (bzw. std::multiset), wenn
die Reihenfolge egal ist?

Gruß,
CSpille

volkard

CSpille schrieb:

Warum verwendest du std::vector und kein std::set (bzw. std::multiset), wenn
die Reihenfolge egal ist?

Set hat andere Aufgaben. Bag wäre angemessen. Haben wir aber nicht.

Nexus

CSpille schrieb:

Mal ne andere Frage...
Warum verwendest du std::vector und kein std::set (bzw. std::multiset), wenn
die Reihenfolge egal ist?

Der Container std::set ist immer sortiert, also ist die Reihenfolge nie egal. Man muss sich ein Sortierkriterium überlegen. Elemente einzufügen kostet O(log n). Ein std::vector – mit leichten Modifikationen, was erase() betrifft – eignet sich für diesen Zweck viel besser.

volkard schrieb:

Bag wäre angemessen. Haben wir aber nicht.

Stimmt, Bag wäre ein guter Name dafür.