Löschen von Elementen aus std :: set während der Iteration

147

Ich muss einen Satz durchgehen und Elemente entfernen, die vordefinierte Kriterien erfüllen.

Dies ist der Testcode, den ich geschrieben habe:

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

Zuerst dachte ich, dass das Löschen eines Elements aus der Menge während des Durchlaufens den Iterator ungültig machen würde und das Inkrement in der for-Schleife ein undefiniertes Verhalten hätte. Obwohl ich diesen Testcode ausgeführt habe und alles gut gelaufen ist, kann ich nicht erklären, warum.

Meine Frage: Ist dies das definierte Verhalten für Standardmengen oder ist diese Implementierung spezifisch? Ich benutze übrigens gcc 4.3.3 unter Ubuntu 10.04 (32-Bit-Version).

Vielen Dank!

Vorgeschlagene Lösung:

Ist dies eine korrekte Methode zum Iterieren und Löschen von Elementen aus der Menge?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

Bearbeiten: BEVORZUGTE LÖSUNG

Ich bin auf eine Lösung gekommen, die mir eleganter erscheint, obwohl sie genau das Gleiche tut.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

Wenn innerhalb der Weile mehrere Testbedingungen vorliegen, muss jede den Iterator erhöhen. Ich mag diesen Code besser, weil der Iterator nur an einer Stelle inkrementiert wird , wodurch der Code weniger fehleranfällig und lesbarer wird.

pedromanoel
quelle
1
Gefragt und beantwortet: stackoverflow.com/questions/263945/…
Martin York
3
Eigentlich habe ich diese Frage (und andere) gelesen, bevor ich meine gestellt habe, aber da sie mit anderen STL-Containern verwandt waren und mein erster Test anscheinend funktionierte, dachte ich, dass es einen Unterschied zwischen ihnen gibt. Erst nach Matts Antwort dachte ich daran, Valgrind zu verwenden. Obwohl ich meine NEUE Lösung den anderen vorziehe, weil sie die Fehlerwahrscheinlichkeit verringert, indem der Iterator nur an einer Stelle erhöht wird. Vielen Dank für die Hilfe!
Pedromanoel
1
@pedromanoel ++itsollte etwas effizienter sein, als it++weil keine unsichtbare temporäre Kopie des Iterators verwendet werden muss. Kornels Version sorgt zwar länger dafür, dass die nicht gefilterten Elemente am effizientesten durchlaufen werden.
Alnitak
@Alnitak Ich habe nicht darüber nachgedacht, aber ich denke, dass der Unterschied in der Leistung nicht so groß wäre. Die Kopie wird auch in seiner Version erstellt, jedoch nur für die übereinstimmenden Elemente. Der Grad der Optimierung hängt also vollständig von der Struktur der Menge ab. Seit geraumer Zeit habe ich Code voroptimiert, was die Lesbarkeit und die Codierungsgeschwindigkeit beeinträchtigt ... Also habe ich einige Tests durchgeführt, bevor ich den anderen Weg eingeschlagen habe.
Pedromanoel

Antworten:

178

Dies ist implementierungsabhängig:

Standard 23.1.2.8:

Die Einfügeelemente haben keinen Einfluss auf die Gültigkeit von Iteratoren und Verweisen auf den Container, und die Löschelemente machen nur Iteratoren und Verweise auf die gelöschten Elemente ungültig.

Vielleicht könnten Sie dies versuchen - dies ist standardkonform:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Beachten Sie, dass es sich bei ++ um ein Postfix handelt und daher die alte Position zum Löschen übergibt, jedoch aufgrund des Operators zuerst zu einer neueren Position springt.

