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

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.

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.

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.