Können Sie Elemente aus einer std :: -Liste entfernen, während Sie sie durchlaufen?

239

Ich habe Code, der so aussieht:

for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
    bool isActive = (*i)->update();
    //if (!isActive) 
    //  items.remove(*i); 
    //else
       other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);

Ich möchte inaktive Elemente sofort nach dem Aktualisieren entfernen, um ein erneutes Durchlaufen der Liste zu vermeiden. Wenn ich jedoch die auskommentierten Zeilen hinzufüge, wird folgende Fehlermeldung i++angezeigt: "Listeniterator nicht inkrementierbar". Ich habe einige Alternativen ausprobiert, die die for-Anweisung nicht erhöht haben, aber ich konnte nichts zum Laufen bringen.

Was ist der beste Weg, um Elemente zu entfernen, während Sie eine std :: -Liste durchlaufen?

AShelly
quelle
Ich habe keine Lösung gesehen, die darauf basiert, rückwärts zu iterieren. Ich habe einen solchen gepostet .
sancho.s ReinstateMonicaCellio

Antworten:

286

Sie müssen zuerst den Iterator inkrementieren (mit i ++) und dann das vorherige Element entfernen (z. B. indem Sie den von i ++ zurückgegebenen Wert verwenden). Sie können den Code wie folgt in eine while-Schleife ändern:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // alternatively, i = items.erase(i);
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}
Michael Kristofik
quelle
7
Eigentlich funktioniert das nicht garantiert. Mit "erase (i ++);" wissen wir nur, dass der vorinkrementierte Wert an erase () übergeben wird und das i vor dem Semikolon inkrementiert wird, nicht unbedingt vor dem Aufruf von erase (). "iterator prev = i ++; erase (prev);" wird sicher funktionieren, ebenso wie der Rückgabewert
James Curran
58
Nein James, ich werde vor dem Aufruf von erase inkrementiert und der vorherige Wert wird an die Funktion übergeben. Die Argumente einer Funktion müssen vollständig ausgewertet werden, bevor die Funktion aufgerufen wird.
Brian Neal
28
@ James Curran: Das stimmt nicht. ALLE Argumente werden vollständig ausgewertet, bevor eine Funktion aufgerufen wird.
Martin York
9
Martin York ist richtig. Alle Argumente für einen Funktionsaufruf werden vollständig ausgewertet, bevor eine Funktion aufgerufen wird, keine Ausnahmen. So funktioniert Funktion einfach. Und es hat nichts mit Ihrem Beispiel foo.b (i ++). C (i ++) zu tun (das auf jeden Fall undefiniert ist)
jalf
75
Die alternative Verwendung i = items.erase(i)ist sicherer, da sie für eine Liste gleichwertig ist, aber trotzdem funktioniert, wenn jemand den Container in einen Vektor ändert. Mit einem Vektor verschiebt erase () alles nach links, um das Loch zu füllen. Wenn Sie versuchen, das letzte Element mit Code zu entfernen, der den Iterator nach dem Löschen inkrementiert, wird das Ende nach links und der Iterator nach rechts verschoben - nach dem Ende. Und dann stürzt du ab.
Eric Seppanen
133

Du willst machen:

i= items.erase(i);

Dadurch wird der Iterator korrekt aktualisiert und zeigt auf den Speicherort nach dem entfernten Iterator.

MSN
quelle
80
Seien Sie gewarnt, dass Sie diesen Code nicht einfach in Ihre for-Schleife ablegen können. Andernfalls überspringen Sie jedes Mal ein Element, wenn Sie eines entfernen.
Michael Kristofik
2
kann er nicht tun i--; jedes Mal nach seinem Code, um ein Überspringen zu vermeiden?
Enthusiastgeek
1
@enthusiasticgeek, was passiert wenn i==items.begin()?
MSN
1
@enthusiasticgeek, an diesem Punkt solltest du einfach tun i= items.erase(i);. Es ist die kanonische Form und kümmert sich bereits um all diese Details.
MSN
6
Michael weist auf ein großes "Gotcha" hin, ich musste mich gerade mit der gleichen Sache befassen. Die einfachste Methode, dies zu vermeiden, bestand darin, die for () - Schleife in eine Weile () zu zerlegen und vorsichtig mit dem Inkrementieren umzugehen
Anne Quinn,
22

Sie müssen die Kombination aus Kristos Antwort und MSNs ausführen:

// Note: Using the pre-increment operator is preferred for iterators because
//       there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
//       along the way you can safely save end once; otherwise get it at the
//       top of each loop.

std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end  = items.end();

while (iter != end)
{
    item * pItem = *iter;

    if (pItem->update() == true)
    {
        other_code_involving(pItem);
        ++iter;
    }
    else
    {
        // BTW, who is deleting pItem, a.k.a. (*iter)?
        iter = items.erase(iter);
    }
}

