Suppression d'éléments de std :: set lors de l'itération

147

J'ai besoin de parcourir un ensemble et de supprimer les éléments qui répondent à un critère prédéfini.

Voici le code de test que j'ai écrit:

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

Au début, je pensais qu'effacer un élément de l'ensemble lors de son itération invaliderait l'itérateur, et que l'incrémentation à la boucle for aurait un comportement indéfini. Même si, j'ai exécuté ce code de test et tout s'est bien passé, et je ne peux pas expliquer pourquoi.

Ma question: est-ce le comportement défini pour les ensembles std ou cette implémentation est-elle spécifique? J'utilise gcc 4.3.3 sur ubuntu 10.04 (version 32 bits), d'ailleurs.

Merci!

Solution proposée:

Est-ce une manière correcte d'itérer et d'effacer des éléments de l'ensemble?

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

Edit: SOLUTION PRÉFÉRÉE

J'ai trouvé une solution qui me semble plus élégante, même si elle fait exactement la même chose.

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

S'il y a plusieurs conditions de test dans le while, chacune d'elles doit incrémenter l'itérateur. J'aime mieux ce code car l'itérateur n'est incrémenté qu'à un seul endroit , ce qui rend le code moins sujet aux erreurs et plus lisible.

pedromanoel
la source
1
Demandé et répondu: stackoverflow.com/questions/263945/…
Martin York
3
En fait, j'ai lu cette question (et d'autres) avant de poser la mienne, mais comme ils étaient liés à d'autres conteneurs STL et que mon test initial fonctionnait apparemment, je pensais qu'il y avait une différence entre eux. Ce n'est qu'après la réponse de Matt que j'ai pensé à utiliser valgrind. Même si, je préfère ma NOUVELLE solution aux autres car elle réduit les risques d'erreurs en incrémentant l'itérateur à un seul endroit. Merci à tous pour l'aide!
pedromanoel
1
@pedromanoel ++itdevrait être un peu plus efficace que it++parce qu'il ne nécessite pas l'utilisation d'une copie temporaire invisible de l'itérateur. La version Kornel, bien que plus longue, garantit que les éléments non filtrés sont itérés plus efficacement.
Alnitak
@Alnitak Je n'y ai pas pensé, mais je pense que la différence de performance ne serait pas si grande. La copie est également créée dans sa version, mais uniquement pour les éléments qui correspondent. Le degré d'optimisation dépend donc totalement de la structure de l'ensemble. Pendant un certain temps, j'ai pré-optimisé le code, ce qui a nui à la lisibilité et à la vitesse de codage dans le processus ... Je ferais donc quelques tests avant d'utiliser l'autre manière.
pedromanoel

Réponses:

178

Cela dépend de la mise en œuvre:

Norme 23.1.2.8:

Les éléments d'insertion n'affectent pas la validité des itérateurs et des références au conteneur, et les membres d'effacement n'invalideront que les itérateurs et les références aux éléments effacés.

Peut-être pourriez-vous essayer ceci - c'est conforme à la norme:

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

Notez qu'il ++ est postfix, donc il passe l'ancienne position à effacer, mais saute d'abord à une plus récente en raison de l'opérateur.

Mise à jour du 27 octobre 2015: C ++ 11 a résolu le problème. iterator erase (const_iterator position);renvoie un itérateur à l'élément qui suit le dernier élément supprimé (ou set::end, si le dernier élément a été supprimé). Le style C ++ 11 est donc:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}
Kornel Kisielewicz
la source
2
Cela ne fonctionne pas avec deque MSVC2013. Soit leur implémentation est boguée, soit il y a encore une autre exigence qui empêche cela de fonctionner deque. La spécification STL est si compliquée que vous ne pouvez pas vous attendre à ce que toutes les implémentations la suivent, sans parler de votre programmeur occasionnel pour la mémoriser. STL est un monstre au-delà de l'apprivoisement, et comme il n'y a pas d'implémentation unique (et les suites de tests, le cas échéant, ne couvrent apparemment pas des cas aussi évidents que la suppression d'éléments dans une boucle), cela fait de la STL un jouet fragile et brillant qui peut aller avec un coup quand vous le regardez de côté.
kuroi neko le
@MatthieuM. C'est le cas en C ++ 11. En C ++ 17, il prend maintenant un itérateur (const_iterator en C ++ 11).
tartaruga_casco_mole
19

Si vous exécutez votre programme via valgrind, vous verrez un tas d'erreurs de lecture. En d'autres termes, oui, les itérateurs sont en cours d'invalidation, mais vous avez de la chance dans votre exemple (ou vraiment pas de chance, car vous ne voyez pas les effets négatifs d'un comportement indéfini). Une solution à cela consiste à créer un itérateur temporaire, incrémenter la température, supprimer l'itérateur cible, puis définir la cible sur la température. Par exemple, réécrivez votre boucle comme suit:

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;                                                               
    }                                                                       
} 
Mat
la source
Si ce n'est que la condition qui compte et qui ne nécessite pas d'initialisation ou de post-opération dans la portée, il vaut mieux utiliser whileloop. ie for ( ; it != numbers.end(); )est mieux visible avecwhile (it != numbers.end())
iammilind
7

Vous ne comprenez pas ce que signifie «comportement indéfini». Un comportement non défini ne signifie pas « si vous faites cela, votre programme va planter ou produire des résultats inattendus. » Cela signifie "si vous faites cela, votre programme pourrait planter ou produire des résultats inattendus", ou faire autre chose, selon votre compilateur, votre système d'exploitation, la phase de la lune, etc.

