Pouvez-vous supprimer des éléments d'une liste std :: tout en parcourant celle-ci?

239

J'ai un code qui ressemble à ceci:

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);

Je souhaite supprimer les éléments inactifs immédiatement après leur mise à jour, afin d'éviter de parcourir à nouveau la liste. Mais si j'ajoute les lignes commentées, j'obtiens une erreur lorsque j'arrive à i++: "L'itérateur de liste n'est pas incrémentable". J'ai essayé des suppléants qui n'ont pas augmenté dans l'instruction for, mais je n'ai rien pu faire.

Quelle est la meilleure façon de supprimer des éléments lorsque vous parcourez une liste std ::?

AShelly
la source
Je n'ai vu aucune solution basée sur l'itération en arrière. J'en ai posté un .
sancho.s ReinstateMonicaCellio

Réponses:

286

Vous devez d'abord incrémenter l'itérateur (avec i ++) puis supprimer l'élément précédent (par exemple, en utilisant la valeur renvoyée par i ++). Vous pouvez changer le code en une boucle while comme ceci:

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;
    }
}
Michael Kristofik
la source
7
En fait, ce n'est pas garanti de fonctionner. Avec "erase (i ++);", nous savons seulement que la valeur pré-incrémentée est passée à erase (), et le i est incrémenté avant le point-virgule, pas nécessairement avant l'appel à erase (). "itérateur prev = i ++; erase (prev);" est sûr de fonctionner, tout comme utiliser la valeur de retour
James Curran
58
Non James, i est incrémenté avant d'appeler erase et la valeur précédente est passée à la fonction. Les arguments d'une fonction doivent être entièrement évalués avant d'appeler la fonction.
Brian Neal
28
@ James Curran: Ce n'est pas correct. TOUS les arguments sont entièrement évalués avant d'appeler une fonction.
Martin York
9
Martin York a raison. Tous les arguments d'un appel de fonction sont entièrement évalués avant l'appel d'une fonction, sans exception. C'est simplement ainsi que fonctionne la fonction. Et cela n'a rien à voir avec votre exemple foo.b (i ++) .c (i ++) (qui n'est en aucun cas défini)
jalf
75
L'utilisation alternative i = items.erase(i)est plus sûre, car elle est équivalente à une liste, mais fonctionnera toujours si quelqu'un change le conteneur en vecteur. Avec un vecteur, erase () déplace tout vers la gauche pour remplir le trou. Si vous essayez de supprimer le dernier élément avec du code qui incrémente l'itérateur après l'effacement, la fin se déplace vers la gauche et l'itérateur se déplace vers la droite - après la fin. Et puis vous vous plantez.
Eric Seppanen
133

Vous voulez faire:

i= items.erase(i);

Cela mettra correctement à jour l'itérateur pour pointer vers l'emplacement après l'itérateur que vous avez supprimé.

MSN
la source
80
Soyez averti que vous ne pouvez pas simplement déposer ce code dans votre boucle for. Sinon, vous sauterez un élément chaque fois que vous en supprimez un.
Michael Kristofik
2
ne peut-il pas faire i--; à chaque fois en suivant son morceau de code pour éviter de sauter?
enthousiastegeek
1
@enthusiasticgeek, que se passe-t-il si i==items.begin()?
MSN
1
@enthusiasticgeek, à ce stade, vous devriez simplement le faire i= items.erase(i);. C'est la forme canonique et s'occupe déjà de tous ces détails.
MSN
6
Michael fait remarquer un énorme «piège», j'ai dû faire face à la même chose tout à l'heure. La méthode la plus simple pour l'éviter que j'ai trouvée consistait simplement à décomposer la boucle for () en un certain temps () et à faire attention à l'incrémentation
Anne Quinn
22

Vous devez faire la combinaison de la réponse de Kristo et 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 != 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);
    }
}

Bien sûr, la chose la plus efficace et la plus efficace de SuperCool® STL serait quelque chose comme ceci:

// 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)));
Mike
la source
J'ai pris en compte votre méthode SuperCool, mon hésitation était que l'appel à remove_if ne précise pas que l'objectif est de traiter les éléments, plutôt que de les supprimer de la liste des actifs. (Les éléments ne sont pas supprimés car ils deviennent seulement inactifs, pas inutiles)
AShelly
Je suppose que tu as raison. D'une part, je suis enclin à suggérer de changer le nom de `` mise à jour '' pour supprimer l'obscurité, mais la vérité est que ce code est fantaisiste avec les foncteurs, mais il est également tout sauf non obscur.
Mike
Bon commentaire, corrigez la boucle while pour utiliser end ou supprimez la définition inutilisée.
Mike
10

Utilisez l'algorithme std :: remove_if.

Edit: Le travail avec les collections devrait ressembler à: 1. préparer la collection. 2. collecte de processus.

La vie sera plus facile si vous ne mélangez pas ces étapes.

  1. std :: remove_if. ou list :: remove_if (si vous savez que vous travaillez avec list et non avec TCollection)
  2. std :: for_each
Mykola Golubyev
la source
2
std :: list a une fonction membre remove_if qui est plus efficace que l'algorithme remove_if (et ne nécessite pas l'idiome "remove-erase").
Brian Neal
5

Voici un exemple utilisant une forboucle qui itère la liste et incrémente ou revalide l'itérateur en cas de suppression d'un élément pendant la traversée de la liste.

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);
David Cormack
la source
4

L'alternative pour la version en boucle à la réponse de Kristo.

