std::vector: element löschen - debug assertion failed!

paulrei

Hallo Leute,
bin schon stundenlang am PC wegen diesem Problem :
ich möchte eine Funltion proggen, die alle Elemente 'zuLoeschen' aus dem Vektor entfernt.
So war meine Idee:

void EraseElems(Typ zuLoeschen) {
	for(std::vector<Typ>::const_iterator i = Elements.begin(); i != Elements.end(); i++) {
		if(*i == zuLoeschen) Elements.erase(i);
	}
}

Das einzige Problem ist, dass eine Fehlermeldung erscheint:
'Debug Assertion Failed!(...)'
Bin total mit meinem C++ am Ende!
Könnt ihr mir sagen, was ich falsch mache???
Ich glaube, es liegt an der erase() - methode.

Danke im Voraus!
Paul

Ad aCTa

Wenn du erase auf einen Iterator machst, wird dieser Iterator ungültig. Ein Inkrement oder erneutes Derefferenzieren machst du dann in irgendwelchem Speicher, was folglich scheitert.

drakon

Und um die nächste Frage auch gleich zu beantworten ein kleiner Tipp:
Schau mal, was vector::erase zurück gibt.

TyRoXx

void EraseElems(Typ zuLoeschen) {
    for(std::vector<Typ>::const_iterator i = Elements.begin(); i != Elements.end(); ) {
        if(*i == zuLoeschen)
			i = Elements.erase(i);
		else
			++i;
    }
}

Nexus

TyRoXx schrieb:

void EraseElems(Typ zuLoeschen) {
    for(std::vector<Typ>::const_iterator i = Elements.begin(); i != Elements.end(); ) {
        if(*i == zuLoeschen)
			i = Elements.erase(i);
		else
			++i;
    }
}

Statt ineffizienten Code mit O(n^2) Laufzeit zu schreiben, kann man natürlich auch bereits existierenden Standard-Code wiederverwenden und std::remove() bzw. std::remove_if() einsetzen.

Max3000

Du willst quasi Elemente mit einem gewissen Wert aus deinem Vector löschen.
Dazu ist die std::list meines Erachtens besser geeignet.
Siehe: http://www.cplusplus.com/reference/stl/list/remove/.
Hier gibt es eine remove Methode, der man als Argument den zu löschenden Wert übergibt.
Vorraussetzung ist dass dein Typ mit operator== verglichen werden kann, aber das benutzt du ja in deiner vector-Implementierung jetzt auch schon.

drakon

Max3000 schrieb:

Du willst quasi Elemente mit einem gewissen Wert aus deinem Vector löschen.
Dazu ist die std::list meines Erachtens besser geeignet.

Diese Logik verstehe ich nicht. Er hat einen vector und möchte Elemente da entfernen und du schlägst ihm eine std::list vor, ohne jeglichen Anhaltspunkt zu haben, wozu er den Container braucht..

Nexus

Max3000 schrieb:

Du willst quasi Elemente mit einem gewissen Wert aus deinem Vector löschen.
Dazu ist die std::list meines Erachtens besser geeignet.

So pauschal würde ich das nicht sagen. Vielleicht will man ja Random Access, oder vielleicht hat man viele kleine Objekte, für die sich einzelne Allokationen nicht lohnen. Durchiterieren und löschen geht für beide Container in O(n), ein Objekt über einen Iterator zu entfernen in O(1), wenn die Reihenfolge unwichtig ist.

Max3000

drakon schrieb:

Max3000 schrieb:

Du willst quasi Elemente mit einem gewissen Wert aus deinem Vector löschen.
Dazu ist die std::list meines Erachtens besser geeignet.

Diese Logik verstehe ich nicht. Er hat einen vector und möchte Elemente da entfernen und du schlägst ihm eine std::list vor, ohne jeglichen Anhaltspunkt zu haben, wozu er den Container braucht..

Der Anhaltspunkt ist, dass er Elemente mit einem gewissen Wert aus der Liste/Vector löschen will. Im Endeffekt ist doch beides eh fast das gleiche. Kommt jetzt nur noch drauf an was der Container sonst noch bringen muss.

