Invalidierung von std::vector-Iteratoren: Eine detaillierte Erklärung

Das Konzept der Iterator-Invalidierung in std::vector wurde häufig diskutiert. Zur Verdeutlichung: Das Löschen von Vektorelementen über std::vector::erase macht Iteratoren ungültig, die genau nach dem gelöschten Element positioniert sind.

Die Gültigkeit des Iterators an der genauen Position des gelöschten Elements bleibt jedoch ungewiss. Logischerweise könnte man davon ausgehen, dass dieser Iterator gültig bleibt, da die zugrunde liegende Implementierung des Vektors normalerweise verbleibende Elemente verschiebt, um den leeren Raum zu füllen. Das genaue Verhalten und die Möglichkeit undefinierter Ergebnisse sind jedoch weniger sicher.

Betrachten Sie das folgende Beispiel, das das Entfernen ungerader Ganzzahlen aus einem Vektor veranschaulicht:

typedef std::vector vectype;
vectype vec;

for (int i = 0; i 
Während dieser Code in der Praxis scheinbar fehlerfrei ausgeführt wird, bleibt seine Gültigkeit umstritten.
Die Antwort liegt im Verhalten von Erase: Es macht tatsächlich alle Iteratoren am oder nach dem Iterator ungültig( s) zum Löschen übergeben. Es gibt jedoch auch einen neuen Iterator zurück, und zwar unmittelbar nach dem/den gelöschten Element(en) oder bis zum Ende, wenn ein solches Element nicht existiert. Dieser Iterator kann verwendet werden, um die Iteration fortzusetzen.
Es ist wichtig zu beachten, dass die obige Methode zum Entfernen ungerader Ganzzahlen ineffizient ist (O(n2)), da jede Löschung eine Verschiebung aller erfordert nachfolgende Elemente. Das Erase-Remove-Idiom bietet eine weitaus effizientere Lösung (O(n)):
bool is_odd(int x) { return (x % 2) == 1; }
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());