Vous perdez de l'efficacité, vous revenez en arrière puis recommencez lors de la suppression, mais en échange de l'incrément d'itérateur supplémentaire, vous pouvez faire déclarer l'itérateur dans la portée de la boucle et le code un peu plus propre. Que choisir dépend des priorités du moment.

La réponse était totalement hors du temps, je sais ...

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);
    }
}
Rafael Gago
la source
1
C'est aussi ce que j'ai utilisé. Mais je ne sais pas s'il est garanti que cela fonctionne si l'élément à supprimer est le premier élément du conteneur. Pour moi, cela fonctionne, je pense, mais je ne sais pas si c'est portable sur toutes les plateformes.
trololo
Je n'ai pas fait "-1", cependant, l'itérateur de liste ne peut pas décrémenter? Au moins, j'ai une affirmation de Visual Studio 2008.
milesma
Tant que la liste chaînée est implémentée comme une liste circulaire double chaînée ayant un nœud head / stub (utilisé comme end () rbegin () et lorsqu'elle est vide utilisée comme begin () et rend () aussi) cela fonctionnera. Je ne me souviens pas sur quelle plate-forme j'utilisais cela, mais cela fonctionnait aussi pour moi, car l'implémentation nommée ci-dessus est l'implémentation la plus courante pour une std :: list. Mais de toute façon, il est presque sûr que cela exploitait un comportement non défini (par la norme C ++), il vaut donc mieux ne pas l'utiliser.
Rafael Gago
re: iterator cannot be decrementedLa eraseméthode a besoin d'un random access iterator. Certaines implémentations de collection fournissent un forward only iteratorqui provoque l'assertion.
Jesse Chisholm
@Jesse Chisholm, la question portait sur une liste std ::, pas sur un conteneur arbitraire. std :: list fournit des itérateurs d'effacement et bidirectionnels.
Rafael Gago
4

Je l'ai résumé, voici les trois méthodes avec exemple:

1. en utilisant la whileboucle

list<int> lst{4, 1, 2, 3, 5};

auto it = lst.begin();
while (it != lst.end()){
    if((*it % 2) == 1){
        it = lst.erase(it);// erase and go to next
    } else{
        ++it;  // go to next
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

2. en utilisant la fonction remove_ifmembre dans la liste:

list<int> lst{4, 1, 2, 3, 5};

lst.remove_if([](int a){return a % 2 == 1;});

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

3. en utilisant la fonction std::remove_ifcombinée avec la erasefonction membre:

list<int> lst{4, 1, 2, 3, 5};

lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
    return a % 2 == 1;
}), lst.end());

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

4. en utilisant la forboucle, notez la mise à jour de l'itérateur:

list<int> lst{4, 1, 2, 3, 5};

for(auto it = lst.begin(); it != lst.end();++it){
    if ((*it % 2) == 1){
        it = lst.erase(it);  erase and go to next(erase will return the next iterator)
        --it;  // as it will be add again in for, so we go back one step
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2 
Jayhello
la source
2

La suppression invalide uniquement les itérateurs qui pointent vers les éléments qui sont supprimés.

Donc, dans ce cas, après avoir supprimé * i, i est invalidé et vous ne pouvez pas l'incrémenter.

Ce que vous pouvez faire, c'est d'abord enregistrer l'itérateur de l'élément à supprimer, puis incrémenter l'itérateur, puis supprimer celui enregistré.

anand
la source
2
L'utilisation de post-incrémentation est beaucoup plus élégante.
Brian Neal
2

Si vous pensez std::listà une file d'attente, vous pouvez retirer et mettre en file d'attente tous les éléments que vous souhaitez conserver, mais uniquement retirer (et non mettre en file d'attente) l'élément que vous souhaitez supprimer. Voici un exemple où je veux supprimer 5 d'une liste contenant les numéros 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 aura désormais uniquement les numéros 1-4 et 6-10.

Alex Bagg
la source
Approche intéressante mais je crains que cela ne soit lent.
sg7
2

L'itération vers l'arrière évite d'effacer un élément sur les autres éléments à parcourir:

typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
    --it;
    bool remove = <determine whether to remove>
    if ( remove ) {
        items.erase( it );
    }
}

PS: voyez ceci , par exemple, concernant l'itération en arrière.

PS2: Je n'ai pas testé à fond s'il gère bien les éléments effaçables aux extrémités.

sancho.s ReinstateMonicaCellio
la source
re: avoids the effect of erasing an element on the remaining elementspour une liste, probablement oui. Pour un vecteur peut-être pas. Ce n'est pas quelque chose de garanti sur les collections arbitraires. Par exemple, une carte peut décider de se rééquilibrer.
Jesse Chisholm
1

Tu peux écrire

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

Vous pouvez écrire du code équivalent avec std::list::remove_if, qui est moins détaillé et plus explicite

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

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

le std::vector::erase std::remove_if idiome doit être utilisé lorsque les éléments sont un vecteur au lieu d'une liste pour conserver la compexité à O (n) - ou si vous écrivez du code générique et que les éléments peuvent être un conteneur sans moyen efficace d'effacer des éléments uniques (comme un vecteur)

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;
}));
J. Kalz
la source
-4

Je pense que vous avez un bug, je code de cette façon:

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);
}
Marcin Skoczylas
la source
Je suppose que cela a été rétrogradé pour les préférences de style, car il semble être fonctionnel. Oui bien sûr, (1) il utilise un itérateur supplémentaire, (2) l'incrément d'itérateur est à un endroit étrange pour une boucle sans bonne raison de le mettre là, (3) il fait le travail de canal après la décision de supprimer à la place d'avant comme dans l'OP. Mais ce n'est pas une mauvaise réponse.
Jesse Chisholm