Das effizienteste und SuperCool® STL-versierte Ding wäre natürlich ungefähr so:

// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
    if (m_needsUpdates == true)
    {
        m_needsUpdates = other_code_involving(this);
    }

    return (m_needsUpdates);
}

// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));
Mike
quelle
Ich habe Ihre SuperCool-Methode in Betracht gezogen. Ich zögerte, dass der Aufruf von remove_if nicht klar macht, dass das Ziel darin besteht, die Elemente zu verarbeiten, anstatt sie aus der Liste der aktiven Elemente zu entfernen. (Die Elemente werden nicht gelöscht, da sie nur inaktiv und nicht mehr benötigt werden.)
AShelly
Ich nehme an, du hast recht. Einerseits neige ich dazu, vorzuschlagen, den Namen "Update" zu ändern, um die Dunkelheit zu beseitigen, aber die Wahrheit ist, dass dieser Code den Funktoren gefällt, aber auch alles andere als nicht dunkel ist.
Mike
Fairer Kommentar: Korrigieren Sie entweder die while-Schleife, um end zu verwenden, oder löschen Sie die nicht verwendete Definition.
Mike
10

Verwenden Sie den Algorithmus std :: remove_if.

Bearbeiten: Die Arbeit mit Sammlungen sollte wie folgt aussehen: 1. Sammlung vorbereiten. 2. Prozesssammlung.

Das Leben wird einfacher, wenn Sie diese Schritte nicht mischen.

  1. std :: remove_if. oder list :: remove_if (wenn Sie wissen, dass Sie mit list und nicht mit der TCollection arbeiten)
  2. std :: for_each
Mykola Golubyev
quelle
2
std :: list verfügt über eine remove_if-Mitgliedsfunktion, die effizienter als der remove_if-Algorithmus ist (und nicht die Redewendung "remove-erase" erfordert).
Brian Neal
5

Hier ist ein Beispiel mit einer forSchleife, die die Liste iteriert und den Iterator erhöht oder erneut validiert, falls ein Element während des Durchlaufs der Liste entfernt wird.

for(auto i = items.begin(); i != items.end();)
{
    if(bool isActive = (*i)->update())
    {
        other_code_involving(*i);
        ++i;

    }
    else
    {
        i = items.erase(i);

    }

}

items.remove_if(CheckItemNotActive);
David Cormack
quelle
4

Die Alternative zur Loop-Version zu Kristos Antwort.

Sie verlieren etwas an Effizienz, gehen beim Löschen vorwärts und dann wieder vorwärts, aber im Austausch für das zusätzliche Iteratorinkrement können Sie den Iterator im Schleifenbereich deklarieren lassen und den Code etwas sauberer aussehen lassen. Was zu wählen ist, hängt von den Prioritäten des Augenblicks ab.

Die Antwort war völlig verspätet, ich weiß ...

typedef std::list<item*>::iterator item_iterator;

for(item_iterator i = items.begin(); i != items.end(); ++i)
{
    bool isActive = (*i)->update();

    if (!isActive)
    {
        items.erase(i--); 
    }
    else
    {
        other_code_involving(*i);
    }
}
Rafael Gago
quelle
1
Das habe ich auch benutzt. Ich bin mir jedoch nicht sicher, ob es garantiert funktioniert, wenn das zu entfernende Element das erste Element im Container ist. Für mich funktioniert es, denke ich, aber ich bin mir nicht sicher, ob es plattformübergreifend portierbar ist.
Trololo
Ich habe nicht "-1" gemacht, aber Listeniterator kann nicht dekrementieren? Zumindest habe ich eine Behauptung von Visual Studio 2008.
Meilenma
Solange die verknüpfte Liste als kreisförmige doppelt verknüpfte Liste mit einem Head / Stub-Knoten implementiert ist (wird als end () rbegin () verwendet und wenn leer als begin () und rend ()), funktioniert dies. Ich kann mich nicht erinnern, auf welcher Plattform ich dies verwendet habe, aber es hat auch bei mir funktioniert, da die oben genannte Implementierung die häufigste Implementierung für eine std :: list ist. Es ist jedoch fast sicher, dass dies ein undefiniertes Verhalten (nach dem C ++ - Standard) ausnutzt. Verwenden Sie es also besser nicht.
Rafael Gago
re: iterator cannot be decrementedDie eraseMethode benötigt a random access iterator. Einige Sammlungsimplementierungen bieten eine, forward only iteratordie die Behauptung verursacht.
Jesse Chisholm
@ Jesse Chisholm Die Frage betraf eine std :: list, keinen beliebigen Container. std :: list bietet Lösch- und bidirektionale Iteratoren.
Rafael Gago
4

Ich habe es zusammengefasst, hier sind die drei Methoden mit Beispiel:

1. mit whileSchleife

list<int> lst{4, 1, 2, 3, 5};

