Eliminación de elementos del conjunto de STL al iterar

Question

Necesito pasar por un conjunto y eliminar los elementos que cumplen 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 que la iteración a través de él invalidaría el iterador, y el incremento en el bucle for tendría indefinido comportamiento. Aunque, ejecuté este código de prueba y todo salió bien, y no puedo explicar por qué.

Mi pregunta es: ¿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 manera correcta para iterar y borrar elementos de la serie?

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: PREFERENTE SOLUCIÓN

me llegó en torno a una solución que parece más elegante para mí, 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

Esto depende de la implementación:

Standard 23.1.2.8:

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

Tal vez usted podría intentar esto - esto es conforme al standard:

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

Nota que ++ es de sufijo, por lo tanto, pasa a la posición antigua de borrar, pero primero salta a uno nuevo debido a la operador.

2015.10.27 actualización: C++ 11 ha resuelto 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 de C++ 11 es:

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

Answer 2

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 3

No entiende lo que significa "comportamiento indefinido". Comportamiento no definido no significa "si lo hace, su programa se bloqueará o producirá resultados inesperados". Significa "si usted hace esto, su programa podría choque o producir resultados inesperados", o hacer cualquier otra cosa, dependiendo de su compilador, el sistema operativo, la fase de la luna, etc.

Si algo se ejecuta sin se bloquea y se comporta como espera, es no prueba de que no es 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.

Answer 4

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, re-escribir el bucle 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 5

Sólo para advertir, que en caso de un contenedor deque, todas las soluciones que verifican la igualdad iterador deque a numbers.end() fallará probablemente en gcc 4.8.4. A saber, el borrado de un elemento de la deque generalmente invalida 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; 
    } 
    } 
} 

de 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 mientras que la transformación deque es correcta en este caso particular, el puntero final ha sido invalidado en el camino. Con la doble cola de un tamaño diferente que 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í es una de las maneras de solucionar este problema:

#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; 
     } 
    } 
    } 
}