Assertion bei vector.erase()



  • Hi,

    ich habe diesen Code:

    auto it    = mValues.begin();
    auto itEnd = mValues.end();
    while(it != itEnd) {
       if((*it).expired()) 
          it = mValues.erase(it);
       else
          ++it;
    }
    

    Leider kriege ich immer in der while Zeile eine Debug Assertion:

    vector iterators incompatible

    Wo is da das Problem? Und wie fixe ich das? 😕



  • Mach es so:

    mValues.erase(std::remove_if(mValues.begin(), mValues.end(), [&](typename mValues::value_type const& cur)
    {
      return cur.expired();
    }, mValues.end());
    

    Google nach dem remove erase Idiom. 😉



  • Ich weiß jetzt noch immer nicht, was das Problem ist.

    Und den Code von dir will ich nicht benutzen, weil ich den ziemlich unleserlich (alias hässlich) finde.



  • Ethons Code ist sogar ziemlich elegant. Durch das remove-erase Idiom auch O(n)
    Die formatierung ist eigentlich okay. Wenn du schon viel mit der STL gearbeitet hast, sollte das kein Problem für dich sein.



  • und es läuft nur unter C++0x. aber du benutzt ja schon auto. Und ich fidns auch hässlich.

    Mach das:

    auto it    = mValues.begin();
    while(it != mValues.end()) {
       if((*it).expired())
          it = mValues.erase(it);
       else
          ++it;
    }
    

    itEnd verändert sich durch den Aufruf von Erase.



  • otze schrieb:

    und es läuft nur unter C++0x. aber du benutzt ja schon auto. Und ich fidns auch hässlich.

    Mach das:

    auto it    = mValues.begin();
    while(it != mValues.end()) {
       if((*it).expired())
          it = mValues.erase(it);
       else
          ++it;
    }
    

    itEnd verändert sich durch den Aufruf von Erase.

    Funktioniert und ist übersichtlich. Danke! 👍



  • Vectoror schrieb:

    Und den Code von dir will ich nicht benutzen, weil ich den ziemlich unleserlich (alias hässlich) finde.

    Mein Problem war dass ich nicht weiß was in deinem Container steckt, denn du hast es uns nicht mitgeteilt.
    Deswegen habe ich dir einen Code geliefert, der auf jeden Fall funktioniert.

    So unleserlich finde ich den Code nicht, aber du könntest ihn zb so umformatieren:

    auto Compare = [&](DEINTYP const& cur) { return cur.expired(); }
    auto begin = std::remove_if(mValues.begin(), mValues.end(), Compare);
    mValues.erase(begin, mValues.end());
    


  • Vectoror schrieb:

    Funktioniert und ist übersichtlich

    und elend langsam. O(n²) ist hier wirklich unnötig.

    Nimm std::remove_if() , dafür ist es da. Statt eines Lambda-Ausdrucks kannst du expired() mit std::mem_fn() binden.



  • Nexus schrieb:

    Vectoror schrieb:

    Funktioniert und ist übersichtlich

    und elend langsam. O(n²) ist hier wirklich unnötig.

    Nimm std::remove_if() , dafür ist es da. Statt eines Lambda-Ausdrucks kannst du expired() mit std::mem_fn() binden.

    Abgesehen davon, dass hier Geschwindigkeit keine Rolle spielt: Wieso n^2? Das sollte doch O(n) sein.


  • Administrator

    @Nexus und Ethon,
    Das bringt nicht viel, was ihr da sagt. Ich glaube kaum, dass er verstehen wird, wieso hier O(n2) sein soll.

    @Vectoror,
    Du solltest dir mal den Algorithmus von std::remove_if anschauen. Der Algorithmus kopiert jeweils nur das Element nach vorne, welches gültig bleiben wird und gibt dann einen Iterator auf das Element hinter dem letzten gültigen zurück. Wodurch man einfach den Rest dahinter löschen kann.
    Der Nachteil von erase ist, dass immer alle Objekte hinter der Position wo du löschst, nach vorne kopiert werden, auch diejenigen, welche du eigentlich löschen möchtest. Mit deinem Algorithmus kopierst du somit Objekte, welche du verwerfen möchtest. Diese unnötigen Kopien entstehen beim Erase-Remove Idiom nicht.

    Grüssli



  • Vectoror schrieb:

    Abgesehen davon, dass hier Geschwindigkeit keine Rolle spielt

    Trotzdem darf man eine Lösung bevorzugen, die 1. mit weniger Code auskommt, 2. ohne irgendwelche Kosten schneller ist und 3. Standardmittel verwendet, statt sie schlecht nachzubauen.

    Vectoror schrieb:

    Wieso n^2? Das sollte doch O(n) sein.

    std::vector::erase() hat O(n), weil es nachfolgende Elemente verschieben muss.


Anmelden zum Antworten