Come eliminare un elemento da un vettore mentre lo si scorre sopra?

Question

Sono in loop attraverso un vettore con un ciclo come for(int i = 0; i < vec.size(); i++). All'interno di questo ciclo, controllo una condizione sull'elemento di quell'indice vettoriale, e se una certa condizione è vera, voglio cancellare quell'elemento.

Come si elimina un elemento vettoriale mentre si esegue il ciclo su di esso senza arrestarsi in modo anomalo?

Answer 1

Il modo idiomatico per rimuovere tutti gli elementi da un contenitore STL che soddisfano un determinato predicato è utilizzare lo remove-erase idiom. L'idea è quella di spostare il predicato (che è la funzione che produce vero o falso per qualche elemento) in una data funzione, dicono pred e poi:

static bool pred(const std::string &s) { 
    // ... 
} 

std::vector<std::string> v; 
v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()); 

Se ti ostini a usare indici, non si dovrebbe incrementare l'indice per ogni elemento, ma solo per coloro che non vengono rimossi:

std::vector<std::string>::size_type i = 0; 
while (i < v.size()) { 
    if (shouldBeRemoved(v[i])) { 
     v.erase(v.begin() + i); 
    } else { 
     ++i; 
    } 
} 

Tuttavia, questo non è solo più codice e meno idiomatica (leggi: i programmatori C++ in realtà hanno a guardare il codice mentre il 'cancellare & rimuovere 'l'idioma dà immediatamente un'idea di cosa sta succedendo), ma anche molto meno efficiente perché i vettori memorizzano th Gli elementi di EIR in un blocco contiguo di memoria, quindi cancellando posizioni diverse dalla fine del vettore, spostano anche tutti gli elementi dopo che il segmento è stato cancellato nelle loro nuove posizioni.

Answer 2

Iterare sul vettore all'indietro. In questo modo, non ottieni la possibilità di accedere agli elementi che non hai ancora visitato.

Answer 3

Utilizzare Erase-Remove Idiom, utilizzando remove_if con un predicato per specificare la condizione.

Answer 4

Se non è possibile utilizzare rimuovere/cancellare (ad esempio perché non si vuole utilizzare lambda o scrivere un predicato), utilizzare il linguaggio standard per la rimozione elemento contenitore sequenza:

for (auto it = v.cbegin(); it != v.cend() /* not hoisted */; /* no increment */) 
{ 
    if (delete_condition) 
    { 
     it = v.erase(it); 
    } 
    else 
    { 
     ++it; 
    } 
} 

Se possibile, però, preferiscono rimuovere/cancellare:

#include <algorithm> 

v.erase(std::remove_if(v.begin(), v.end(), 
         [](T const & x) -> bool { /* decide */ }), 
     v.end()); 

Answer 5

mi rendo conto che si sta chiedendo in particolare sulla rimozione dal vettore, ma volevo solo sottolineare che è costoso per rimuovere elementi da uno std :: vector in quanto tutti gli elementi dopo l'elemento rimosso deve essere copiati in una nuova posizione Se vuoi rimuovere elementi dal contenitore dovresti usare una lista std ::. Il metodo std :: list :: erase (item) restituisce persino l'iteratore che punta al valore dopo quello appena cancellato, quindi è facile da usare in un ciclo for o while. Anche la cosa bella con std :: list è che gli iteratori che puntano a elementi non cancellati rimangono validi per tutta la durata dell'elenco. Si veda ad esempio lo docs at cplusplus.com.

Detto questo, se non si ha scelta, un trucco che può funzionare è semplicemente creare un nuovo vettore vuoto e aggiungere elementi dal primo vettore, quindi utilizzare std :: swap (oldVec, newVec), che è molto efficiente (nessuna copia, cambia solo i puntatori interni).

Answer 6

if(vector_name.empty() == false) { 
    for(int i = vector_name.size() - 1; i >= 0; i--) 
    { 
     if(condition) 
      vector_name.erase(vector_name.at(i)); 
    } 
} 

Questo funziona per me. E non c'è bisogno di pensare agli indici che sono già stati cancellati.