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

Question

Je dois parcourir un ensemble et 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 que le fait d'effacer un élément de l'ensemble tout en l'itérant invaliderait l'itérateur, et que l'incrément de la boucle for aurait un comportement indéfini. Pourtant, j'ai exécuté ce code de test et tout s'est bien passé, sans que je puisse expliquer pourquoi.

Ma question : S'agit-il du comportement défini pour les ensembles std ou d'une implémentation spécifique ? Au fait, j'utilise gcc 4.3.3 sur ubuntu 10.04 (version 32 bits).

Gracias.

Solution proposée :

Est-ce une façon 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 à l'intérieur du while, chacune d'entre elles doit incrémenter l'itérateur. J'aime mieux ce code car l'itérateur est incrémenté seulement à un endroit ce qui rend le code moins sujet aux erreurs et plus lisible.

Answer 1

Cela dépend de l'implémentation :

Norme 23.1.2.8 :

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

Peut-être que vous pourriez essayer ceci C'est conforme aux normes :

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

Notez que it++ est postfixe, donc il passe l'ancienne position à effacer, mais saute d'abord à une plus récente grâce à l'opérateur.

Mise à jour 2015.10.27 : C++11 a résolu le défaut. iterator erase (const_iterator position); retourne un itérateur vers l'élément qui suit le dernier élément retiré (ou set::end si le dernier élément a été retiré). Le style C++11 est donc :

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

Answer 2

Si vous exécutez votre programme avec valgrind, vous verrez un tas d'erreurs de lecture. En d'autres termes, oui, les itérateurs sont invalidés, mais vous êtes chanceux dans votre exemple (ou vraiment malchanceux, car vous ne voyez pas les effets négatifs du comportement non défini). Une solution à ce problème est de créer un itérateur temporaire, d'incrémenter le temporaire, de supprimer l'itérateur cible, puis de définir la cible sur le temporaire. 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;                                                               
    }                                                                       
}

Answer 3

Vous comprenez mal ce que signifie "comportement indéfini". Un comportement indéfini ne signifie pas "si vous faites ceci, votre programme sera se planter ou produire des résultats inattendus". Cela signifie "si vous faites ceci, votre programme pourrait planter ou produire des résultats inattendus", ou faire n'importe quoi d'autre, 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, c'est que no la preuve qu'il ne s'agit pas d'un comportement indéfini. Tout ce que cela prouve, c'est que son comportement s'est avéré être celui observé pour cette exécution particulière après avoir été compilé avec ce compilateur particulier sur ce système d'exploitation particulier.

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

Answer 4

Le 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 cppRéférence pour plus d'informations.

Answer 5

Juste pour prévenir, 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 sous gcc 4.8.4. En effet, l'effacement d'un élément de la 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;
    }
  }
}

Sortie :

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

Sortie :

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