Update 27.10.2015: C ++ 11 hat den Fehler behoben. iterator erase (const_iterator position);Geben Sie einen Iterator an das Element zurück, das auf das zuletzt entfernte Element folgt (oder set::endwenn das letzte Element entfernt wurde). Der C ++ 11-Stil lautet also:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}
Kornel Kisielewicz
quelle
2
Dies funktioniert nicht mit deque MSVC2013. Entweder ist ihre Implementierung fehlerhaft oder es gibt noch eine weitere Anforderung, die verhindert, dass dies funktioniert deque. Die STL-Spezifikation ist so kompliziert, dass Sie nicht erwarten können, dass alle Implementierungen ihr folgen, geschweige denn, dass Ihr gelegentlicher Programmierer sie sich merkt. STL ist ein Monster, das nicht zu zähmen ist, und da es keine eindeutige Implementierung gibt (und Testsuiten, falls vorhanden, offenbar nicht so offensichtliche Fälle wie das Löschen von Elementen in einer Schleife abdecken), ist STL ein glänzendes, sprödes Spielzeug, mit dem man mithalten kann ein Knall, wenn man es seitwärts betrachtet.
Kuroi Neko
@MatthieuM. Dies ist in C ++ 11 der Fall. In C ++ 17 wird jetzt der Iterator (const_iterator in C ++ 11) benötigt.
tartaruga_casco_mole
18

Wenn Sie Ihr Programm über valgrind ausführen, werden eine Reihe von Lesefehlern angezeigt. Mit anderen Worten, ja, die Iteratoren werden ungültig, aber Sie haben Glück in Ihrem Beispiel (oder wirklich Pech, da Sie die negativen Auswirkungen von undefiniertem Verhalten nicht sehen). Eine Lösung hierfür besteht darin, einen temporären Iterator zu erstellen, die Temperatur zu erhöhen, den Zieliterator zu löschen und das Ziel dann auf die Temperatur festzulegen. Schreiben Sie Ihre Schleife beispielsweise wie folgt neu:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 
Matt
quelle
Wenn es nur auf die Bedingung ankommt und keine Initialisierung oder Nachoperation im Gültigkeitsbereich erforderlich ist, ist es besser, die whileSchleife zu verwenden . dh for ( ; it != numbers.end(); )ist besser sichtbar mitwhile (it != numbers.end())
iammilind
7

Sie verstehen falsch, was "undefiniertes Verhalten" bedeutet. Undefiniertes Verhalten bedeutet nicht "Wenn Sie dies tun, stürzt Ihr Programm ab oder führt zu unerwarteten Ergebnissen." Es bedeutet : „Wenn Sie das tun, Ihr Programm könnte abstürzen oder produzieren unerwartete Ergebnisse“, oder irgendetwas anderes tun, abhängig von Ihrem Compiler, Ihr Betriebssystem, die Phase des Mondes usw.

Wenn etwas ohne Absturz ausgeführt wird und sich so verhält, wie Sie es erwarten, ist dies kein Beweis dafür, dass es sich nicht um undefiniertes Verhalten handelt. Alles, was es beweist, ist, dass sein Verhalten zufällig für diesen bestimmten Lauf beobachtet wurde, nachdem es mit diesem bestimmten Compiler auf diesem bestimmten Betriebssystem kompiliert wurde.

Durch das Löschen eines Elements aus einer Menge wird der Iterator für das gelöschte Element ungültig. Die Verwendung eines ungültig gemachten Iterators ist ein undefiniertes Verhalten. Es ist einfach so passiert, dass das beobachtete Verhalten das war, was Sie in diesem speziellen Fall beabsichtigt haben; Dies bedeutet nicht, dass der Code korrekt ist.

Tyler McHenry
quelle
Oh, mir ist klar, dass undefiniertes Verhalten auch bedeuten kann: "Es funktioniert für mich, aber nicht für alle". Deshalb habe ich diese Frage gestellt, weil ich nicht wusste, ob dieses Verhalten korrekt ist oder nicht. Wenn es so wäre, würde ich einfach so gehen. Die Verwendung einer while-Schleife würde dann mein Problem lösen? Ich habe meine Frage mit meinem Lösungsvorschlag bearbeitet. Bitte probieren Sie es aus.
Pedromanoel
Das funktioniert auch bei mir. Aber wenn ich die Bedingung in if (n > 2 && n < 7 )dann ändere, erhalte ich 0 1 2 4 7 8 9. - Das besondere Ergebnis hier hängt wahrscheinlich mehr von den Implementierungsdetails der Löschmethode und den festgelegten Iteratoren ab als von der Mondphase (nicht von dieser) sollte sich jemals auf Implementierungsdetails verlassen). ;)
OnkelBens
1
STL fügt "undefiniertem Verhalten" viele neue Bedeutungen hinzu. Zum Beispiel "Microsoft hielt es für klug, die Spezifikation zu verbessern, indem es std::set::erasedie Rückgabe eines Iterators zulässt, damit Ihr MSVC-Code beim Kompilieren von gcc einen Knall bekommt" oder "Microsoft überprüft dies, std::bitset::operator[]damit sich Ihr sorgfältig optimierter Bitset-Algorithmus auf a verlangsamt crawlen beim Kompilieren mit MSVC ". STL hat keine eindeutige Implementierung und seine Spezifikation ist ein exponentiell wachsendes, aufgeblähtes Durcheinander. Kein Wunder, dass das Löschen von Elementen aus einer Schleife das Fachwissen eines erfahrenen Programmierers erfordert ...
kuroi neko
2

