c++ - pila - Borrando elementos de un vector

eliminar un elemento de un arreglo en c

Question

Quiero borrar un elemento de un vector usando 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;
}

Obviamente, este código falla porque estoy cambiando el final del vector mientras lo recorro. ¿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

1. Puede iterar usando el acceso de índice,

2. Para evitar la complejidad de O (n ^ 2) puede usar dos índices, i - índice de prueba actual, j - índice para almacenar el siguiente ítem 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, no tiene invalidación de los iteradores, la complejidad es O (n) y el código es muy conciso y no necesita escribir algunas clases auxiliares, aunque en algunos casos el uso de clases auxiliares puede beneficiarse con un código más flexible.

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

Usando stl puro puede hacer esto de la siguiente manera (esto es similar a la respuesta de 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());
}

Answer 2

Dependiendo de por qué estás haciendo esto, usar un std::set podría ser una mejor idea que std :: vector.

Permite que cada elemento ocurra 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 menor complejidad de tiempo que en el vector, sin embargo, agregar elementos es más lento en el conjunto, por lo que puede no ser una gran ventaja.

Por supuesto, esto no funcionará si le interesa cuántas veces se ha agregado un elemento a su vector o el orden en que se agregaron los elementos.

Answer 3

El borrado de llamadas invalidará los iteradores, puede usar:

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 puede usar std::remove_if junto con un functor 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 funtor en este caso, podría usar std::remove :

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

Answer 4

Use la expresión eliminar / borrar :

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 que se eliminará ( number_in ) en el comienzo del vector y devuelve el iterador al primer elemento después de ese rango. Luego, erase elimina estos elementos (el valor de quién no está especificado).