paulrei

Hey danke für die vielen Antworten!
Ich weiß jetzt, wie ich es machen muss!

Viele Grüße
Paul

paulrei

Ich versteh das nicht...
Die Fehlermeldung kommt immer noch!
Der Debugger zeigt aber, dass es jetzt nicht mehr an der Funktion liegt.
Ich werde mir die Codestruktur wohl nochmal selber anschauen und euch nicht mit den hundert Zeilen Code im Stich lassen...
Wenn ihr es wissen wollt:
Ich will ein Timer-Objekt proggen, das einen windows.h-SetTimer() - Funktion aufruft. In einem statischen TimerProc() wird ein Vektor voll Funktiospointern aufgerufen, die jeweils einen Timer vertreten und im Falle eines Ticks ihre Aufgabe ausführen. Der Pointer muss aber im Destruktor auch wieder gelöscht werden, wobei das Programm immer einen schwerwiegenden Fehler im preincrement-operator von vector ausgibt...
Ich bin euch trotzdem sehr dankbar für eure Lösungsvorschläge.

Nexus

Max3000 schrieb:

Der Anhaltspunkt ist, dass er Elemente mit einem gewissen Wert aus der Liste/Vector löschen will.

Er will sie aus dem Vector löschen.

Max3000 schrieb:

Im Endeffekt ist doch beides eh fast das gleiche. Kommt jetzt nur noch drauf an was der Container sonst noch bringen muss.

Ja, und genau deswegen kannst du nicht sagen, dass eine Liste besser geeignet wäre. Allein an den Anforderungen hier erkenne ich keinen signifikanten Vorteil.

Max3000

Ich meinte ja nur dass die Liste eine Funktion bereitstellt mit der man Elemente durch Angabe ihres Wertes löschen kann und sich so eine Schleife mit elementweise Vergleichen spart.

Tachyon

Nexus schrieb:

Statt ineffizienten Code mit O(n^2) Laufzeit zu schreiben[...]

Nur mal so als Frage: Wieso O(n²)?

Tachyon schrieb:

Nexus schrieb:

Statt ineffizienten Code mit O(n^2) Laufzeit zu schreiben[...]

Nur mal so als Frage: Wieso O(n²)?

...weil die Elemente jedes Mal alle um eins im Vektor nachrücken müssen, wenn Du ein einziges Element aus der Mitte löschst. Die idiomatische Lösung habe ich hier leider noch nicht gesehen, obwohl sie angedeutet worden ist:

meinvektor.erase(
  std::remove(meinvektor.begin(),meinvektor.end(),zuLoeschen),
  meinvektor.end() );

Dies ist bekannt unter dem Namen "Erase-Remove Idiom".

BTW: In den folgenden Video-Lectures wird dieses Idiom auch angesprochen und sogar genau mit Illustrationen erklärt, warum das eine O(n^2) und das andere O(n) hat:
Introduction to the STL, Part 1
Introduction to the STL, Part 2

kk

Tachyon

krümelkacker schrieb:

[...]Dies ist bekannt unter dem Namen "Erase-Remove Idiom".[...]

Aber das hätte dann ja auch O(n²).

Tachyon schrieb:

krümelkacker schrieb:

[...]Dies ist bekannt unter dem Namen "Erase-Remove Idiom".[...]

Aber das hätte dann ja auch O(n²).

Nein. Hat es nicht.

Und wer die Stelle in den Videos nachgucken will: Part 2 bei 35 Minuten

Tachyon

krümelkacker schrieb:

Tachyon schrieb:

krümelkacker schrieb:

[...]Dies ist bekannt unter dem Namen "Erase-Remove Idiom".[...]

Aber das hätte dann ja auch O(n²).

Nein. Hat es nicht.

Und wer die Stelle in den Videos nachgucken will: Part 2 bei 35 Minuten

Stimmt, das hat Sinn. Danke für die Info.