Obtenir un index dans un vecteur en utilisant des itérateurs

Question

Lors d'une itération sur des éléments d'un vecteur, il est préférable d'utiliser des itérateurs plutôt qu'un index (voir Pourquoi utiliser des itérateurs plutôt que des index de tableaux? ).

std::vector<T> vec;
std::vector<T>::iterator it;
for ( it = vec.begin(); it != vec.end(); ++it )
{
   // do work
}

Cependant, il peut être nécessaire d’utiliser l’index dans le corps de la boucle. Lequel des éléments suivants serait préférable dans ce cas, compte tenu des performances et de la flexibilité / extensibilité?

1. Revenir à la boucle indexée

   std::vector vec;
   size_t i;
   for ( i = 0; i < vec.size(); ++i )
   {
      // use i
   }
   

2. Calculer l'offset

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = it - vec.begin(); 
      // use i
   }
   

3. Utilisez std :: distance

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = std::distance( vec.begin(), it );
      // use i
   }
   

Answer 1

Si vous prévoyez d'utiliser exclusivement un vecteur, vous voudrez peut-être revenir à la boucle indexée, car elle traduit votre intention plus clairement que la boucle itérateur. Cependant, si l'évolution de votre programme à l'avenir peut entraîner un changement de conteneur, vous devez vous en tenir aux itérateurs et utiliser std :: distance, qui est garanti pour fonctionner avec tous les itérateurs standard.

Answer 2

Utiliser std :: distance est un peu plus générique car il fonctionne pour tous les itérateurs, pas seulement les itérateurs à accès aléatoire. Et cela devrait être aussi rapide que It - vec.begin () en cas d’itérateurs à accès aléatoire.

It - vec.begin () est essentiellement une arithmétique de pointeur.

Answer 3

std :: distance (vec.begin (), it) vous donnera l'index qu'il pointe , en supposant qu'il pointe dans vec .

Carl

Answer 4

Revenez à la boucle indexée.

En gros, dans 90% des cas, les itérateurs sont supérieurs, c’est l’un de ces 10%. En utilisant un itérateur, vous rendez le code plus complexe et donc plus difficile à comprendre, alors que la raison principale de son utilisation était de simplifier votre code.

Answer 5

Il vous manque une solution: conservez un index au cas où vous en auriez besoin, mais ne l'utilisez pas comme condition de boucle. Fonctionne aussi sur les listes, et les coûts (par boucle) sont O (n) et un registre supplémentaire.

Answer 6

J'aurais toujours tendance à rester avec les itérateurs pour des raisons de développement futur.

Dans l'exemple ci-dessus, si vous décidiez peut-être de remplacer std :: vector par std :: set (vous aviez peut-être besoin d'une collection d'éléments unique), l'utilisation d'itérateurs et de distance () continuerait à fonctionner.

Je suis presque sûr que tous les problèmes de performances seraient optimisés au point d’être négligeables.

Answer 7

Pour les vecteurs, j'utilise toujours la méthode des nombres entiers. Chaque index dans le vecteur a la même vitesse qu'une recherche de tableau. Si je vais utiliser beaucoup la valeur, je crée une référence, par souci de commodité.

Les itérateurs de vecteurs

peuvent être légèrement plus rapides qu'un index en théorie, car ils utilisent l'arithmétique de pointeur pour parcourir la liste. Cependant, je trouve généralement que la lisibilité vaut la différence d’exécution minimale.

J'utilise des itérateurs pour d'autres types de conteneurs, et parfois lorsque vous n'avez pas besoin de la variable de boucle. Mais si vous avez besoin de la variable de boucle, vous ne faites rien, sauf rendre votre boucle plus difficile à taper. (Je ne peux pas attendre pour l'auto de c ++ 0x.)