Pourquoi utiliser des iterators au lieu d’indices de tableaux?

La première forme n’est efficace que si vector.size () est une opération rapide. Cela est vrai pour les vecteurs, mais pas pour les listes, par exemple. De plus, que comptez-vous faire dans le corps de la boucle? Si vous envisagez d’accéder aux éléments comme dans

 T elem = some_vector[i]; 

alors vous faites l’hypothèse que l’ operator[](std::size_t) a défini operator[](std::size_t) . Encore une fois, cela est vrai pour le vecteur mais pas pour les autres conteneurs.

L’utilisation d’iterators vous rapproche de l’indépendance des conteneurs. Vous ne faites pas d’hypothèses sur la capacité d’access aléatoire ou sur la size() rapide size() , mais uniquement que le conteneur possède des capacités d’iterator.

Vous pouvez améliorer votre code en utilisant des algorithmes standard. Selon ce que vous essayez d’atteindre, vous pouvez choisir d’utiliser std::for_each() , std::transform() , etc. En utilisant un algorithme standard plutôt qu’une boucle explicite, vous évitez de réinventer la roue. Votre code est susceptible d’être plus efficace (avec le bon algorithme choisi), correct et réutilisable.

car vous n’attachez pas votre code à l’implémentation particulière de la liste some_vector. Si vous utilisez des indices de tableau, il doit s’agir d’une forme de tableau; Si vous utilisez des iterators, vous pouvez utiliser ce code sur n’importe quelle implémentation de liste.

Cela fait partie du processus moderne d’endocsortingnement C ++. Les iterators sont le seul moyen d’itérer la plupart des conteneurs, vous les utilisez donc même avec des vecteurs, juste pour vous mettre dans le bon état d’esprit. Sérieusement, c’est la seule raison pour laquelle je le fais – je ne pense pas avoir jamais remplacé un vecteur avec un autre type de conteneur.

Wow, cela est toujours en train d’être abaissé après trois semaines. Je suppose que ça ne paie pas d’être un peu ironique.

Je pense que l’index du tableau est plus lisible. Elle correspond à la syntaxe utilisée dans les autres langages et à la syntaxe utilisée pour les tableaux C anciens. C’est aussi moins verbeux. L’efficacité devrait être un lavage si votre compilateur est bon, et il n’y a pratiquement pas de cas où cela compte.

Malgré cela, je me retrouve toujours à utiliser des iterators fréquemment avec des vecteurs. Je crois que l’iterator est un concept important, donc je le fais chaque fois que je le peux.

Imagine que some_vector est implémenté avec une liste liée. Ensuite, demander un élément à la i-ème place nécessite que des opérations soient effectuées pour parcourir la liste des nœuds. Maintenant, si vous utilisez un iterator, de manière générale, il fera de son mieux pour être aussi efficace que possible (dans le cas d’une liste chaînée, il maintiendra un pointeur sur le nœud actuel et le fera avancer dans chaque itération). opération unique).

Donc, il fournit deux choses:

• Abstraction de l’utilisation: vous voulez juste itérer certains éléments, vous ne vous souciez pas de la façon de le faire
• Performance

Je vais être l’avocat des démons ici, et ne pas recommander les iterators. La principale raison est que tout le code source sur lequel j’ai travaillé, depuis le développement d’applications de bureau jusqu’au développement de jeux, n’a pas eu besoin d’utiliser des iterators. Pendant tout ce temps, ils n’ont pas été nécessaires et deuxièmement, les suppositions cachées, les erreurs de code et les problèmes de débogage que vous rencontrez avec les iterators en font un excellent exemple pour ne pas l’utiliser dans des applications exigeant de la vitesse.

Même d’un sharepoint vue de la maintenance, ils sont en désordre. Ce n’est pas à cause d’eux mais à cause de tous les alias qui se produisent derrière la scène. Comment puis-je savoir que vous n’avez pas implémenté votre propre liste de vecteurs virtuels ou de tableaux qui fait quelque chose de complètement différent des normes. Est-ce que je sais quel type est actuellement en cours d’exécution? Avez-vous surchargé un opérateur? Je n’ai pas eu le temps de vérifier tout votre code source. Dois-je même savoir quelle version de la STL vous utilisez?

