Itération et suppression simultanées sur vector

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:

---

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

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)

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/

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é.

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)

Bonjour,

Citation:

---

Envoyé par Nogane

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 :

Citation:

---

Envoyé par erase

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

Salut

Citation:

---

Envoyé par Arzar

Bonjour,


Pas tout à fait, la norme dit :

Citation:

---

Envoyé par erase

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,

Citation:

---

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:

---

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:

---

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

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"

Citation:

---

Envoyé par 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"

---

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 :D

Bonjour,
et un truc du style :

Code:

---

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+

le probleme etait que selon la valeur de l'iterateur courant on pouvait decider de supprimer un autre element, ce qui pouvait invalider l'iterateur courant sans prevenir

Et comme ceci?....

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

it = myvector.begin( ); while( it != myvector.end( ) ) { if(suppression) { supprimer_dautres_iterateurs( it/*en param si on en a besoin*/ ); it = myvector.begin( ); // On recommence au début... } else { ++it; // Pas de suppression, on continue... } }

---

Ici je recommence au début à chaque suppression. Si on souhaite effectuer
une seule passe en éliminant 1 ou n itérateurs sur cette seule passe,
là çà se complique!...la fonction "supprimer_dautres_iterateurs" doit
retourner le prochain iterateur valide après son travail :

Code:

---

1 2 3 4 5

if(suppression) { it = supprimer_dautres_iterateurs( it ); }

---

Salut tout le monde,

Voici mon premier post j'espère qu'il sera utile a tous.

std::vector fait parti de la STL et donc réagis pareil sur toutes les archi :D

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

std::vector<Type> v; std::vector<Type>::iterator it;   it = v.begin(); while (it != v.end()) { if (suppression) { it = v.erase(it); } else it++; }

---

voila l'iterator de retour de la method erase et l'ement suivant la suppression.
j'espère que sa peut vous etre utile bonne journee et bonne annee a tous :)

désole si il manque quelque accent la magie du qwerty :D