std::vector : Elemente löschen während Iteration

[miracle max]

Hi,

ich habe einen vector, der mit einem iterator einmal komplett durchlaufen wird. Dabei kann sich herausstellen, dass eine Element gelöscht werden muss. Innerhalb der Schleife ist das ja nicht möglich, weil sonst der iterator ungültig wird. remove_if fällt leider auch weg, weil ich für jedes Element noch Speicher freigeben muss etc. - ich muss also wissen welche Elemente entfernt werden. Wie macht man sowas normalerweise?

[dot]

http://www.cplusplus.com/reference/stl/vector/erase/ schau dir mal genau an was das returned

[otze]

remove_if ist genau das Richtige. Der Punkt ist, dass du nach remove_if das Element am Ende des Vektors hast. Das zerstörst du dann, wie du vorhattest und rufst danach die entsprechende löschmethode beim Container auf.

[fr33g]

Du kannst doch auch einfach so machen:

vector< int > ivec;

for( vector< int >::iterator it = ivec.begin(); it != ivec.end(); ++it )
{
// mach was mit den daten oder prüf halt ob dieses Element gelöscht werden muss
it = ivec.erase( it );
}

Lg freeG

[brotbernd]

http://en.wikipedia.org/wiki/Erase-remove_idiom

[EOP]

fr33g schrieb:

Du kannst doch auch einfach so machen:

vector< int > ivec;

for( vector< int >::iterator it = ivec.begin(); it != ivec.end(); ++it )
{
// mach was mit den daten oder prüf halt ob dieses Element gelöscht werden muss
it = ivec.erase( it );
}

Lg freeG

Das löscht bei einer geraden Anzahl von Elementen nur jedes zweite.
Und bei einer ungeraden Anzahl crasht es ganz fürchterlich.

Genau so macht man es nicht!

[krümelkacker]

EOP schrieb:

Genau so macht man es nicht!

...schon allein wegen der schlechten Laufzeit. Ein einzelnes Element aus dem Vektor löschen kostet schon O(n), wobei n die Größe des Vektors ist.

+1 für die einzig richtige Lösung vector<>::erase(std::remove_if(...),...);

[miracle max]

Danke für die vielen Vorschläge!

otze schrieb:

remove_if ist genau das Richtige. Der Punkt ist, dass du nach remove_if das Element am Ende des Vektors hast. Das zerstörst du dann, wie du vorhattest und rufst danach die entsprechende löschmethode beim Container auf.

Ich wusste gar nicht, dass remove_if die Elemente nach hinten sortiert (anstatt sie direkt zu entfernen). Das sollte klappen.

krümelkacker schrieb:

+1 für die einzig richtige Lösung vector<>::erase(std::remove_if(...),...);

Also wie gesagt: es muss für jedes Element noch einzeln aufgeräumt werden. Alle auf einmal quasi "anonym" zu löschen scheidet leider aus

krümelkacker schrieb:

Ein einzelnes Element aus dem Vektor löschen kostet schon O(n), wobei n die Größe des Vektors ist.

Es sei denn, man trennt immer das jeweils letzte Element ab (siehe oben). Oder gibt es selbst dann noch eine bessere Lösung?

[brotbernd]

miracle max schrieb:

Also wie gesagt: es muss für jedes Element noch einzeln aufgeräumt werden. Alle auf einmal quasi "anonym" zu löschen scheidet leider aus

Erledige Aufräumarbeiten im Destruktor der Elemente.

[pumuckl]

miracle max schrieb:

Ich wusste gar nicht, dass remove_if die Elemente nach hinten sortiert (anstatt sie direkt zu entfernen).

tuts auch nicht. http://www.cplusplus.com/reference/algorithm/remove_if/ schreibt:

Notice that this function does not alter the elements past the new end, which keep their old values and are still accessible.

[miracle max]

brotbernd schrieb:

Erledige Aufräumarbeiten im Destruktor der Elemente.

Das geht nicht. Ich sag jetzt mal wozu der vector gut ist, vielleicht wirds dann klarer. Der vector verwaltet Zeiger auf rigid bodies (Starrkörper) in einer Physik-Simulation. Bei jedem Simulationsschritt gehe ich den vector durch und wende die Transformation jedes Körpers auf die zugehörige SceneNode an. Wenn ich jetzt feststelle, dass ein Körper "über den Rand gefallen ist" soll er aus der Simulation ausgeschlossen werden. Dazu muss ich folgende Schritte abarbeiten, die nicht im Destruktor ablaufen können:

