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

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.

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

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

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.

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

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.

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.

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.

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