std :: invalidazione iteratore vettoriale

Question

Ci sono state alcune domande su questo problema in precedenza; la mia comprensione è che chiamando std::vector::erase invaliderà solo gli iteratori che si trovano in una posizione dopo l'elemento cancellato. Tuttavia, dopo aver cancellato un elemento, l'iteratore in quella posizione è ancora valido (a patto, ovviamente, che non punti a end() dopo la cancellazione)?

La mia comprensione di come un vettore sarebbe implementato sembra suggerire che l'iteratore sia utilizzabile in modo definitivo, ma non sono del tutto sicuro che possa portare a un comportamento indefinito.

Come esempio di ciò di cui sto parlando, il seguente codice rimuove tutti gli interi dispari da un vettore. Questo codice causa un comportamento indefinito?

typedef std::vector<int> vectype; 
vectype vec; 

for (int i = 0; i < 100; ++i) vec.push_back(i); 

vectype::iterator it = vec.begin(); 
while (it != vec.end()) { 
    if (*it % 2 == 1) vec.erase(it); 
    else ++it; 
} 

Il codice funziona correttamente sulla mia macchina, ma questo non mi convince che sia valido.

Answer 1

dopo la cancellazione di un elemento, è l'iteratore in quella posizione ancora valido

No; tutti gli iteratori a/dopo l'iteratore/i passati a erase vengono invalidati.

Tuttavia, erase restituisce un nuovo iteratore che punta all'elemento immediatamente dopo l'elemento (s) che sono stati cancellati (o alla fine se non esiste tale elemento). È possibile utilizzare questo iteratore per riprendere l'iterazione.

---

Si noti che questo particolare metodo di rimozione di elementi dispari è del tutto inefficiente: ogni volta che si rimuovere un elemento, tutti gli elementi dopo che deve essere spostato di una posizione verso nel vettore sinistra (questo è O (n)). È possibile eseguire questa operazione in modo molto più efficiente utilizzando erase-remove idiom (O (n)). È possibile creare un is_odd predicato:

bool is_odd(int x) { return (x % 2) == 1; } 

allora questo può essere passato a remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end()); 

Answer 2

Oppure:

class CIsOdd 
{ 
public: 
    bool operator()(const int& x) { return (x % 2) == 1; } 
}; 

vec.erase(std::remove_if(vec.begin(), vec.end(), CIsOdd()), vec.end());