Eliminar elementos de std :: set mientras itera

Necesito revisar un conjunto y eliminar elementos que cumplan con un criterio predefinido.

Este es el código de prueba que escribí:

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

Al principio, pensé que borrar un elemento del conjunto mientras lo iteraba invalidaría el iterador, y el incremento en el bucle for tendría un comportamiento indefinido. Aunque ejecuté este código de prueba y todo salió bien, y no puedo explicar por qué.

Mi pregunta: ¿Es este el comportamiento definido para los conjuntos estándar o esta implementación es específica? Por cierto, estoy usando gcc 4.3.3 en ubuntu 10.04 (versión de 32 bits).

¡Gracias!

Solución propuesta:

¿Es esta una forma correcta de iterar y borrar elementos del conjunto?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

Editar: SOLUCIÓN PREFERIDA

Encontré una solución que me parece más elegante, a pesar de que hace exactamente lo mismo.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

Si hay varias condiciones de prueba dentro del tiempo, cada una de ellas debe incrementar el iterador. Me gusta más este código porque el iterador se incrementa solo en un lugar , lo que hace que el código sea menos propenso a errores y más legible.

Esto depende de la implementación:

Norma 23.1.2.8:

Los miembros de inserción no afectarán la validez de los iteradores y las referencias al contenedor, y los miembros de borrado invalidarán solo los iteradores y las referencias a los elementos borrados.

Tal vez podría intentar esto, esto es conforme estándar:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Tenga en cuenta que ++ es postfix, por lo tanto, pasa la posición anterior para borrar, pero primero salta a una nueva debido al operador.

Actualización 2015.10.27: C ++ 11 ha resuelto el defecto. iterator erase (const_iterator position);devolver un iterador al elemento que sigue al último elemento eliminado (o set::end, si se eliminó el último elemento). Entonces el estilo C ++ 11 es:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

Si ejecuta su programa a través de valgrind, verá un montón de errores de lectura. En otras palabras, sí, los iteradores están siendo invalidados, pero tienes suerte en tu ejemplo (o realmente desafortunado, ya que no estás viendo los efectos negativos del comportamiento indefinido). Una solución para esto es crear un iterador temporal, incrementar la temperatura, eliminar el iterador de destino y luego establecer el objetivo en la temperatura. Por ejemplo, vuelva a escribir su ciclo de la siguiente manera:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 

Usted no comprende lo que significa "comportamiento indefinido". El comportamiento indefinido no significa "si hace esto, su programa se bloqueará o producirá resultados inesperados". Significa "si hace esto, su programa podría fallar o producir resultados inesperados", o hacer cualquier otra cosa, dependiendo de su compilador, su sistema operativo, la fase de la luna, etc.

Si algo se ejecuta sin fallar y se comporta como espera, no es prueba de que no sea un comportamiento indefinido. Todo lo que demuestra es que su comportamiento resultó ser el observado para esa ejecución en particular después de compilar con ese compilador en particular en ese sistema operativo en particular.

Borrar un elemento de un conjunto invalida el iterador al elemento borrado. Usar un iterador invalidado es un comportamiento indefinido. Dio la casualidad de que el comportamiento observado era el que pretendía en este caso particular; no significa que el código sea correcto.

Solo para advertir que en el caso de un contenedor de deque, todas las soluciones que verifiquen la igualdad del iterador de deque a números.end () probablemente fallarán en gcc 4.8.4. Es decir, borrar un elemento de la deque generalmente invalida el puntero a números.end ():

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Salida:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

Tenga en cuenta que si bien la transformación de deque es correcta en este caso particular, el puntero final se ha invalidado en el camino. Con la deque de un tamaño diferente, el error es más evidente:

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Salida:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Aquí está una de las formas de solucionar esto:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}

C ++ 20 tendrá un "borrado uniforme del contenedor" y podrá escribir:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

Y que va a trabajar para vector, set, deque, etc. Ver cppReference para obtener más información.

Este comportamiento es específico de la implementación. Para garantizar la exactitud del iterador, debe usar "it = numbers.erase (it);" declaración si necesita eliminar el elemento y simplemente iterar el iterador en otro caso.

Creo que usar el método STL ' remove_if' podría ayudar a prevenir algún problema extraño cuando intente eliminar el objeto envuelto por el iterador.

Esta solución puede ser menos eficiente.

Digamos que tenemos algún tipo de contenedor, como vector o una lista llamada m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

' it' es el iterador que ' remove_if' devuelve, el tercer argumento es una función lambda que se ejecuta en cada elemento del contenedor. Debido a que el contenedor contiene Bullet::Ptr, la función lambda necesita que ese tipo (o una referencia a ese tipo) pase como argumento.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

' remove_if' elimina el contenedor donde la función lambda devolvió verdadero y desplaza ese contenido al comienzo del contenedor. El ' it' apunta a un objeto indefinido que puede considerarse basura. Los objetos de 'it' a m_bullets.end () se pueden borrar, ya que ocupan memoria, pero contienen basura, por lo que se llama al método 'borrar' en ese rango.

Me encontré con el mismo problema anterior y encontré el siguiente código más comprensible, lo que es en cierta forma según las soluciones anteriores.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}