Discussion :

[tnarol]

Salut,

Je travaille sur un vector d'objets. J'ai besoin de parcourir les objets dans l'ordre, mais au cours du parcours je peux me rendre compte que certains doivent être supprimés.

J'ai déjà l'habitude de faire ça facilement lorsque l'objet à supprimer est celui sur lequel est l'itérateur courant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
for (iter = monVecteur.begin; iter != monVecteur.end(); /* Rien */)
{
   if (suppression) { iter = monVecteur.erase(iter);}
   else { iter++; }
}

Mais ici je coince car il est possible que ce soient aussi des objets situés avant ou après l'itérateur courant. Je suppose que si j'efface violemment un bout du vecteur sur lequel je boucle ça risque de mal se passer. Quelles solutions voyez-vous ?

Merci

[r0d]

bonjour,

il est toujours délicat de supprimer des éléments d'un vecteur "en vol", à cause de la contrainte de contiguïté des éléments d'un vecteur. A vue de nez (sans le contexte), il me semblerait mieux d'utiliser une liste plutôt qu'un vecteur, ou alors d'avoir un 2eme vecteur que l'on remplirait au fur et à mesure de l'algo.
Ou alors, faire en sorte que les objets de ton vecteurs puissent être marqués (un booleen mustErase par exemple), et puis faire le ménage ensuite (qui se fera ainsi très facilement et très rapidement - en terme d'exécution - en commençant pas trier le vecteur en fonction de ce booleen, puis en "coupant" le vecteur)

[Nogane]

Bonjour,

En effet cette méthode ne marchera pas sur un vector, car tout les iterateur sont invalidé lors de la suppression.

En plus des solutions de r0d, on peut aussi utiliser std::remove_if:
http://www.cplusplus.com/reference/algorithm/remove_if/

[3DArchi]

Salut,
Une solution pour supprimer un élément du vecteur sans trop perturber l'iterateur est de swapper l'élément que tu veux supprimer avec le dernier suivi d'un resize (qui n'invalide que les itérateurs après la nouvelle taille).
Cela suppose que ton vecteur n'a pas besoin d'être trié.

[screetch]

battu par 3D archi. mais j'avais la même solution. c'est aussi beaucoup plus efficace de supprimer un élément comme ca (pas besoin de copier la queue plusieurs fois)

[Arzar]

Bonjour,

En effet cette méthode ne marchera pas sur un vector, car tout les iterateur sont invalidé lors de la suppression.

Pas tout à fait, la norme dit :

Effects: Invalidates iterators and references at or after the point of the erase.

Donc on peut supprimer sans danger des éléments situés au delà de l'élement courant, mais pas avant.

Le plus simple reste probablement la méthode de rod : une première passe pour marquer les éléments à supprimer suivi d'un erase + remove_if

[koala01]

Salut

Bonjour,


Pas tout à fait, la norme dit :

Effects: Invalidates iterators and references at or after the point of the erase.

Donc on peut supprimer sans danger des éléments situés au delà de l'élement courant, mais pas avant.

Le plus simple reste probablement la méthode de rod : une première passe pour marquer les éléments à supprimer suivi d'un erase + remove_if

Le problème vient bien du fait que l'on ne peut supprimer "sereinement" (comprend: sans trop se poser de question ni risquer une catastrophe) qu'un itérateur qui se trouve après l'itérateur courent, sous peine que l'itérateur courent soit invalidé:

Soit un itérateur (somme toute classique):
std::vector<UnType>::iterator iter;

La norme précise, en reprenant tes termes,

Invalidates iterators and references at or after the point of the erase.

ce qui comprend... l'itérateur courent

Ainsi, iter est devenu invalide après un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
myvector.erase(iter);
//iter est invalide ici

Les solutions proposées par 3DArchi et par r0d sont donc bel et bien celles qui posent le moins de problème, car, si tu souhaite effectivement supprimer directement un élément dont tu viens de déterminer qu'il doit l'être, tu en serait réduit à un code proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for(std::vector<type>::iterator it=myvector.begin(); it!=myvector.end();++it)
{
    if(suppression)
    {
        /* cas particulier: l'itérateur à supprimer est le premier élément */
        if(it==myvector.begin())
        {
             myvector.erase(it); 
             /* it est invalidé, il faut donc le redéfinir... 
              * comme le début du vecteur
              */
             it=myvector.begin();
        }
        else
        {
            /* il faut garder une trace de l'itérateur qui se trouve avant
             * l'itérateur à supprimer
             */
            std::vector<unType>::iterator temp=it;
            --temp;
            /* supprimer l'itérateur qui doit l'être */
            myvector.erase(it);
            /*et redéfinir celui qui précède comme itérateur courent*/
            it=temp;
            /* on laisse ici l'incrémentation à la boucle :D */
        }
    }
}

Et je ne suis même pas tout à fait sur que le code soit correct (non testé )

[screetch]

le code n'est pas entierement correct car si tu elimines un élément et souhaite retourner au début, l'itérateur sera quand meme incrémenté
mettons que tu souhaites supprimer les éléments (initialement) 1 et 2
alors la premiere passe va supprimer l'element 1
la tete devient donc 2, la boucle recommence a partir de 2
mais la boucle for incrémente quand meme l'itérateur, qui passe sur 3
et ainsi 2 n'a jamais été testé

mais c'est un detail d'implémentation, la philosophie restant "il faut recommencer au début"

[koala01]

le code n'est pas entierement correct car si tu elimines un élément et souhaite retourner au début, l'itérateur sera quand meme incrémenté
mettons que tu souhaites supprimer les éléments (initialement) 1 et 2
alors la premiere passe va supprimer l'element 1
la tete devient donc 2, la boucle recommence a partir de 2
mais la boucle for incrémente quand meme l'itérateur, qui passe sur 3
et ainsi 2 n'a jamais été testé

mais c'est un detail d'implémentation, la philosophie restant "il faut recommencer au début"

Effectivement, il faudrait, pour qu'il soit tout à fait juste "sortir" l'incrémentation de l'itérateur de la définition de la boucle et ne la mettre que dans le "else" du code...

Finalement cela illustre tout à fait le message que l'on essaye de faire passer: cette méthode nécessite réellement une réflexion approfondie et s'intéressant au moindre détail, la moindre distraction pouvant être fatale

Je viens donc de donner par l'absurde la preuve que les meilleures solutions envisageables sont bel et bien celles de 3DArchi et de rûd

[ads59]

Bonjour,
et un truc du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
it = myvector.begin( );
while( it != myvector.end( ) )
{
    if(suppression)
    {
       myvector.erase( it );
       it = myvector.begin( ); // On recommence au début...
    }
    else
    {
        ++it; // Pas de suppression, on continue...
    }
}

A+