Eliminar elementos de std :: set mientras itera

147

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.

pedromanoel
fuente
1
Pregunta y respuesta: stackoverflow.com/questions/263945/…
Martin York
3
En realidad, leí esta pregunta (y otras) antes de hacer la mía, pero como estaban relacionadas con otros contenedores STL y dado que mi prueba inicial aparentemente funcionó, pensé que había alguna diferencia entre ellos. Solo después de la respuesta de Matt pensé en usar valgrind. Sin embargo, prefiero mi NUEVA solución sobre las demás porque reduce las posibilidades de errores al incrementar el iterador en un solo lugar. ¡Gracias a todos por la ayuda!
pedromanoel
1
@pedromanoel ++itdebería ser algo más eficiente que it++porque no requiere el uso de una copia temporal invisible del iterador. La versión de Kornel, si bien es más larga, garantiza que los elementos no filtrados se repitan de la manera más eficiente.
Alnitak
@Alnitak No he pensado en eso, pero creo que la diferencia en el rendimiento no sería tan grande. La copia también se crea en su versión, pero solo para los elementos que coinciden. Por lo tanto, el grado de optimización depende totalmente de la estructura del conjunto. Durante bastante tiempo optimicé previamente el código, perjudicando la legibilidad y la velocidad de codificación en el proceso ... Así que realizaría algunas pruebas antes de usarlo de otra manera.
pedromanoel

Respuestas:

178

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;
    }
}
Kornel Kisielewicz
fuente
2
Esto no funciona con deque MSVC2013. O su implementación tiene errores o hay otro requisito que impide que esto funcione deque. La especificación STL es tan compleja que no puede esperar que todas las implementaciones la sigan, y mucho menos que su programador casual la memorice. STL es un monstruo más allá de la domesticación, y dado que no hay una implementación única (y las suites de prueba, si las hay, aparentemente no cubren casos tan obvios como eliminar elementos en un bucle), eso hace que el STL sea un juguete brillante y frágil que puede funcionar con una explosión cuando lo miras de reojo.
kuroi neko
@MatthieuM. Lo hace en C ++ 11. En C ++ 17, toma iterator (const_iterator en C ++ 11) ahora.
tartaruga_casco_mole
19

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;                                                               
    }                                                                       
} 
Mate
fuente
Si lo único que importa es la condición y no requiere la inicialización dentro del alcance o la operación posterior, entonces es mejor usar el whilebucle. es decir, for ( ; it != numbers.end(); )es mejor visible conwhile (it != numbers.end())
iammilind
7

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.

Tyler McHenry
fuente
Oh, soy muy consciente de que el comportamiento indefinido también puede significar "Funciona para mí, pero no para todos". Es por eso que hice esta pregunta, porque no sabía si este comportamiento era correcto o no. Si lo fuera, simplemente me iría así. ¿Usar un ciclo while resolvería mi problema, entonces? Edité mi pregunta con mi solución propuesta. Por favor, míralo.
pedromanoel
A mí también me funciona. Pero cuando cambio la condición a if (n > 2 && n < 7 ), obtengo 0 1 2 4 7 8 9. - El resultado particular aquí probablemente depende más de los detalles de implementación del método de borrado y de los iteradores establecidos, en lugar de la fase de la luna (no ese siempre debe confiar en los detalles de implementación). ;)
UncleBens
1
STL agrega muchos significados nuevos al "comportamiento indefinido". Por ejemplo, "Microsoft pensó que era inteligente mejorar la especificación al permitir std::set::erasedevolver un iterador, por lo que su código MSVC aumentará con una explosión cuando sea compilado por gcc", o "Microsoft realiza comprobaciones vinculadas std::bitset::operator[]para que su algoritmo de bitset cuidadosamente optimizado disminuya a un rastrear cuando se compila con MSVC ". STL no tiene una implementación única y su especificación es un desorden hinchado que crece exponencialmente, por lo que no es de extrañar que la eliminación de elementos desde el interior de un ciclo requiera la experiencia de un programador senior ...
kuroi neko
2

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;
      }
    }
  }
}
McKryak
fuente
La clave de ser do not trust an old remembered dq.end() value, always compare to a new call to dq.end().
Jesse Chisholm
2

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.

Marshall Clow
fuente
1

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.

Vitaly Bogdanov
fuente
1
Set<T>::erasela versión no devuelve el iterador.
Arkaitz Jimenez
44
En realidad lo hace, pero solo en la implementación de MSVC. Así que esta es realmente una respuesta específica de implementación. :)
Eugene
1
@Eugene Lo hace para todas las implementaciones con C ++ 11
mastov
Algunas implementaciones de gcc 4.8with c++1ytienen un error en borrar. it = collection.erase(it);se supone que funciona, pero puede ser más seguro de usarcollection.erase(it++);
Jesse Chisholm
1

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.

John Behm
fuente
0

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();
}
Anurag
fuente
Esto solo funciona si siempre borras todos los elementos. El OP se trata de borrar selectivamente los elementos y seguir teniendo iteradores válidos.
Jesse Chisholm