- Körper aus dem vector entfernen
- Körper aus der Simulation (=world) entfernen
- Körper zerstören
- Objekte, die dem Konstruktor des Körpers übergeben wurden (wie zB Kollisionsobjekte) zerstören
- die passende SceneNode in die deletion queue einreihen

Jetzt wundere ich mich, dass es nicht so einfach möglich ist, beim Durchlauf des Containers ein paar Operationen auf einem Element auszuführen und es danach zu entfernen.
Das remove-erase-idiom geht ja leider nicht und eine Art OnErase-Callback gibts auch nicht, also werde ich die Elemente wohl mittels partition/remove_if nach hinten sortieren und einzeln löschen müssen

[miracle max]

Oh, so wie in der ersten Antwort vorgeschlagen funktionierts auch, man muss nur richtig zählen, ungefähr so:

for(it = v.begin(); it != v.end(); ) {
    if(someCondition) {
        ...
        it = v.erase(it);
    } else {
        ++it;
    }
}

Jedenfalls produziert das keinen Segfault, aber ist das auch korrekt so?

[pumuckl]

miracle max schrieb:

brotbernd schrieb:

Erledige Aufräumarbeiten im Destruktor der Elemente.

Das geht nicht.

Sagen wir, du weißt zumindest nicht wie du das machen sollst.
Was da angebracht wäre ist eine Art erweiterter Smartpointer, nennen wir ihn mal "KoerperHolder". Dann sollten die von dir genannten Schritte folgendermaßen gemacht werden:

- Körper aus dem vector entfernen -> Der vector enthält garkeine Körper, sondern nur Pointer darauf, bzw. KoerperHolder. Den kann man einfach aus dem vector entfernen, dadurch wird der Destruktor des KoerperHolder aufgerufen

- Körper aus der Simulation (=world) entfernen -> macht der Destruktor des KoerperHolder
- Körper zerstören -> macht der Destruktor des KoerperHolders - oder die Simulation ruft ein delete auf, wenn du den Körper eh daraus entfernst
**- Objekte, die dem Konstruktor des Körpers übergeben wurden (wie zB Kollisionsobjekte) zerstören
**-> Ist Aufgabe des Körper-Destruktors
- die passende SceneNode in die deletion queue einreihen ist je nachdem Aufgabe des Körper-Destruktors, des KörperHolder-Destruktors oder der Simulation::EntferneKoerper-Methode

[fr33g]

miracle max schrieb:

Oh, so wie in der ersten Antwort vorgeschlagen funktionierts auch, man muss nur richtig zählen, ungefähr so:

for(it = v.begin(); it != v.end(); ) {
    if(someCondition) {
        ...
        it = v.erase(it);
    } else {
        ++it;
    }
}

Jedenfalls produziert das keinen Segfault, aber ist das auch korrekt so?

Jops, also so meinte ich eigentlich auch mein Beispiel, war da n bissel zu hastig heut morgen.
So mach ichs jedenfalls eg immer und hatte damit eigentlich noch nie ein Problem.

Lg freeG

[Nexus]

fr33g schrieb:

So mach ichs jedenfalls eg immer und hatte damit eigentlich noch nie ein Problem.

Weil du noch nie grössere Datenmengen in kurzer Zeit bearbeiten musstest. Wie von krümelkacker erwähnt ist es absoluter Unsinn, Elemente im Vector in quadratischer Laufzeit zu löschen.

Vor allem wurde ja die Alternative std::remove_if() bereits vorgeschlagen!

[camper]

pumuckl schrieb:

miracle max schrieb:

Ich wusste gar nicht, dass remove_if die Elemente nach hinten sortiert (anstatt sie direkt zu entfernen).

tuts auch nicht. http://www.cplusplus.com/reference/algorithm/remove_if/ schreibt:

Notice that this function does not alter the elements past the new end, which keep their old values and are still accessible.

Imo inkorrekt:
1. Der Standard sagt macht keine explizite Aussage über den Inhalt der Elemente, die nicht Teil der Ergebnis-Sequenz sind.
2. Die Beschränkung zu remove_copy/remove_copy_if

Requires: Type T is EqualityComparable (20.1.1). The ranges [first, last) and [result,result+(last-first)) shall not overlap.

ist strenger als sie sein müsste, wenn man den einfachsten möglichen Algorithmus unterstellt (dann würde reichen, dass result nicht in (first, last) liegt).
3. Je nach verwendetem Iterator sind effizientere Methoden als einfaches Kopieren denkbar: z.B. im Falle von list könnte ein swap von Nodes oder splice effizienter sein; in C++0x ggf. ein move der Elemente.

