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

Ce comportement est spécifique à la mise en œuvre. Pour garantir l'exactitude de l'itérateur, vous devez utiliser l'instruction "it = numbers.erase(it) ;" si vous devez supprimer l'élément et simplement incrémenter l'itérateur dans les autres cas.

Answer 2

Je pense que l'utilisation de la méthode STL remove_if pourrait aider à éviter un problème bizarre lors de la tentative de suppression de l'objet enveloppé par l'itérateur.

Cette solution peut être moins efficace.

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

Bullet::Ptr is a shared_pr<Bullet>

' it est l'itérateur que ' remove_if retourne, le troisième argument est une fonction lambda qui est exécutée sur chaque élément du conteneur. Comme le conteneur contient Bullet::Ptr la fonction lambda doit recevoir ce type (ou une référence à ce type) en tant qu'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 où la fonction lambda a retourné vrai et déplace ce contenu au début du conteneur. La fonction ' it ' pointe vers un objet non défini qui peut être considéré comme une poubelle. Les objets allant de 'it' à m_bullets.end() peuvent être effacés, car ils occupent de la mémoire, mais contiennent des déchets, donc la méthode 'erase' est appelée sur cette plage.

Answer 3

Je suis tombé sur le même vieux problème et j'ai trouvé le code ci-dessous plus compréhensible ce qui correspond en quelque sorte aux 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();
}