Boucle de suppression d'éléments d'une Map

Bonjour,
j'ai un petit problème avec ce code :

Code:

---

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

void CTest::PurgeRequest () { CSingleLock Lock (&m_semRequest, TRUE);   std::map<DWORD, HCALL>::iterator it;   for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); it ++) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it ); }   return;   }// CTest::PurgeRequest

---

Ma suppression n'est pas correcte, et fait planter si je supprime le dernier élément.
J'ai bien regardé cette page :
http://c.developpez.com/faq/cpp/?pag...ssion_elements
mais cela ne semble pas adapté au parcours des map ...

Merci de votre aide.

Avec

Code:

---

m_mapWaitReq.erase( it->first );

---

ça donne quoi?

Personnelement, j ai l'habitude de mettre a jour l'iterateur a partir de la methode erase:

Code:

---

it = m_mapWaitReq.erase( it->first );

---

Sauf que std::map::erase renvoie un void (ne me demandez pas pourquoi). Sous Visual C++ il me semble qu'il renvoie bien un itérateur, mais ce n'est pas standard.

Solution de rechange :

Code:

---

1 2 3 4 5 6 7

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); ) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it++ ); else ++it; }

---

avec

Code:

---

it->first

---

(clé comme paramètre), la map fait son propre algo de suppression donc ça marche. Par contre, j'ai peur que ce soir un peu plus lent...

Merci à vous !

Effectivement sous VC++ il renvoie un iterateur. Bon j'aurais pu utiliser comme ça, car je suis sous VC++, mais comme j'avais lu dans la faq que ça ne renvoie rien, j'avais peur de la portabilité ....

Laurent, une question : pourquoi utilises-tu un coup it++, un coup ++it ? y a -til une raison ?

Citation:

---

Envoyé par poukill

avec

Code:

---

it->first

---

(clé comme paramètre), la map fait son propre algo de suppression donc ça marche. Par contre, j'ai peur que ce soir un peu plus lent...

---

Non, ça ne marche pas non plus, car je retourne sur le it++ qui plante

Citation:

---

Envoyé par poukill

avec

Code:

---

it->first

---

(clé comme paramètre), la map fait son propre algo de suppression donc ça marche. Par contre, j'ai peur que ce soir un peu plus lent...

---

A mon avis ça ne marchera pas plus, la version de erase qui prend une clé en paramètre recherche l'itérateur avec find puis appelle la version d'erase prenant un itérateur. Puisqu'on fait le parcours nous-même ici, autant passer directement l'itérateur à erase.

De toute façon ce n'est pas un problème de fonction, mais de logique : si tu supprimes un élément, tu ne peux pas demander à ce que l'itérateur qui pointait dessus soit encore valide après.

Salut

A moins de supprimer les éléments au fur et à mesure de leur invalidation (chaque fois qu'il y en a un dont la valeur passe à NULL), il n'y a qu'une solution qui tient dans l'algorithme:

Code:

---

1 2 3 4 5 6 7 8 9 10

iterateur <- map.begin() Tant que iterateur!= map.end() | si iterateur->second=NULL | | suppression iterateur | | iterateur <- map.begin() | SINON | | iterateur ++ | FIN SI FIN TANT

---

Mais cela nous emmenera à une complexité en N! :P

Citation:

---

Envoyé par koala01

A moins de supprimer les éléments au fur et à mesure de leur invalidation (chaque fois qu'il y en a un dont la valeur passe à NULL), il n'y a qu'une solution qui tient dans l'algorithme

---

La solution que j'ai donnée ici est quand même censée marcher. Mais bon on dirait que personne ne l'a vue.

Si si... Bien sûr...
Moi je faisais que poser une question !!! :D

Autant pour moi, laurent, je ne l'avais effectivement pas vue...

Mais, disons, que de manière générale, je suis quelque peu allergique à l'idée de créer une boucle incrémentale sans fournir les trois valeurs explicitement :P

les for( ;; ) for(i=0;i<n; ) et autres for(i=0,j=0;i<n;i++,j++) du meme style, pourtant autorisées par le C++, ont tendance à me faire hérisser le poil :P

Rien n'empêche de la remplacer par un while ;)

Je préfère, en effet, et tu remarqueras que c'est en substance le but de l'algorithme prorosé :D

Citation:

---

Envoyé par Laurent Gomila

La solution que j'ai donnée ici est quand même censée marcher. Mais bon on dirait que personne ne l'a vue.

---

Heu perso, je l'ai bien vue, et même que depuis 1 heure je m'en sers !! :D
MERCI !

Effectivement, on peut aussi faire un while ... mais qui fait repartir à chaque suppression au début 8O
Bon, dans mon cas, c'est pas trés dérangeant ... mais de manière générale si.
Je préfère donc fournir 2 valeurs dans un for, plutôt qu'avoir un while + lent.

Le while est équivalent au for, c'est juste écrit différemment.

Code:

---

1 2 3 4 5 6 7 8

it = m_mapWaitReq.begin(); while (it != m_mapWaitReq.end()) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it++ ); else ++it; }

---

Citation:

---

Envoyé par koala01

Salut

A moins de supprimer les éléments au fur et à mesure de leur invalidation (chaque fois qu'il y en a un dont la valeur passe à NULL), il n'y a qu'une solution qui tient dans l'algorithme:

Code:

---

1 2 3 4 5 6 7 8 9 10

iterateur <- map.begin() Tant que iterateur!= map.end() | si iterateur->second=NULL | | suppression iterateur | | iterateur <- map.begin() | SINON | | iterateur ++ | FIN SI FIN TANT

---

Mais cela nous emmenera à une complexité en N! :P

---

Oui oui en effet, mais ce n'est pas ce que l'algo de Koala (cf. ci-dessus) sous-entendait ...

Bonjour,

Désolé de relancer un sujet aussi ancien, mais je ne vois pas la différence que vous faites entre

Code:

---

1 2 3 4 5 6 7

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); ) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it++ ); else ++it; }

---

et

Code:

---

1 2 3 4 5 6 7

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); ) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it );   ++it; }

---

ou encore

Code:

---

1 2 3 4 5

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); it++) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it ); }

---

Bon ce fût bref et je me réponds moi-même :lol:

erase(it++) crée une copie de it qu'il passe à erase, l'incrémentation est effectuée sur sa valeur originale. D'où la différence entre
erase(it);
it++;
et
erase(it++);

Cela répond aussi du coup à la question de olive_le_malin posée plus haut : it++ réalise une copie alors que ++it ne passe pas par cette étape. C'est pour cela qu'il vaut mieux utiliser ++it quand c'est possible pour question de performances.

Donc ok pour :

Code:

---

1 2 3 4 5 6 7

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); ) { if( GetInCallFromHandle( (*it).second ) == NULL ) m_mapWaitReq.erase( it++ ); else ++it; }

---

Sauf que la question originale a été posté en 2007. Depuis, le C++11 est passé par là et le standard a été corrigé pour qu'erase() retourne l'itérateur suivant. Il est donc maintenant recommandé pour plus de clarté d'écrire :

Code:

---

1 2 3 4 5 6 7 8

for( it = m_mapWaitReq.begin(); it != m_mapWaitReq.end(); ) { if( GetInCallFromHandle( (*it).second ) == NULL ) it = m_mapWaitReq.erase(it); else ++it; }

---