Obtention d'un index dans un vecteur en utilisant des itérateurs

Question

Lors de l'itération sur des éléments d'un vecteur, il est préférable d'utiliser des itérateurs au lieu d'un index (voir Why use iterators instead of array indices?).

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 de la performance et de la flexibilité/extensibilité?

1. Revert à la boucle indexée

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

2. Calculer décalage

    
   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 envisagez d'utiliser exclusivement un vecteur, vous souhaiterez peut-être revenir à la boucle indexée, car il transmet votre intention plus clairement que itérateur-boucle. Cependant, si l'évolution de votre programme dans le futur peut conduire à un changement de conteneur, vous devriez vous en tenir aux itérateurs et utiliser std :: distance, ce qui est garanti pour fonctionner avec tous les itérateurs standards.

Answer 2

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

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

Answer 3

Rétablit la boucle indexée.

Fondamentalement 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 l'utilisation de l'itérateur était de simplifier votre code.

Answer 4

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 5

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

Dans l'exemple ci-dessus, si vous avez peut-être décidé d'échanger std :: vector pour std :: set (vous auriez peut-être besoin d'une collection unique d'éléments), utiliser iterators et distance() continuerait à fonctionner.

Je suis certain que les problèmes de performances seraient optimisés au point d'être négligeables.

Answer 6

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

Carl

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 beaucoup utiliser la valeur, je crée une référence, par commodité.

Les itérateurs vectoriels peuvent être légèrement plus rapides qu'un index en théorie, puisqu'ils utilisent l'arithmétique du pointeur pour parcourir la liste. Cependant, habituellement, je trouve 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 d'autre que de rendre votre boucle plus difficile à taper. (Je ne peux pas attendre l'auto de C++ 0x ..)