[miracle max]

Ich hatte auch schon darüber nachgedacht die Bindestelle zwischen Physik- und Grafik-Engine zu abstrahieren, habe es aber der Einfachheit halber bisher vermieden. Jetzt sehe ich gerade, dass es praktisch wäre, wenn jeder Körper einen shared_ptr auf eine Kollision hätte, da ich dann schon einige Kollisionen einsparen könnte, also werde ich wohl nicht um eine weitere Klasse drumherum kommen. KörperHolder müsste dann ein shared_ptr sein, oder?

[drakon]

camper schrieb:

pumuckl schrieb:

miracle max schrieb:

Ich wusste gar nicht, dass remove_if die Elemente nach hinten sortiert (anstatt sie direkt zu entfernen).

tuts auch nicht. http://www.cplusplus.com/reference/algorithm/remove_if/ schreibt:

Notice that this function does not alter the elements past the new end, which keep their old values and are still accessible.

Imo inkorrekt:
1. Der Standard sagt macht keine explizite Aussage über den Inhalt der Elemente, die nicht Teil der Ergebnis-Sequenz sind.

Sehe ich auch so. Als ich das mal gelesen habe kam mir das auch suspekt vor.
Alleine schon, weil dann definiert sein müsste für wie lange das denn jetzt noch gültig sein müsste.

Ich habe den Satz dann eher als Erklärung verstanden, was da genau passiert, als für eine echte Bedingung.

[seldon]

Wenn es nur um diesen speziellen Anwendungsfall geht, wäre auch ein Kunstgriff mit dem Prädikat für remove_if möglich. Etwa

template <typename T>
struct remove_functor {
public:
  typedef T    argument_type;
  typedef bool result_type;

  typedef bool(*)(argument_type) predicate_type;
  typedef void(*)(argument_type) cleanup_type;

  remove_functor(predicate_type pred,
                 cleanup_type   cleanup)
    : predicate_(pred),
      cleanup_(cleanup) { }

  result_type operator()(argument_type arg) const {
    if(predicate_(arg)) {
      cleanup_(arg);
      return true;
    }

    return false;
  }

private:
  predicate_type predicate_;
  cleanup_type   cleanup_;
};

// ...

v.erase(std::remove_if(v.begin(), v.end(), remove_functor<Koerper*>(pruefung, aufraeumen)), v.end());

...wobei pruefung und aufraeumen Funktionen sind, die bestimmen, ob das Objekt gelöscht werden soll bzw. die Aufräumarbeiten durchführen. Das funktioniert, weil der Standard für remove_if garantiert, dass das Prädikat genau einmal pro Objekt im angegebenen Bereich aufgerufen wird.

ABER (WICHTIG!): Du musst hierfür sehr vorsichtig mit Exceptions sein. So, wie es im Moment da steht, sollten weder predicate_ noch cleanup_ Exceptions werfen, sonst würde der erase-Teil des erase-remove-Idioms nicht ausgeführt und du hättest die selben Zeiger mehrfach im Vektor. Das sollte in der Praxis kein riesengroßes Problem sein - Aufräumarbeiten sollten generell keine Exceptions werfen - aber falls das Prädikat etwas werfen kann, musst du dir überlegen, wie dieser Fall behandelt werden soll und die Exception davon abhalten, remove_functor zu verlassen.

shared_ptr wäre in diesem Sinne die sicherere Lösung. Übrigens kannst du shared_ptr, falls das Aufräumen nicht vollständig im Destruktor abgehandelt werden kann, im Konstruktor ein Funktionsobjekt mitgeben.

[Athar]

Dann kann man eigentlich auch gleich remove_if nachbauen, das ist letztendlich simpler.

auto result=vec.begin();
  for (auto it=vec.begin();it!=vec.end();++it)
  {
    if (!mussWeg)*result++ = *it;
    else
    { //Aufräumarbeiten...
    }
  }
  vec.resize(result-vec.begin());

auto ist passend zu ersetzen.

Eventuelle Optimierungen in der remove_if-Implementierung spielen hier wohl eher keine große Rolle, da ja eine Lösung mit quadratischer Laufzeit anscheinend auch noch akzeptabel gewesen wäre.

[Nexus]

Was ich noch nützlich finde, ist sowas:

template <class Container, typename Pred>
void ReallyRemoveIf(Container& c, Pred p)
{
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

Eventuell noch für std::list überladen und deren spezialisiertes Member- remove_if() aufrufen.