¿Se pueden eliminar elementos de una lista std::mientras se itera a través de ella?


Tengo un código que se ve así:

for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
    bool isActive = (*i)->update();
    //if (!isActive) 
    //  items.remove(*i); 
    //else
       other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);

Me gustaría eliminar los elementos inactivos inmediatamente después de actualizarlos, para evitar caminar por la lista de nuevo. Pero si añado las líneas comentadas, obtengo un error cuando llego a i++: "Iterador de lista no incrementable". Probé algunos suplentes que no aumentaron en la declaración de for, pero no pude hacer que nada funcionara.

¿Cuál es la mejor manera de eliminar elementos mientras camina una lista std::?

 209
Author: AShelly, 2009-02-27

10 answers

Primero debe incrementar el iterador (con i++) y luego eliminar el elemento anterior (por ejemplo, utilizando el valor devuelto de i++). Puedes cambiar el código a un bucle while de la siguiente manera:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // alternatively, i = items.erase(i);
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}
 245
Author: Michael Kristofik,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-02-27 21:15:23

Quieres hacer:

i= items.erase(i);

Que actualizará correctamente el iterador para que apunte a la ubicación después del iterador que eliminó.

 108
Author: MSN,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-02-27 19:18:02

Necesitas hacer la combinación de la respuesta de Kristo y la de MSN:

// Note: Using the pre-increment operator is preferred for iterators because
//       there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
//       along the way you can safely save end once; otherwise get it at the
//       top of each loop.

std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end  = items.end();

while (iter != items.end())
{
    item * pItem = *iter;

    if (pItem->update() == true)
    {
        other_code_involving(pItem);
        ++iter;
    }
    else
    {
        // BTW, who is deleting pItem, a.k.a. (*iter)?
        iter = items.erase(iter);
    }
}

Por supuesto, lo más eficiente y SuperCool ® STL savy sería algo como esto:

// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
    if (m_needsUpdates == true)
    {
        m_needsUpdates = other_code_involving(this);
    }

    return (m_needsUpdates);
}

// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));
 19
Author: Mike,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-02-27 21:12:11

Utilice el algoritmo std::remove_if.

Editar: Trabajar con colecciones debe ser como: 1. prepara la colección. 2. proceso de recogida.

La vida será más fácil si no mezclas estos pasos.

  1. std:: remove_if. or list:: remove_if (si sabe que trabaja con list y no con TCollection )
  2. std:: for_each
 10
Author: Mykola Golubyev,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-03-01 13:42:34

La alternativa para la versión de bucle a la respuesta de Kristo.

Se pierde algo de eficiencia, se retrocede y luego se avanza de nuevo al eliminar, pero a cambio del incremento del iterador adicional, se puede declarar el iterador en el ámbito del bucle y el código se ve un poco más limpio. Qué elegir depende de las prioridades del momento.

La respuesta estaba totalmente fuera de tiempo, lo sé...

typedef std::list<item*>::iterator item_iterator;

for(item_iterator i = items.begin(); i != items.end(); ++i)
{
    bool isActive = (*i)->update();

    if (!isActive)
    {
        items.erase(i--); 
    }
    else
    {
        other_code_involving(*i);
    }
}
 4
Author: Rafael Gago,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-05 12:57:59

Aquí hay un ejemplo usando un bucle for que itera la lista e incrementa o revalida el iterador en el caso de que un elemento se elimine durante el recorrido de la lista.

for(auto i = items.begin(); i != items.end();)
{
    if(bool isActive = (*i)->update())
    {
        other_code_involving(*i);
        ++i;

    }
    else
    {
        i = items.erase(i);

    }

}

items.remove_if(CheckItemNotActive);
 4
Author: David Cormack,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-04 20:37:39

La eliminación invalida solo los iteradores que apuntan a los elementos que se eliminan.

Así que en este caso después de eliminar *i , i se invalida y no se puede hacer incremento en él.

Lo que puede hacer es primero guardar el iterador del elemento que se va a eliminar , luego incrementar el iterador y luego eliminar el guardado.

 2
Author: anand,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-02-27 19:29:58

Puedes escribir

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive) {
        i = items.erase(i); 
    } else {
        other_code_involving(*i);
        i++;
    }
}

Puede escribir código equivalente con std::list::remove_if, que es menos detallado y más explícito

items.remove_if([] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
});

El std::vector::erase std::remove_if el modismo debe usarse cuando items es un vector en lugar de una lista para mantener la compexidad en O (n), o en caso de que escriba código genérico y items puedan ser un contenedor sin una forma efectiva de borrar elementos individuales (como un vector)

items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
}));
 2
Author: J. Kalz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-26 09:06:31

Si piensa en el std::list como una cola, entonces puede desqueuear y enqueue todos los elementos que desea mantener, pero solo desqueue (y no enqueue) el elemento que desea eliminar. Aquí hay un ejemplo donde quiero eliminar 5 de una lista que contiene los números 1-10...

std::list<int> myList;

int size = myList.size(); // The size needs to be saved to iterate through the whole thing

for (int i = 0; i < size; ++i)
{
    int val = myList.back()
    myList.pop_back() // dequeue
    if (val != 5)
    {
         myList.push_front(val) // enqueue if not 5
    }
}

myList ahora solo tendrá números 1-4 y 6-10.

 2
Author: Alex Bagg,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-12-18 11:22:18

Creo que tienes un error ahí, codifico de esta manera:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
             itAudioChannel != audioChannels.end(); )
{
    CAudioChannel *audioChannel = *itAudioChannel;
    std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
    itAudioChannel++;

    if (audioChannel->destroyMe)
    {
        audioChannels.erase(itCurrentAudioChannel);
        delete audioChannel;
        continue;
    }
    audioChannel->Mix(outBuffer, numSamples);
}
 -4
Author: Marcin Skoczylas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-09-18 16:15:53