Nur um zu warnen, dass im Fall eines Deque-Containers alle Lösungen, die prüfen, ob der Deque-Iterator gleich numbers.end () ist, unter gcc 4.8.4 wahrscheinlich fehlschlagen werden. Das Löschen eines Elements der Deque macht den Zeiger auf numbers.end () im Allgemeinen ungültig:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Ausgabe:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

Beachten Sie, dass der Endzeiger auf dem Weg ungültig wurde, obwohl die Deque-Transformation in diesem speziellen Fall korrekt ist. Bei einer Deque einer anderen Größe ist der Fehler offensichtlicher:

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Ausgabe:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Hier ist eine der Möglichkeiten, dies zu beheben:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}
McKryak
quelle
Der Schlüssel ist do not trust an old remembered dq.end() value, always compare to a new call to dq.end().
Jesse Chisholm
2

C ++ 20 hat "einheitliche Containerlöschung" und Sie können schreiben:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

Und das funktioniert für vector, set, dequeetc. Siehe cppReference für weitere Informationen.

Marshall Clow
quelle
1

Dieses Verhalten ist implementierungsspezifisch. Um die Richtigkeit des Iterators zu gewährleisten, sollten Sie "it = numbers.erase (it);" verwenden. Anweisung, wenn Sie das Element löschen und in einem anderen Fall einfach den Iterator inerieren müssen.

Vitaly Bogdanov
quelle
1
Set<T>::eraseVersion gibt keinen Iterator zurück.
Arkaitz Jimenez
4
Eigentlich schon, aber nur bei MSVC-Implementierung. Dies ist also wirklich eine implementierungsspezifische Antwort. :)
Eugene
1
@ Eugene Es macht es für alle Implementierungen mit C ++ 11
Mastov
Einige Implementierungen von gcc 4.8with c++1yhaben einen Fehler beim Löschen. it = collection.erase(it);soll funktionieren, aber es kann sicherer seincollection.erase(it++);
Jesse Chisholm
1

Ich denke mit der STL-Methode 'remove_if ' von könnte helfen, ein seltsames Problem zu vermeiden, wenn versucht wird, das vom Iterator umschlossene Objekt zu löschen.

Diese Lösung ist möglicherweise weniger effizient.

Nehmen wir an, wir haben eine Art Container wie einen Vektor oder eine Liste namens m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

' it' ist der Iterator, der ' remove_if' zurückgibt, das dritte Argument ist eine Lambda-Funktion, die für jedes Element des Containers ausgeführt wird. Da der Container enthält Bullet::Ptr, muss die Lambda-Funktion diesen Typ (oder einen Verweis auf diesen Typ) als Argument übergeben.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

' remove_if' entfernt den Container, in dem die Lambda-Funktion true zurückgegeben hat, und verschiebt diesen Inhalt an den Anfang des Containers. Das ' it' zeigt auf ein undefiniertes Objekt, das als Müll betrachtet werden kann. Objekte von 'it' bis m_bullets.end () können gelöscht werden, da sie Speicher belegen, aber Müll enthalten. Daher wird die Methode 'erase' für diesen Bereich aufgerufen.

John Behm
quelle
0

Ich bin auf dasselbe alte Problem gestoßen und fand den folgenden Code verständlicher, was in gewisser Weise den oben genannten Lösungen entspricht.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}
Anurag
quelle
Dies funktioniert nur, wenn Sie immer jedes Element löschen . Beim OP geht es darum, die Elemente selektiv zu löschen und dennoch gültige Iteratoren zu haben.
Jesse Chisholm