std::map: erase dans une boucle

Bonjour;

J'ai ce code source qui permet de supprimer un élement dans une map:

Code:

---

1 2 3 4 5 6 7 8 9

for(std::map<int, int>::iterator it = m.begin(); it!=m.end(); ) { if(it->first==1 || it->first==2) { m.erase(it++); }else{ it++; } }

---

Je n'arrive pas à comprendre pourquoi le code source suivant ne fonctionne pas et est différent du premier:

Code:

---

1 2 3 4 5 6 7 8 9 10

for(std::map<int, int>::iterator it = m.begin(); it!=m.end(); ) { if(it->first==1 || it->first==2) { m.erase(it); it++; }else{ it++; } }

---

Dans les deux cas, l'iterateur est incrémenté (++) après l'appel à erase, non ?

Merci d'avance.

Salut,

Le fait est que, dans le premier code, tu incrémente d'abord ton itérateur (donc, tu passes d'abord à l'élément suivant), et puis seulement, tu supprimes l'élément.

C'est à dire que si la clé vaut 1 ou que si la clé vaut 2, tu prends la clé suivante (2,3 ou... ce qui suit la clé sur laquelle tu te trouves, de manière générale)

Dans le second exemple, tu supprimes d'abord l'élément que tu as trouvé (celui dont la clé vaut 1 ou 2) et puis seulement tu passes à l'élément suivant.

En fait ton premier code est plutôt équivalent à

Code:

---

1 2 3 4 5 6 7 8 9 10

for(std::map<int, int>::iterator it = m.begin(); it!=m.end(); ) { if(it->first==1 || it->first==2) { it++; m.erase(it); }else{ it++; } }

---

Bonjour,

je miserais plutôt sur un coup de bol pour que le premier code ne crash pas non plus.

"par hasard" (ou pas ?) ton m.erase(it++); équivaudrait donc à it = m.erase(it);, qui est la bonne façon de supprimer un itérateur pendant son parcours.
Toutes les méthodes de type erase sur itérateur retourne l'itérateur suivant. cf la doc.

@Koala, ton code crashera à la boucle suivante, tu incrémentes it, le supprimes, puis... tu repasses par ->first qui est indéterminé. :aie:

Cela dit, si c'est juste pour supprimer une clé, erase est surchargé dans le cas des maps pour prendre en paramètre une const key&

Code:

---

1 2	myMap.erase[1]; myMap.erase[2];

---

Le premier code de zenux n'est certainement pas un coup de bol, c'était la méthode recommandée (et la seule qui marche) pour effacer des élements d'une map dans une boucle for en C++03 !

voir par exemple : http://stackoverflow.com/questions/8...e-iterating-it

Depuis, En C++11, erase() a été corrigé pour retourner l'itérateur sur l'élément suivant, mais sur les vieux compilos on est toujours obligé d'utiliser l'astuce du m.erase(it++);

Merci pour vos réponses mais j'ai toujours un peu de mal à comprendre.
Dans mon exemple, c'est bien les éléments ayant la clef 1 et 2 qui sont supprimés (et pas 2 et 3).

La seul explication possible que je vois pour que le code source "m.erase(it++);" fonctionne est:

1) La méthode 'erase' prend une copie de 'it'
2) La variable 'it' est incrémentée
3) La méthode 'erase' s'exécute sur base la variable 'it' copié précédement afin de supprimer le bon élément (et pas le suivant)

Est-ce bien dans cet ordre que l'exécution fonctionne ?

Oui c'est exactement ça.
Toute l'astuce repose sur le comportement de l'incrémentation par l'opérateur de postincrémentation++. L'implémentation de cet opérateur ressemble plus ou moins à :

Code:

---

1 2 3 4 5 6 7

map_iterator map_iterator::operator++(int) //postincrémentation { map_iterator copy_it= *this; ++*this; return copy_it; }

---

il fait donc :
1) Une copie de l'itérateur
2) incrémente l'original
3) Renvoie la copie

C'est bien la copie non incrémentée qui est passé à erase().
Très important, l'incrémentation de l'original se fait *avant* l'appel à erase() car si erase() se finissait avant l'incrémentation alors l'itérateur n'aurait plus été valide.

Autant dire que c'est quand même bigrement subtil, en tout cas suffisamment pour surprendre koala et bousk ce qui n'est pas chose facile. :aie:
(et je mets dans le lot hein, la première fois que je suis tombé sur un code de ce style j'étais persuadé qu'il devait y avoir un bug quelque part)

Donc si tu n'as pas accès à un compilo récent (sur lequel il suffit de faire it = m.erase(it);) le mieux reste encore d'être explicite et de faire la copie à la main :

Code:

---

1 2 3 4 5 6 7

if(it->first==1 || it->first==2) { std::map<int, int>::iterator it_to_erase = it; it++; m.erase(it_to_erase); }

---

Merci beaucoup pour cette explication.
C'est maintenant très clair.