¿Cómo borrar y eliminar punteros a los objetos almacenados en un vector?

Question

Tengo un vector que almacena punteros a muchos objetos instanciados dinámicamente, y estoy tratando de iterar a través del vector y eliminar ciertos elementos (eliminar del vector y destruir el objeto), pero estoy teniendo problemas. Esto es lo que parece:

vector<Entity*> Entities; 
    /* Fill vector here */ 
    vector<Entity*>::iterator it; 
    for(it=Entities.begin(); it!=Entities.end(); it++) 
     if((*it)->getXPos() > 1.5f) 
      Entities.erase(it); 

Cuando cualquiera de los objetos Entity llegar a xPos> 1.5, el programa se bloquea con un error de aserción ... Alguien sabe lo que estoy haciendo mal?

estoy usando VC++ 2008.

Answer 1

Debe tener cuidado porque erase() invalidará los iteradores existentes. Sin embargo, ir devuelve un iterador nuevo válidas que puede utilizar:

for (it = Entities.begin(); it != Entities.end();) 
    if((*it)->getXPos() > 1.5f) 
     delete * it; 
     it = Entities.erase(it); 
    } 
    else { 
     ++it; 
    } 
} 

Answer 2

Después de modificar el vector, todos los iteradores pendientes de ser válida. En otras palabras, no puede modificar el vector mientras lo itera. Piensa en lo que eso hace a la memoria y verás por qué. Sospecho que su afirmación es una afirmación de "iterador inválido".

std :: vector :: erase() devuelve un iterador que debe usar para reemplazar el que estaba usando. Ver here.

Answer 3

if((*it)->getXPos() > 1.5f) 
{ 
    delete *it; 
    it = Entities.erase(it); 
} 

Answer 4

La forma "correcta" de hacer esto es usar un algoritmo:

#include <algorithm> 
#include <functional> 

// this is a function object to delete a pointer matching our criteria. 
struct entity_deleter 
{ 
    void operator()(Entity*& e) // important to take pointer by reference! 
    { 
     if (e->GetXPos() > 1.5f) 
     { 
      delete e; 
      e = NULL; 
     } 
} 

// now, apply entity_deleter to each element, remove the elements that were deleted, 
// and erase them from the vector 
for_each(Entities.begin(), Entities.end(), entity_deleter()); 
vector<Entity*>::iterator new_end = remove(Entities.begin(), Entities.end(), static_cast<Entity*>(NULL)); 
Entities.erase(new_end, Entities.end()); 

Ahora sé lo que estás pensando. Estás pensando que algunas de las otras respuestas son más cortas. Pero, (1) este método normalmente se compila para codificar más rápido; intente compararlo, (2) esta es la forma "adecuada" de STL, (3) hay menos posibilidades de errores estúpidos, y (4) es más fácil lea una vez que pueda leer el código STL. Vale la pena aprender a programar STL, y sugiero que consultes el gran libro de Scott Meyer "Effective STL", que contiene muchos consejos STL sobre este tipo de cosas.

Otro punto importante es que al no borrar elementos hasta el final de la operación, los elementos no necesitan mezclarse. GMan sugirió usar una lista para evitar esto, pero usando este método, toda la operación es O (n). El código de Neil anterior, en cambio, es O (n^2), ya que la búsqueda es O (n) y la eliminación es O (n).

Answer 5

El problema principal es que la mayoría de los iteradores de contenedor stl no admiten la adición o eliminación de elementos en el contenedor. Algunos invalidarán todos los iteradores, algunos solo invalidarán un iterador que apunta a un elemento que se elimina. Hasta que tenga una mejor idea de cómo funciona cada uno de los contenedores, deberá tener cuidado de leer la documentación sobre lo que puede y no puede hacer en un contenedor.

stl contenedores no imponen una implementación particular, pero un vector generalmente se implementa mediante una matriz debajo del capó. Si elimina un elemento al principio, todos los demás elementos se mueven. Si tuviera un iterador apuntando a uno de los otros elementos, ahora podría estar apuntando al elemento después del elemento anterior. Si agrega un elemento, es posible que sea necesario cambiar el tamaño de la matriz, por lo que se creará una nueva matriz, se copiarán los elementos anteriores y ahora su iterador apuntará a la versión anterior del vector, lo cual es malo.

Para su problema, debe ser seguro repetir el vector hacia atrás y eliminar los elementos sobre la marcha. También será un poco más rápido, ya que no se moverá por los elementos que luego eliminará.

vector<Entity*> Entities; 
/* Fill vector here */ 
vector<Entity*>::iterator it; 
for(it=Entities.end(); it!=Entities.begin();){ 
    --it; 
    if(*(*it) > 1.5f){ 
    delete *it; 
    it=Entities.erase(it); 
    } 
}