Si quelque chose s'exécute sans planter et se comporte comme vous l'attendez, ce n'est pas la preuve qu'il ne s'agit pas d'un comportement indéfini. Tout ce qu'il prouve, c'est que son comportement s'est avéré être celui observé pour cette exécution particulière après la compilation avec ce compilateur particulier sur ce système d'exploitation particulier.

L'effacement d'un élément d'un ensemble invalide l'itérateur vers l'élément effacé. L'utilisation d'un itérateur invalidé est un comportement indéfini. Il se trouve que le comportement observé était ce que vous vouliez dans ce cas particulier; cela ne signifie pas que le code est correct.

Tyler McHenry
la source
Oh, je suis bien conscient qu'un comportement indéfini peut aussi signifier "ça marche pour moi, mais pas pour tout le monde". C'est pourquoi j'ai posé cette question, car je ne savais pas si ce comportement était correct ou non. Si c'était le cas, je partirais comme ça. L'utilisation d'une boucle while résoudrait mon problème, alors? J'ai édité ma question avec ma solution proposée. Vérifie s'il te plaît.
pedromanoel
Ça marche pour moi aussi. Mais quand je change la condition en if (n > 2 && n < 7 )alors j'obtiens 0 1 2 4 7 8 9. - Le résultat particulier ici dépend probablement plus des détails de mise en œuvre de la méthode d'effacement et des itérateurs définis, plutôt que de la phase de la lune (pas celle-là devrait jamais se fier aux détails de mise en œuvre). ;)
UncleBens
1
STL ajoute beaucoup de nouvelles significations au «comportement indéfini». Par exemple, "Microsoft a pensé qu'il était judicieux d'améliorer la spécification en permettant std::set::erasede renvoyer un itérateur, de sorte que votre code std::bitset::operator[]MSVC montera en flèche une fois compilé par gcc", ou "Microsoft effectue des vérifications liées afin que votre algorithme de jeu de bits soigneusement optimisé ralentisse à un crawler une fois compilé avec MSVC ". STL n'a pas d'implémentation unique et sa spécification est un désordre gonflé à croissance exponentielle, il n'est donc pas étonnant que la suppression d'éléments de l'intérieur d'une boucle nécessite une expertise de programmeur senior ...
kuroi neko
2

Juste pour avertir que dans le cas d'un conteneur deque, toutes les solutions qui vérifient l'égalité de l'itérateur deque avec numbers.end () échoueront probablement sur gcc 4.8.4. À savoir, l'effacement d'un élément du deque invalide généralement le pointeur vers 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;
    }
  }
}

Production:

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

Notez que si la transformation deque est correcte dans ce cas particulier, le pointeur de fin a été invalidé en cours de route. Avec le deque d'une taille différente, l'erreur est plus apparente:

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

Production:

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)

Voici l'une des façons de résoudre ce problème:

#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
la source
La clé étant do not trust an old remembered dq.end() value, always compare to a new call to dq.end().
Jesse Chisholm
2

C ++ 20 aura un "effacement uniforme des conteneurs", et vous pourrez écrire:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

Et cela fonctionnera pour vector, set, deque, etc. Voir cppReference pour plus d' informations.

Marshall Clow
la source
1

Ce comportement est spécifique à l'implémentation. Pour garantir l'exactitude de l'itérateur, vous devez utiliser "it = numbers.erase (it);" instruction si vous avez besoin de supprimer l'élément et simplement de l'itérateur dans les autres cas.

Vitaly Bogdanov
la source
1
Set<T>::erasela version ne renvoie pas d'itérateur.
Arkaitz Jimenez
4
En fait, c'est le cas, mais uniquement sur l'implémentation MSVC. C'est donc vraiment une réponse spécifique à la mise en œuvre. :)
Eugene
1
@Eugene Il le fait pour toutes les implémentations avec C ++ 11
mastov
Certaines implémentations de gcc 4.8with c++1yont un bogue dans l'effacement. it = collection.erase(it);est censé fonctionner, mais il peut être plus sûr à utilisercollection.erase(it++);
Jesse Chisholm
1

Je pense en utilisant la méthode STL 'remove_if ' de pourrait aider à éviter un problème étrange lorsque vous essayez de supprimer l'objet qui est enveloppé par l'itérateur.

Cette solution peut être moins efficace.

Disons que nous avons une sorte de conteneur, comme vector ou une liste appelée m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

« it» est l'itérateur que « remove_if» renvoie, le troisième argument est une fonction lambda qui est exécutée sur chaque élément du conteneur. Étant donné que le conteneur contient Bullet::Ptr, la fonction lambda doit obtenir ce type (ou une référence à ce type) passé en argument.

 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' supprime le conteneur dans lequel la fonction lambda a renvoyé true et déplace ce contenu au début du conteneur. Le ' it' pointe vers un objet indéfini qui peut être considéré comme une poubelle. Les objets de «it» à m_bullets.end () peuvent être effacés, car ils occupent de la mémoire, mais contiennent des déchets, ainsi la méthode «effacer» est appelée sur cette plage.

John Behm
la source
0

Je suis tombé sur le même vieux problème et j'ai trouvé le code ci-dessous plus compréhensible, ce qui est en quelque sorte les solutions ci-dessus.

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
la source
Cela ne fonctionne que si vous effacez toujours chaque élément. L'OP consiste à effacer sélectivement les éléments tout en conservant des itérateurs valides.
Jesse Chisholm