Le prochain problème que vous avez rencontré avec les iterators est l’abstraction qui fuit, bien qu’il existe de nombreux sites Web qui en discutent en détail avec eux.

Désolé, je n’ai pas et n’ai toujours pas vu de points dans les iterators. S’ils vous séparent de la liste ou du vecteur, alors vous devriez déjà savoir quel vecteur ou quelle liste vous traitez si vous ne le faites pas, alors vous allez vous préparer à de futures sessions de débogage.

Vous voudrez peut-être utiliser un iterator si vous souhaitez append / supprimer des éléments au vecteur pendant que vous l’itérez.

 some_iterator = some_vector.begin(); while (some_iterator != some_vector.end()) { if (/* some condition */) { some_iterator = some_vector.erase(some_iterator); // some_iterator now positioned at the element after the deleted element } else { if (/* some other condition */) { some_iterator = some_vector.insert(some_iterator, some_new_value); // some_iterator now positioned at new element } ++some_iterator; } } 

Si vous utilisiez des index, vous devrez mélanger les éléments dans le tableau pour gérer les insertions et les suppressions.

Séparation des préoccupations

Il est très intéressant de séparer le code d’itération du problème de base de la boucle. C’est presque une décision de conception.

En effet, l’itération par index vous lie à l’implémentation du conteneur. Demander au conteneur un iterator de début et de fin active le code de boucle à utiliser avec d’autres types de conteneur.

De plus, dans la méthode std::for_each , vous dites à la collection quoi faire, au lieu de lui demander quelque chose à propos de ses composants internes.

Le standard 0x va introduire des fermetures, ce qui rendra cette approche beaucoup plus facile à utiliser – jetez un coup d’œil à la puissance expressive, par exemple, de Ruby’s [1..6].each { |i| print i; } [1..6].each { |i| print i; } [1..6].each { |i| print i; } …

Performance

Mais peut-être un problème beaucoup plus important est que l’utilisation de l’approche for_each donne l’opportunité de paralléliser l’itération – les blocs de threads d’Intel peuvent dissortingbuer le bloc de code sur le nombre de processeurs du système!

Note: après avoir découvert la bibliothèque d’ algorithms , et surtout foreach , j’ai passé deux ou trois mois à écrire des structures d’opérateurs «ridiculement petites» qui rendront vos développeurs fous. Après cette période, je suis revenu à une approche pragmatique – les petits organismes en boucle ne méritent plus de rien 🙂

Une référence incontournable sur les iterators est le livre “Extended STL” .

Le GoF a un tout petit paragraphe à la fin du schéma Iterator, qui parle de cette marque d’itération; c’est ce qu’on appelle un “iterator interne”. Regardez aussi ici .

Parce que c’est plus orienté object. si vous effectuez une itération avec un index, vous supposez:

a) que ces objects sont commandés
b) que ces objects peuvent être obtenus par un index
c) que l’incrément d’index va bash chaque article
d) que cet indice commence à zéro

Avec un iterator, vous dites “donnez-moi tout pour pouvoir travailler avec” sans savoir quelle est l’implémentation sous-jacente. (En Java, il existe des collections inaccessibles via un index)

De plus, avec un iterator, pas besoin de vous soucier de sortir des limites du tableau.

Une autre bonne chose à propos des iterators est qu’ils vous permettent d’exprimer (et d’appliquer) vos préférences constantes. Cet exemple garantit que vous ne modifierez pas le vecteur au milieu de votre boucle:

 for(std::vector::const_iterator pos=foos.begin(); pos != foos.end(); ++pos) { // Foo & foo = *pos; // this won't comstack const Foo & foo = *pos; // this will comstack } 

Mis à part toutes les autres excellentes réponses … int peut ne pas être assez grand pour votre vecteur. Si vous souhaitez utiliser l’indexation, utilisez size_type le size_type pour votre conteneur:

 for (std::vector::size_type i = 0; i < myvector.size(); ++i) { Foo& this_foo = myvector[i]; // Do stuff with this_foo } 

Je devrais probablement souligner que vous pouvez également appeler

std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);

Les iterators STL sont principalement là pour que les algorithmes STL comme le sorting puissent être indépendants des conteneurs.

Si vous voulez simplement parcourir toutes les entrées d’un vecteur, utilisez simplement le style de boucle d’index.

Il est moins typé et plus facile à parsingr pour la plupart des humains. Ce serait bien si C ++ avait une simple boucle foreach sans dépasser la magie des templates.

 for( size_t i = 0; i < some_vector.size(); ++i ) { T& rT = some_vector[i]; // now do something with rT } ' 

Je ne pense pas que cela fasse beaucoup de différence pour un vecteur. Je préfère utiliser moi-même un index car je le considère plus lisible et que vous pouvez effectuer un access aléatoire comme sauter en avant de 6 éléments ou revenir en arrière si besoin est.

J’aime aussi faire une référence à l’élément à l’intérieur de la boucle pour qu’il n’y ait pas beaucoup de crochets autour de la place:

 for(size_t i = 0; i < myvector.size(); i++) { MyClass &item = myvector[i]; // Do stuff to "item". } 

Utiliser un iterator peut être utile si vous pensez que vous pourriez avoir besoin de remplacer le vecteur par une liste à un moment donné et que cela semble également plus élégant pour les monstres de la STL, mais je ne peux penser à aucune autre raison.

Le deuxième formulaire représente ce que vous faites plus précisément. Dans votre exemple, vous ne vous souciez pas vraiment de la valeur de i – tout ce que vous voulez, c’est l’élément suivant de l’iterator.

Après avoir appris un peu plus sur le sujet de cette réponse, je me rends compte que c’était une simplification excessive. La différence entre cette boucle:

 for (some_iterator = some_vector.begin(); some_iterator != some_vector.end(); some_iterator++) { //do stuff } 

Et cette boucle:

 for (int i = 0; i < some_vector.size(); i++) { //do stuff } 

Est assez minime. En fait, la syntaxe de faire des boucles de cette façon semble augmenter sur moi:

 while (it != end){ //do stuff ++it; } 

Les iterators permettent de débloquer certaines fonctionnalités déclaratives assez puissantes et, combinées à la bibliothèque d'algorithmes STL, vous pouvez faire des choses plutôt intéressantes qui ne relèvent pas de l'administration des index de tableaux.

L’indexation nécessite une opération supplémentaire. Par exemple, pour le vector v , le compilateur convertit v[i] dans &v + sizeof(int) * i .

Pendant l’itération, vous n’avez pas besoin de connaître le nombre d’éléments à traiter. Vous avez juste besoin de l’élément et les iterators font de telles choses très bien.

Plusieurs bons points déjà. J’ai quelques commentaires supplémentaires:

1. En supposant que nous parlions de la bibliothèque standard C ++, “vector” implique un conteneur d’access aléatoire qui a les garanties de C-array (access aléatoire, disposition de la mémoire contiguos, etc.). Si vous aviez dit “some_container”, la plupart des réponses ci-dessus auraient été plus précises (indépendance des conteneurs, etc.).

2. Pour éliminer les dépendances sur l’optimisation du compilateur, vous pouvez déplacer some_vector.size () de la boucle dans le code indexé, comme ceci:

     const size_t numElems = some_vector.size ();
    pour (size_t i = 0; i 

3. Toujours pré-incrémenter les iterators et traiter les post-incréments comme des cas exceptionnels.

pour (some_iterator = some_vector.begin (); some_iterator! = some_vector.end (); ++ some_iterator) {// faire des trucs}

Donc, en supposant et indexable std::vector<> comme conteneur, il n’y a pas de bonne raison de préférer l’un à l’autre, en passant séquentiellement dans le conteneur. Si vous devez vous référer fréquemment à des index elemnent plus anciens ou plus récents, la version indexée est plus appropriée.

En général, l’utilisation des iterators est préférable car les algorithmes les utilisent et le comportement peut être contrôlé (et implicitement documenté) en modifiant le type de l’iterator. Les emplacements des tableaux peuvent être utilisés à la place des iterators, mais la différence syntaxique sera évidente.

Je n’utilise pas d’iterators pour la même raison que je n’aime pas les déclarations de principe. Lorsque vous avez plusieurs boucles internes, il est assez difficile de suivre les variables globales / membres sans avoir à mémoriser toutes les valeurs locales et les noms des iterators. Ce que je trouve utile, c’est d’utiliser deux ensembles d’indices pour différentes occasions:

 for(int i=0;i