Pourquoi utiliser des itérateurs au lieu des indices de tableau?

Prenez les deux lignes de code suivantes:

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

Et ça:

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

On me dit que la deuxième voie est préférée. Pourquoi est-ce exactement cela?

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. Aussi, que comptez-vous faire dans le corps de la boucle? Si vous prévoyez d'accéder aux éléments comme dans

T elem = some_vector[i];

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

L'utilisation d'itérateurs vous rapproche de l' indépendance des conteneurs . Vous ne faites pas d'hypothèses sur la capacité d'accès aléatoire ou le size()fonctionnement rapide , mais seulement que le conteneur a des capacités d'itérateur.

Vous pouvez encore améliorer votre code en utilisant des algorithmes standard. Selon ce que vous essayez de réaliser, vous pouvez choisir de l'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 (étant donné que le bon algorithme est choisi), correct et réutilisable.

Cela fait partie du processus d'endoctrinement C ++ moderne. Les itérateurs sont le seul moyen d'itérer la plupart des conteneurs, vous l'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 déjà remplacé un vecteur par un autre type de conteneur.

Je pense que l'index du tableau est plus lisible. Il correspond à la syntaxe utilisée dans d'autres langages et à la syntaxe utilisée pour les tableaux C à l'ancienne. C'est aussi moins verbeux. L'efficacité devrait être un lavage si votre compilateur est bon, et il n'y a pratiquement aucun cas où cela importe de toute façon.

Malgré cela, je continue à utiliser fréquemment des itérateurs avec des vecteurs. Je crois que l'itérateur est un concept important, donc je le fais la promotion chaque fois que je le peux.

parce que 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 itérateurs, vous pouvez utiliser ce code sur n'importe quelle implémentation de liste.

Imaginez que some_vector soit implémenté avec une liste chaînée. La demande d'un élément à la i-ème place nécessite alors que i opérations soient effectuées pour parcourir la liste des nœuds. Maintenant, si vous utilisez l'itérateur, d'une 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 à chaque itération, nécessitant juste un opération unique).

Il fournit donc deux choses:

• Abstraction d'utilisation: vous voulez juste itérer certains éléments, peu vous importe comment le faire
• Performance

Je vais être l'avocat des démons ici, et je ne recommanderai pas les itérateurs. 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 ni besoin d'utiliser des itérateurs. Tout le temps, ils n'ont pas été nécessaires et deuxièmement, les hypothèses cachées et les cauchemars de débogage et de débogage que vous obtenez avec les itérateurs en font un excellent exemple pour ne pas l'utiliser dans les applications qui nécessitent de la vitesse.

Même du point de vue de la maintenance, ils sont un gâchis. 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 vecteur virtuel ou liste 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. Enfer, je sais même quelle version de la STL vous utilisez?

Le problème suivant que vous avez avec les itérateurs 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 vu et je n'ai toujours pas vu d'utilité dans les itérateurs. S'ils font abstraction de la liste ou du vecteur loin de vous, alors qu'en fait vous devriez déjà savoir à quel vecteur ou à quelle liste vous traitez si vous ne le faites pas, alors vous allez simplement vous préparer pour de grandes sessions de débogage à l'avenir.

Vous pouvez utiliser un itérateur si vous souhaitez ajouter / 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 utilisez des index, vous devrez mélanger les éléments vers le haut / bas dans le tableau pour gérer les insertions et les suppressions.

Séparation des préoccupations

C'est très agréable de séparer le code d'itération de la préoccupation «centrale» 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 itérateur de début et de fin active le code de boucle à utiliser avec d'autres types de conteneurs.

De plus, dans la std::for_eachmanière, vous dites à la collection quoi faire, au lieu de lui demander quelque chose sur ses internes

La norme 0x va introduire des fermetures, ce qui rendra cette approche beaucoup plus facile à utiliser - jetez un œil à la puissance expressive de Ruby par exemple [1..6].each { |i| print i; }...

Performance

Mais peut-être un problème beaucoup plus surveillé est que l'utilisation de l' for_eachapproche donne la possibilité de paralléliser l'itération - les blocs de threads Intel peuvent distribuer le bloc de code sur le nombre de processeurs dans le système!

Remarque: après avoir découvert la algorithmsbibliothèque, et surtout foreach, j'ai passé deux ou trois mois à écrire des structures d'opérateur 'helper' ridiculement petites qui rendront vos collègues développeurs fous. Après ce temps, je suis revenu à une approche pragmatique - les petits corps en boucle ne méritent pasforeach plus :)

