Pourquoi «! =» Est-il utilisé avec des iterators au lieu de «<»?

J’ai l’habitude d’écrire des boucles comme celle-ci:

for (std::size_t index = 0; index < foo.size(); index++) { // Do stuff with foo[index]. } 

Mais quand je vois des boucles d’iterators dans le code des autres, elles ressemblent à ceci:

 for (Foo::Iterator iterator = foo.begin(); iterator != foo.end(); iterator++) { // Do stuff with *Iterator. } 

Je trouve que l’ iterator != foo.end() est hors-jeu. Cela peut aussi être dangereux si l’ iterator est incrémenté de plus d’un.

Il semble plus “correct” d’utiliser l’ iterator < foo.end() , mais je ne le vois jamais dans le code réel. Pourquoi pas?

Tous les iterators sont égaux. Seuls les iterators à access aléatoire sont comparables sur le plan relationnel. Les iterators d’entrée, les iterators directs et les iterators bidirectionnels ne sont pas comparables sur le plan relationnel.

Ainsi, la comparaison utilisant != Est plus générique et flexible que la comparaison utilisant < .


Il existe différentes catégories d'iterators car toutes les plages d'éléments n'ont pas les mêmes propriétés d'access. Par exemple,

  • Si vous avez des iterators dans un tableau (une séquence contiguë d'éléments), il est sortingvial de les comparer. il suffit de comparer les indices des éléments pointés (ou les pointeurs vers ceux-ci, car les iterators ne contiennent probablement que des pointeurs vers les éléments);

  • Si vous avez des iterators dans une liste chaînée et que vous voulez tester si un iterator est "inférieur" à un autre iterator, vous devez parcourir les noeuds de la liste chaînée depuis un iterator jusqu'à atteindre l'autre iterator ou à la fin de la liste.

La règle est que toutes les opérations sur un iterator doivent avoir une complexité temporelle constante (ou, au minimum, une complexité de temps sublinéaire). Vous pouvez toujours effectuer une comparaison d'égalité en temps constant car il vous suffit de comparer si les iterators pointent vers le même object. Donc, tous les iterators sont égaux en termes d'égalité.


De plus, vous n'êtes pas autorisé à incrémenter un iterator après la fin de la plage dans laquelle il pointe. Donc, si vous vous retrouvez dans un scénario où it != foo.end() ne fait pas la même chose que it < foo.end() , vous avez déjà un comportement indéfini parce que vous avez parcouru la fin de la plage.

La même chose est vraie pour les pointeurs dans un tableau: vous n'êtes pas autorisé à incrémenter un pointeur au-delà du bout du tableau; un programme qui le fait montre un comportement indéfini. (La même chose n'est évidemment pas vraie pour les indices, car les indices ne sont que des entiers.)

Certaines implémentations de la bibliothèque standard (comme l'implémentation de la bibliothèque standard Visual C ++) ont un code de débogage utile qui génère une assertion lorsque vous faites quelque chose d'illégal avec un iterator comme celui-ci.

Réponse courte: Comme Iterator n’est pas un nombre, c’est un object.

Réponse plus longue: Il existe plus de collections que les tableaux linéaires. Les arbres et les hachages, par exemple, ne se prêtent pas vraiment à “cet index est avant cet autre index”. Pour un arbre, par exemple, deux index qui vivent sur des twigs distinctes. Ou, deux index dans un hash – ils n’ont aucun ordre, donc tout ordre que vous leur imposez est arbitraire.

Vous n’avez pas à vous soucier de la “disparition” de End() . Ce n’est pas non plus un nombre, c’est un object qui représente la fin de la collection. Cela n’a pas de sens d’avoir un iterator qui le dépasse, et même pas.