¿Cómo se pueden borrar elementos de un vector mientras se itera?
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 aparezca 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 obviamente falla porque estoy cambiando el final del vector mientras lo repito. ¿Cuál es la mejor manera de lograr esto? Es decir, ¿hay alguna forma de hacer esto sin iterar el vector varias veces o crear una copia más del vector?
Desde C++ 20, existen funciones independientes std::erasequestd::erase_if funcionan en contenedores y simplifican las cosas considerablemente:
std::erase(myNumbers, number_in);
// or
std::erase_if(myNumbers, [&](int x) { return x == number_in; });
Antes de C++ 20, usaba el modismo borrar-eliminar :
std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());
// or
vec.erase(std::remove_if(vec.begin(), vec.end(), [&](int x) {
return x == number_in;
}), vec.end());
Lo que pasa es que std::removecompacta los elementos que difieren del valor a eliminar ( number_in) al inicio del vectory devuelve el iterador al primer elemento después de ese rango. Luego eraseelimina estos elementos (cuyo valor no está especificado).
Llamar a borrar invalidará los iteradores, puedes 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 podrías 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, puede usar std::remove :
std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());
En C++11 podrías usar una lambda en lugar de un funtor:
std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());
En C++ 17 std::experimental::erase y std::experimental::erase_if también están disponibles, en C++ 20 (finalmente) se les cambia el nombre a std::erase y std::erase_if ( nota: en Visual Studio 2019, deberá cambiar su versión del lenguaje C++ a la última versión experimental para obtener soporte ):
std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda
o:
std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
Dependiendo de por qué esté haciendo esto, usar std::set podría ser una mejor idea que std::vector.
Permite que cada elemento ocurra solo una vez. Si lo agrega varias veces, de todos modos solo habrá una instancia para borrar. 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, agregar elementos es más lento en el conjunto, por lo que podría no ser una gran ventaja.
Por supuesto, esto no funcionará si está interesado en cuántas veces se agregó un elemento a su vector o en el orden en que se agregaron los elementos.
Hay std::erase y std::erase_if desde C++ 20 que combina el modismo remove-erase.
std::vector<int> nums;
...
std::erase(nums, targetNumber);
o
std::vector<int> nums;
...
std::erase_if(nums, [](int x) { return x % 2 == 0; });
Si cambia su código de la siguiente manera, puede realizar una eliminación estable.
void atest(vector<int>& container,int number_in){
for (auto it = container.begin(); it != container.end();) {
if (*it == number_in) {
it = container.erase(it);
} else {
++it;
}
}
}
Sin embargo, también se puede utilizar un método como el siguiente.
void btest(vector<int>& container,int number_in){
container.erase(std::remove(container.begin(), container.end(), number_in),container.end());
}
Si debemos preservar el orden de nuestra secuencia (digamos, si la mantenemos ordenada por alguna propiedad interesante), entonces podemos usar uno de los anteriores. Pero si la secuencia es solo una bolsa de valores cuyo orden no nos importa en absoluto, entonces podríamos considerar mover elementos individuales desde el final de la secuencia para llenar cada nuevo espacio a medida que se crea:
void ctest(vector<int>& container,int number_in){
for (auto it = container.begin(); it != container.end(); ) {
if (*it == number_in) {
*it = std::move(container.back());
container.pop_back();
} else {
++it;
}
}
}
A continuación se muestran sus resultados de referencia: CLang 15.0:
Gcc 12.2:
