parcourir une liste de la fin vers le début

Bonjour,

Voilà j'ai tenté ceci pour parcourir une stl::list de la fin au début:

Code:

---

1 2 3 4 5 6 7 8

list<CObjectBase*>::iterator iter; for (iter = objectList.end(); iter != objectList.begin(); iter--) { ... if (...) objectList.erase(iter); }

---

Apparement ce code me fait un jolie segfault. Comment faire alors ?

Et aussi, dans cette boucle sous certaines conditions je suis amenté a supprimer iter de la liste mais je me demande si apres ça on peut continuer gentillement la boucle ?? ou ça risque aussi de provoquer des segfault ? Donc si ça risque de provoquer des miseres, comment faire ça ??

Merci !

dans le cas d'un iterator non reverse, l'iterator .end() pointe après le dernier element.
Si tu veux parcourir ta liste dans le sens inverse tu doi utiliser un reverse iterator:

Code:

---

1 2 3 4 5 6 7 8 9

list<CObjectBase*>::reverse_iterator iter; for (iter = objectList.rbegin(); iter != objectList.rend(); iter++) { ... if (...) objectList.erase(iter); } [fais à la volée]

---

oké je connaissais pas. Merci.

Cependant j'ai un autre probleme, apparement list::erase() n'est pas défini sur un revers_iterator.... Comment faire alors pour enlever des elements pendant le parcour ?

Pourquoi dois-tu la parcourir dans le sens inverse?

Attention à la fonction erase qui va invalider l'itérateur.

Code:

---

1 2 3 4 5 6 7 8 9

list<CObjectBase*>::reverse_iterator iter; for (iter = objectList.rbegin(); iter != objectList.rend(); ) { ... if (...) iter = objectList.erase(iter); else ++iter; }

---

Pour ce qui est d'erase + reverse_iterator, effectivement c'est un problème. Plusieurs solutions bourrins : récupérer l'indice de ton itérateur, puis faire avancer un iterator de size - indice à partir de begin. Ainsi tu pointeras sur le même élément mais avec un iterator. Ou encore inverser ta liste avant parcours puis la réinverser après.

Il me semble qu'il existait des conversions automatiques entre les types d'itérateurs, il faudrait voir si dans ce cas ce ne serait pas possible.

En fait c'est pour une lib SDL_gui que je suis entriant de developper pour un jeu que je fais... Et donc la liste des objets doit etre affiché dans un sens, mais runnée dans l'autre sens car la derniere à etre affichée est la 1er a recevoir les messages de souris etc...

Ce que je vais faire c'est inverser la liste une fois pour toutes et faire l'affichage avec des revers_iterator comme ça j'ai pas le probleme du erase :)

Cela dit, d'un maniere ou de l'autre si l'iterator est invalidé apres un erase ça va merder.... je vais faire des testes pour voir si ça marche...

Pas sur que ce soit tres propre mais tu peux faire comme ça :

Code:

---

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

list<int> test; test.push_back(5); test.push_back(6); test.push_back(7); test.push_back(8); test.push_back(9);   typedef list<int>::reverse_iterator iter; for(iter it = test.rbegin(); it != test.rend(); ++it) { if((*it) == 6) test.erase(--(it.base())); }

---

Citation:

---

Cela dit, d'un maniere ou de l'autre si l'iterator est invalidé apres un erase ça va merder....

---

Ben suffit de gérer ça correctement, comme je te l'ai montré :wink:

Citation:

---

Code:

---

test.erase(--(it.base()));

---

---

Bien vu ! C'est bien comme cela qu'on peut passer d'un reverse_iterator à un iterator. Maintenant je me souviens où j'avais vu ça : dans Effective STL, il y a un diagramme expliquant les relations entre les différents types d'itérateurs et comment passer de l'un à l'autre.

j'ai ptetre une idée, un truc comme ça:

iter_next = iter + 1;
objectList.erase(iter);
iter = iter_next;

Loulou24 > ici je vois que erase retourne void, donc ça marchera pas ton algo il me semble... je vais qd meme essayer ;)

Mauvaise doc :wink:

http://www.sgi.com/tech/stl/List.html

Citation:

---

iterator erase(iterator pos)
Erases the element at position pos.

---

En ce qui concerne ta solution, l'opérateur + est reservé aux RandomAccessIterator (ceux des vector). Ici tu aurais dû utiliser ++.

oké c'est vrai que cette doc est plus complete :)

Donc en combiant les 2solus ça donne ça:

Code:

---

1 2 3 4 5 6 7 8 9 10

list<CObjectBase*>::reverse_iterator iter; for (iter = objectList.rbegin(); iter != objectList.rend(); ) { ... if (...) iter = objectList.erase(--(iter.base())); else ++iter; }

---

Comme ça pas de risque que iter soit invalidé, et avec le ptit truc du --(iter.base()) on peut erase() un reverse_iterator :)

Merci !

[edit] sauf que erase ne retourne retourne pas un reverse_iterator, mais un iterator....

La conversion inverse est possible également : les reverse_iterator possèdent un constructeur (explicite) qui leur permet de se construire à partir d'un iterator.

Mais bon, après tant de bidouilles, la solution qui me parait la plus propre, simple et performante était ta première idée :

Citation:

---

Ce que je vais faire c'est inverser la liste une fois pour toutes et faire l'affichage avec des revers_iterator comme ça j'ai pas le probleme du erase

---

Loulou, l'article dont tu parles dans effective STL est aussi disponible en ligne : http://www.aristeia.com/Papers/CUJ_June_2001.pdf