c++ - container - Eliminar elementos del conjunto de STL mientras se itera

set string c++

Question

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 al iterar a través de él invalidaría el iterador, y el incremento en el ciclo 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 es esta implementación específica? Estoy usando gcc 4.3.3 en ubuntu 10.04 (versión de 32 bits), por cierto.

¡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 , haciendo que el código sea menos propenso a errores y más legible.

Answer 1

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

Answer 2

Esto depende de la implementación:

Estándar 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 únicamente los iteradores y las referencias a los elementos borrados.

Tal vez podrías probar esto, esto es estándar conforme:

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

Tenga en cuenta que ++ es postfijo, por lo tanto, pasa la posición anterior para borrar, pero primero salta a uno más nuevo debido al operador.

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

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

Answer 3

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 del objetivo, luego establecer el objetivo a 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;                                                               
    }                                                                       
} 

Answer 4

Solo para advertir, que en el caso de un contenedor deque, todas las soluciones que verifiquen la igualdad del iterador deque a numbers.end () probablemente fallarán en gcc 4.8.4. A saber, borrar un elemento del deque generalmente invalida el puntero a numbers.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 deque es correcta en este caso particular, el puntero final ha sido invalidado en el camino. Con el 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)

Esta es 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;
      }
    }
  }
}

Answer 5

Usted no entiende lo que significa "comportamiento indefinido". Comportamiento no definido no significa "si haces esto, tu programa se bloqueará o producirá resultados inesperados". Significa "si haces esto, tu programa podría bloquearse o producir resultados inesperados", o hacer cualquier otra cosa, dependiendo de tu compilador, tu sistema operativo, la fase de la luna, etc.

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

Al borrar un elemento de un conjunto, se invalida el iterador al elemento borrado. El uso de un iterador invalidado es un comportamiento indefinido. Dio la casualidad de que el comportamiento observado era el que pretendías en esta instancia particular; no significa que el código sea correcto.