auto it = lst.begin();
while (it != lst.end()){
    if((*it % 2) == 1){
        it = lst.erase(it);// erase and go to next
    } else{
        ++it;  // go to next
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

2. Verwenden der remove_ifMitgliederfunktion in der Liste:

list<int> lst{4, 1, 2, 3, 5};

lst.remove_if([](int a){return a % 2 == 1;});

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

3. Verwenden der std::remove_ifFunktion in Kombination mit der Elementfunktion erase:

list<int> lst{4, 1, 2, 3, 5};

lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
    return a % 2 == 1;
}), lst.end());

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

4. Verwenden Sie die forSchleife, und beachten Sie, dass der Iterator aktualisiert wird:

list<int> lst{4, 1, 2, 3, 5};

for(auto it = lst.begin(); it != lst.end();++it){
    if ((*it % 2) == 1){
        it = lst.erase(it);  erase and go to next(erase will return the next iterator)
        --it;  // as it will be add again in for, so we go back one step
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2 
Jayhello
quelle
2

Durch das Entfernen werden nur die Iteratoren ungültig, die auf die entfernten Elemente verweisen.

In diesem Fall ist i nach dem Entfernen von * i ungültig und Sie können es nicht inkrementieren.

Sie können zuerst den Iterator des Elements speichern, das entfernt werden soll, dann den Iterator erhöhen und dann den gespeicherten entfernen.

anand
quelle
2
Die Verwendung des Post-Inkrements ist weitaus eleganter.
Brian Neal
2

Wenn Sie sich std::listeine Warteschlange vorstellen, können Sie alle Elemente, die Sie behalten möchten, aus der Warteschlange entfernen und in die Warteschlange stellen, aber nur das Element, das Sie entfernen möchten, aus der Warteschlange entfernen (und nicht in die Warteschlange stellen). Hier ist ein Beispiel, in dem ich 5 aus einer Liste mit den Nummern 1-10 entfernen möchte ...

std::list<int> myList;

int size = myList.size(); // The size needs to be saved to iterate through the whole thing

for (int i = 0; i < size; ++i)
{
    int val = myList.back()
    myList.pop_back() // dequeue
    if (val != 5)
    {
         myList.push_front(val) // enqueue if not 5
    }
}

myList wird jetzt nur die Nummern 1-4 und 6-10 haben.

Alex Bagg
quelle
Interessanter Ansatz, aber ich befürchte, dass es langsam sein könnte.
SG7
2

Durch das Rückwärtslaufen wird vermieden, dass ein Element auf die verbleibenden zu durchlaufenden Elemente gelöscht wird:

typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
    --it;
    bool remove = <determine whether to remove>
    if ( remove ) {
        items.erase( it );
    }
}

PS: Siehe dies z. B. in Bezug auf die Rückwärtsiteration.

PS2: Ich habe nicht gründlich getestet, ob es gut löschende Elemente an den Enden handhabt.

sancho.s ReinstateMonicaCellio
quelle
re: avoids the effect of erasing an element on the remaining elementsfür eine Liste wahrscheinlich ja. Für einen Vektor vielleicht nicht. Das ist bei beliebigen Sammlungen nicht garantiert. Zum Beispiel kann eine Karte kann entscheiden , sich neu zu gewichten.
Jesse Chisholm
1

Du kannst schreiben

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive) {
        i = items.erase(i); 
    } else {
        other_code_involving(*i);
        i++;
    }
}

Sie können äquivalenten Code mit schreiben std::list::remove_if, der weniger ausführlich und expliziter ist

items.remove_if([] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
});

Das std::vector::erase std::remove_ifIdiom sollte verwendet werden, wenn Elemente ein Vektor anstelle einer Liste sind, um die Komplexität bei O (n) zu halten - oder wenn Sie generischen Code schreiben und Elemente möglicherweise ein Container sind, in dem einzelne Elemente (wie ein Vektor) nicht effektiv gelöscht werden können.

items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
}));
J. Kalz
quelle
-4

Ich denke du hast dort einen Fehler, ich codiere so:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
             itAudioChannel != audioChannels.end(); )
{
    CAudioChannel *audioChannel = *itAudioChannel;
    std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
    itAudioChannel++;

    if (audioChannel->destroyMe)
    {
        audioChannels.erase(itCurrentAudioChannel);
        delete audioChannel;
        continue;
    }
    audioChannel->Mix(outBuffer, numSamples);
}
Marcin Skoczylas
quelle
Ich vermute, dies wurde für Stilvorlieben herabgestuft, da es funktional zu sein scheint. Ja, sicher, (1) es wird ein zusätzlicher Iterator verwendet, (2) das Iteratorinkrement befindet sich an einer ungeraden Stelle für eine Schleife, ohne einen guten Grund, es dort abzulegen, (3) es erledigt die Kanalarbeit nach der Entscheidung, stattdessen zu löschen von vorher wie im OP. Aber es ist keine falsche Antwort.
Jesse Chisholm