Comment faire une itération arrière dans une liste STL?

Question

J'écris du code multiplateforme entre Windows et Mac. Si list :: end() "renvoie un itérateur qui adresse l'emplacement suivant le dernier élément d'une liste" et qui peut être vérifié lors de la traversée d'une liste, quel est le meilleur moyen de reculer?

Ce code workson le Mac, mais pas sous Windows (ne peut pas décrémenter au-delà de premier élément):

list<DVFGfxObj*>::iterator iter = m_Objs.end(); 
for (iter--; iter!=m_Objs.end(); iter--)// By accident discovered that the iterator is circular ? 
{ 
} 

cela fonctionne sous Windows:

list<DVFGfxObj*>::iterator iter = m_Objs.end(); 
    do{ 
     iter--; 
    } while (*iter != *m_Objs.begin()); 

Y at-il une autre façon de traverser vers l'arrière que pourrait être mis en œuvre dans une boucle for?

Answer 1

Utilisez reverse_iterator au lieu de l'itérateur. Utilisez rbegin() & rend() au lieu de begin() & end().

Une autre possibilité, si vous aimez utiliser la macro BOOST_FOREACH, est d'utiliser la macro BOOST_REVERSE_FOREACH introduite dans Boost 1.36.0.

Answer 2

Vous voulez probablement les itérateurs inverses. De mémoire:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin(); 
for(; iter != m_Objs.rend(); ++iter) 
{ 
} 

Answer 3

Comme déjà mentionné par Ferruccio, l'utilisation reverse_iterator:

for (std::list<int>::reverse_iterator i = s.rbegin(); i != s.rend(); ++i) 

Answer 4

Cela devrait fonctionner:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin(); 
for (; iter!= m_Objs.rend(); iter++) 
{ 
} 

Answer 5

La meilleure/meilleure façon d'inverser itérer une liste est (comme déjà indiqué) d'utiliser des itérateurs inverses rbegin/rend.

Cependant, je tenais à mentionner que les itérateurs inverses sont implémentés en stockant la position de l'itérateur «courant» au cas par cas (au moins sur l'implémentation GNU de la bibliothèque standard).

Ceci est fait pour simplifier la mise en œuvre, pour la plage en sens inverse pour la même sémantique que toute une gamme avant [début, fin) et [rbegin, Déchirez)

Ce que cela signifie est que déréférencement une iterator consiste à créer un nouveau temporaire, et décrémenter ensuite, chaque fois:

reference 
    operator*() const 
    { 
_Iterator __tmp = current; 
return *--__tmp; 
    } 

Ainsi, déréférencement un reverse_iterator est plus lent qu'un iterator normal.

Cependant, vous pouvez utiliser à la place les itérateurs bidirectionnels réguliers pour simuler inverse itération vous, en évitant cette surcharge:

for (iterator current = end() ; current != begin() ; /* Do nothing */) 
{ 
    --current; // Unfortunately, you now need this here 
    /* Do work */ 
    cout << *current << endl; 
} 

Les essais ont montré que cette solution soit environ 5 fois plus rapide pour chaque déréférencer utilisé dans la corps de la boucle.

Remarque: Le test n'a pas été effectué avec le code ci-dessus, car std :: cout aurait été le goulot d'étranglement.Remarque: la différence d'heure de l'horloge murale était d'environ 5 secondes avec une taille std :: list de 10 millions d'éléments. Donc, de façon réaliste, à moins que la taille de vos données ne soit si grande, il suffit de s'en tenir à rbegin() rend()!