Google
 

lunes, octubre 09, 2006

Como borrar elementos de una std::list

Borrar un elemento de una lista STL no es tan fácil como parece pues si hacemos:
1 for(std::list<int>::iterator i = lista.begin(); i != lista.end(); i++)
2 if((*i) < 0)
3 lista.erase(i);
Tendremos una bonita lista corrupta, pues no tenemos en cuenta que los elementos anterior y posterior del que estemos borrando continúan apuntando al elemento borrado. La función erase realmente arregla esos punteros anterior y posterior, pero el iterador que estamos usando actualmente mantiene guardados en memoria los punteros anteriores al borrado. La solución es mover el iterador antes de borrar:
 1 std::list<int>::iterator i = lista.begin();
2 while(i != lista.end())
3 if((*i) < 0) {
4 std::list<int>::iterator j = i;
5 i++; // Movemos antes de borrar nada
6 lista.erase(j); // Aqui borramos el elemento
7 } else
8 i++;
Otra opción es usar la función remove_if pues ya tiene todo esto en cuenta. Tened cuidado porque hay dos funciones remove_if; la del algoritmo general y una que pertenece a la clase std::list que es mucho más óptima que la general.

Actualización:
AK47 me comenta que la función erase ya se encarga de devolver un iterador válido. La función correcta quedaría entonces así:
1 std::list<int>::iterator it = lista.begin();
2 while(it != lista.end()) {
3 if(*it > 0)
4 it = lista.erase(it);
5 else
6 it++;
7 }

2 comentarios:

AK47 dijo...

La función erase devuelve un iterador válido, así que bastaría hacer

i = lista.erase(i);

dentro del if donde se comprueba si es un elemento eliminable o no.

hannibalevivo dijo...

Gracias por el artículo y por el comentario. Me han resultado muy útiles.