Une référence incontournable sur les itérateurs est le livre "Extended STL" .

Le GoF a un petit petit paragraphe à la fin du modèle Iterator, qui parle de cette marque d'itération; cela s'appelle un «itérateur interne». Jetez un œil ici aussi.

Parce qu'il est plus orienté objet. si vous itérez avec un index, vous supposez:

a) que ces objets sont ordonnés
b) que ces objets peuvent être obtenus par un index
c) que l'incrément d'index atteindra chaque élément
d) que cet index commence à zéro

Avec un itérateur, vous dites "donnez-moi tout pour que je puisse travailler avec" sans savoir quelle est l'implémentation sous-jacente. (En Java, il existe des collections qui ne sont pas accessibles via un index)

De plus, avec un itérateur, pas besoin de s'inquiéter de sortir des limites du tableau.

Une autre bonne chose à propos des itérateurs est qu'ils permettent mieux d'exprimer (et d'appliquer) votre préférence const. Cet exemple garantit que vous ne modifierez pas le vecteur au milieu de votre boucle:

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

Mis à part toutes les autres excellentes réponses ... intpeut-être pas assez grandes pour votre vecteur. Au lieu de cela, si vous souhaitez utiliser l'indexation, utilisez le size_typepour votre conteneur:

for (std::vector<Foo>::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 itérateurs STL sont principalement là pour que les algorithmes STL comme sort puissent être indépendants du conteneur.

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

Il est moins dactylographique et plus facile à analyser pour la plupart des humains. Ce serait bien si C ++ avait une boucle foreach simple sans aller trop loin avec la magie des modèles.

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 un index moi-même car je le considère plus lisible et vous pouvez faire un accès aléatoire comme sauter en avant 6 éléments ou sauter en arrière si besoin est.

J'aime aussi faire référence à l'élément à l'intérieur de la boucle comme ceci, donc il n'y a pas beaucoup de crochets autour de l'endroit:

for(size_t i = 0; i < myvector.size(); i++)
{
    MyClass &item = myvector[i];

    // Do stuff to "item".
}

L'utilisation d'un itérateur peut être utile si vous pensez que vous devrez peut-être remplacer le vecteur par une liste à un moment donné dans le futur et il 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 avec plus de précision. 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 dans l'itérateur.

Après avoir appris un peu plus sur le sujet de cette réponse, je me rends compte que c'était un peu 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 se développer sur moi:

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

Les itérateurs déverrouillent certaines fonctionnalités déclaratives assez puissantes, et lorsqu'ils sont combinés avec la bibliothèque d'algorithmes STL, vous pouvez faire des choses assez intéressantes qui sortent du cadre de l'administration d'index de tableau.

L'indexation nécessite une mulopération supplémentaire . Par exemple, pour vector<int> v, le compilateur se convertit v[i]en &v + sizeof(int) * i.

Pendant l'itération, vous n'avez pas besoin de connaître le nombre d'articles à traiter. Vous avez juste besoin de l'article et les itérateurs font de très bonnes choses.

Personne n'a encore mentionné que l'un des avantages des index est qu'ils ne deviennent pas invalides lorsque vous les ajoutez à un conteneur contigu comme std::vector, vous pouvez donc ajouter des éléments au conteneur pendant l'itération.

Cela est également possible avec les itérateurs, mais vous devez appeler reserve(), et donc avoir besoin de savoir combien d'éléments vous ajouterez.

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

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

2. Pour éliminer toute dépendance sur l'optimisation du compilateur, vous pouvez déplacer some_vector.size () hors 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 itérateurs et traiter les post-incréments comme des cas exceptionnels.

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

En général, l'utilisation des itérateurs est préférable car les algorithmes les utilisent et le comportement peut être contrôlé (et implicitement documenté) en changeant le type de l'itérateur. Les emplacements de tableau peuvent être utilisés à la place des itérateurs, mais la différence syntaxique ressortira.

Je n'utilise pas d'itérateurs pour la même raison que je n'aime pas pour chaque déclaration. Lorsqu'il y a plusieurs boucles internes, il est assez difficile de garder une trace des variables globales / membres sans avoir à se souvenir de toutes les valeurs locales et des noms d'itérateurs également. Ce que je trouve utile, c'est d'utiliser deux ensembles d'indices pour différentes occasions:

for(int i=0;i<anims.size();i++)
  for(int j=0;j<bones.size();j++)
  {
     int animIndex = i;
     int boneIndex = j;


     // in relatively short code I use indices i and j
     ... animation_matrices[i][j] ...

     // in long and complicated code I use indices animIndex and boneIndex
     ... animation_matrices[animIndex][boneIndex] ...


  }

Je ne veux même pas abréger des choses comme "animation_matrices [i]" en un itérateur aléatoire nommé "anim_matrix" par exemple, car alors vous ne pouvez pas voir clairement de quel tableau provient cette valeur.

• Si vous aimez être proche du métal / ne faites pas confiance à leurs détails d'implémentation, n'utilisez pas d' itérateurs.
• Si vous changez régulièrement un type de collection pour un autre pendant le développement, utilisez des itérateurs.
• Si vous avez du mal à vous rappeler comment itérer différents types de collections (vous avez peut-être plusieurs types provenant de plusieurs sources externes différentes), utilisez des itérateurs pour unifier les moyens par lesquels vous parcourez les éléments. Cela s'applique, par exemple, à la commutation d'une liste chaînée avec une liste de tableaux.

Vraiment, c'est tout ce qu'il y a à faire. Ce n'est pas comme si vous alliez gagner en brièveté dans les deux cas en moyenne, et si la brièveté est vraiment votre objectif, vous pouvez toujours vous rabattre sur les macros.

Si vous avez accès aux fonctionnalités C ++ 11 , vous pouvez également utiliser une boucle basée surfor une plage pour itérer sur votre vecteur (ou tout autre conteneur) comme suit:

for (auto &item : some_vector)
{
     //do stuff
}

L'avantage de cette boucle est que vous pouvez accéder aux éléments du vecteur directement via la itemvariable, sans courir le risque de gâcher un index ou de faire une erreur lors du déréférencement d'un itérateur. De plus, l'espace réservé autovous évite d'avoir à répéter le type des éléments de conteneur, ce qui vous rapproche encore plus d'une solution indépendante du conteneur.

Remarques:

• Si vous avez besoin de l'index de l'élément dans votre boucle et qu'il operator[]existe pour votre conteneur (et qu'il est assez rapide pour vous), alors optez pour votre première méthode.
• Une forboucle basée sur une plage ne peut pas être utilisée pour ajouter / supprimer des éléments dans / depuis un conteneur. Si vous voulez le faire, mieux vaut vous en tenir à la solution proposée par Brian Matthews.
• Si vous ne voulez pas changer les éléments dans votre conteneur, vous devez utiliser le mot - clé constcomme suit: for (auto const &item : some_vector) { ... }.

Encore mieux que "dire au CPU quoi faire" (impératif), c'est "dire aux bibliothèques ce que vous voulez" (fonctionnel).

Donc, au lieu d'utiliser des boucles, vous devriez apprendre les algorithmes présents dans stl.

Pour l'indépendance des conteneurs

J'utilise toujours un index de tableau parce que beaucoup de mes applications nécessitent quelque chose comme "afficher l'image miniature". J'ai donc écrit quelque chose comme ceci:

some_vector[0].left=0;
some_vector[0].top =0;<br>

for (int i = 1; i < some_vector.size(); i++)
{

    some_vector[i].left = some_vector[i-1].width +  some_vector[i-1].left;
    if(i % 6 ==0)
    {
        some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
        some_vector[i].left = 0;
    }

}

Les deux implémentations sont correctes, mais je préférerais la boucle "for". Comme nous avons décidé d'utiliser un vecteur et non aucun autre conteneur, l'utilisation d'index serait la meilleure option. L'utilisation d'itérateurs avec des vecteurs perdrait l'avantage même d'avoir les objets dans des blocs de mémoire continue qui facilitent leur accès.

J'ai senti qu'aucune des réponses ici n'explique pourquoi j'aime les itérateurs comme concept général par rapport à l'indexation dans des conteneurs. Notez que la plupart de mon expérience avec les itérateurs ne vient pas réellement de C ++ mais de langages de programmation de niveau supérieur comme Python.

L'interface de l'itérateur impose moins d'exigences aux consommateurs de votre fonction, ce qui permet aux consommateurs d'en faire plus avec elle.

Si tout ce dont vous avez besoin est de pouvoir effectuer une itération directe, le développeur n'est pas limité à l'utilisation de conteneurs indexables - il peut utiliser n'importe quelle implémentation de classe operator++(T&), operator*(T)et operator!=(const &T, const &T).

#include <iostream>
template <class InputIterator>
void printAll(InputIterator& begin, InputIterator& end)
{
    for (auto current = begin; current != end; ++current) {
        std::cout << *current << "\n";
    }
}

// elsewhere...

printAll(myVector.begin(), myVector.end());

Votre algorithme fonctionne pour le cas où vous en avez besoin - itération sur un vecteur - mais il peut également être utile pour les applications que vous n'anticipez pas nécessairement:

#include <random>

class RandomIterator
{
private:
    std::mt19937 random;
    std::uint_fast32_t current;
    std::uint_fast32_t floor;
    std::uint_fast32_t ceil;

public:
    RandomIterator(
        std::uint_fast32_t floor = 0,
        std::uint_fast32_t ceil = UINT_FAST32_MAX,
        std::uint_fast32_t seed = std::mt19937::default_seed
    ) :
        floor(floor),
        ceil(ceil)
    {
        random.seed(seed);
        ++(*this);
    }

    RandomIterator& operator++()
    {
        current = floor + (random() % (ceil - floor));
    }

    std::uint_fast32_t operator*() const
    {
        return current;
    }

    bool operator!=(const RandomIterator &that) const
    {
        return current != that.current;
    }
};

int main()
{
    // roll a 1d6 until we get a 6 and print the results
    RandomIterator firstRandom(1, 7, std::random_device()());
    RandomIterator secondRandom(6, 7);
    printAll(firstRandom, secondRandom);

    return 0;
}

Tenter d'implémenter un opérateur entre crochets qui fait quelque chose de similaire à cet itérateur serait artificiel, tandis que l'implémentation de l'itérateur est relativement simple. L'opérateur entre crochets a également des implications sur les capacités de votre classe - que vous pouvez indexer à n'importe quel point arbitraire - qui peuvent être difficiles ou inefficaces à implémenter.

Les itérateurs se prêtent également à la décoration . Les utilisateurs peuvent écrire des itérateurs qui prennent un itérateur dans leur constructeur et étendent ses fonctionnalités:

template<class InputIterator, typename T>
class FilterIterator
{
private:
    InputIterator internalIterator;

public:
    FilterIterator(const InputIterator &iterator):
        internalIterator(iterator)
    {
    }

    virtual bool condition(T) = 0;

    FilterIterator<InputIterator, T>& operator++()
    {
        do {
            ++(internalIterator);
        } while (!condition(*internalIterator));

        return *this;
    }

    T operator*()
    {
        // Needed for the first result
        if (!condition(*internalIterator))
            ++(*this);
        return *internalIterator;
    }

    virtual bool operator!=(const FilterIterator& that) const
    {
        return internalIterator != that.internalIterator;
    }
};

template <class InputIterator>
class EvenIterator : public FilterIterator<InputIterator, std::uint_fast32_t>
{
public:
    EvenIterator(const InputIterator &internalIterator) :
        FilterIterator<InputIterator, std::uint_fast32_t>(internalIterator)
    {
    }

    bool condition(std::uint_fast32_t n)
    {
        return !(n % 2);
    }
};


int main()
{
    // Rolls a d20 until a 20 is rolled and discards odd rolls
    EvenIterator<RandomIterator> firstRandom(RandomIterator(1, 21, std::random_device()()));
    EvenIterator<RandomIterator> secondRandom(RandomIterator(20, 21));
    printAll(firstRandom, secondRandom);

    return 0;
}

Bien que ces jouets puissent sembler banals, il n'est pas difficile d'imaginer utiliser des itérateurs et des décorateurs d'itérateurs pour faire des choses puissantes avec une interface simple - décorer un itérateur en avant uniquement des résultats de la base de données avec un itérateur qui construit un objet modèle à partir d'un seul résultat, par exemple . Ces modèles permettent une itération efficace en mémoire d'ensembles infinis et, avec un filtre comme celui que j'ai écrit ci-dessus, une évaluation potentiellement paresseuse des résultats.

Une partie de la puissance des modèles C ++ est votre interface d'itérateur, lorsqu'elle est appliquée à des tableaux C de longueur fixe, se désintègre en une arithmétique de pointeur simple et efficace , ce qui en fait une abstraction vraiment sans coût.