Borrando elementos de un vector

Question

Quiero borrar un elemento de un vector utilizando el método de borrado. Pero el problema aquí es que no se garantiza que el elemento ocurra solo una vez en el vector. Puede estar presente varias veces y necesito borrarlas todas. Mi código es algo como esto:

void erase(std::vector<int>& myNumbers_in, int number_in) 
{ 
    std::vector<int>::iterator iter = myNumbers_in.begin(); 
    std::vector<int>::iterator endIter = myNumbers_in.end(); 
    for(; iter != endIter; ++iter) 
    { 
     if(*iter == number_in) 
     { 
      myNumbers_in.erase(iter); 
     } 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    std::vector<int> myNmbers; 
    for(int i = 0; i < 2; ++i) 
    { 
     myNmbers.push_back(i); 
     myNmbers.push_back(i); 
    } 

    erase(myNmbers, 1); 

    return 0; 
} 

Este código se bloquea, obviamente, porque yo estoy cambiando el final del vector, mientras que la iteración a través de él. ¿Cuál es la mejor manera de lograr esto? Es decir. ¿Hay alguna manera de hacer esto sin iterar a través del vector varias veces o crear una copia más del vector?

Answer 1

Usa el remove/erase idiom:

std::vector<int>& vec = myNumbers; // use shorter name 
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end()); 

Lo que sucede es que remove compacta los elementos que difieren del valor a ser removidos (number_in) en el comienzo de la vector y devuelve el iterador al primer elemento después de ese rango. Luego, erase elimina estos elementos (cuyo valor no está especificado).

Answer 2

Puede comenzar desde el final o actualizar el final cuando se borra un elemento.

Se vería algo como esto:

void erase(std::vector<int>& myNumbers_in, int number_in) 
    { 
     std::vector<int>::iterator iter = myNumbers_in.begin(); 
     std::vector<int>::iterator endIter = myNumbers_in.end(); 
     for(; iter != endIter; ++iter) 
     { 
       if(*iter == number_in) 
       { 
         myNumbers_in.erase(iter); 
         endIter = myNumbers_in.end(); 
       } 
     } 

    } 

Answer 3

Calling borrado invalidará iteradores, se puede utilizar:

void erase(std::vector<int>& myNumbers_in, int number_in) 
{ 
    std::vector<int>::iterator iter = myNumbers_in.begin(); 
    while (iter != myNumbers_in.end()) 
    { 
     if (*iter == number_in) 
     { 
      iter = myNumbers_in.erase(iter); 
     } 
     else 
     { 
      ++iter; 
     } 
    } 

} 

O usted podría utilizar std::remove_if junto con un funtor y std :: vector: : erase:

struct Eraser 
{ 
    Eraser(int number_in) : number_in(number_in) {} 
    int number_in; 
    bool operator()(int i) const 
    { 
     return i == number_in; 
    } 
}; 

std::vector<int> myNumbers; 
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end()); 

En lugar de escribir su propio functor en este caso usted co ULD utilizar std::remove:

std::vector<int> myNumbers; 
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end()); 

Answer 4

Dependiendo de por qué lo hace, usar una std::set podría ser una mejor idea que std :: vector.

Permite que cada elemento se produzca solo una vez. Si lo agrega varias veces, solo habrá una instancia para borrar de todos modos. Esto hará que la operación de borrado sea trivial. La operación de borrado también tendrá una complejidad de tiempo menor que en el vector, sin embargo, la adición de elementos es más lenta en el conjunto, por lo que podría no ser una gran ventaja.

Esto, por supuesto, no funcionará si está interesado en cuántas veces se ha agregado un elemento a su vector o el orden en que se agregaron los elementos.

Answer 5

1. Se puede recorrer gracias a la conexión índice,

2. Para evitar O (n^2) la complejidad se pueden utilizar dos índices, i - actual índice de pruebas, j - índice de almacén de elementos siguiente y al final del ciclo nuevo tamaño del vector.

código:

void erase(std::vector<int>& v, int num) 
{ 
    size_t j = 0; 
    for (size_t i = 0; i < v.size(); ++i) { 
    if (v[i] != num) v[j++] = v[i]; 
    } 
    // trim vector to new size 
    v.resize(j); 
} 

En tal caso de no tener invalidante de iteradores, la complejidad es O (n), y el código es muy concisa y que no es necesario escribir algunas clases de ayuda, aunque en algunos casos el uso de clases auxiliares puede beneficiarse con un código más flexible.

Este código no utiliza el método erase, pero resuelve su tarea.

Usando STL pura puede hacerlo de la siguiente manera (esto es similar a la respuesta de la Motti):

#include <algorithm> 

void erase(std::vector<int>& v, int num) { 
    vector<int>::iterator it = remove(v.begin(), v.end(), num); 
    v.erase(it, v.end()); 
}