Je suis en train d'itérer sur un vecteur et j'ai besoin de l'index sur lequel l'itérateur pointe actuellement. Il y a deux façons d'y parvenir :
it - vec.begin()std::distance(vec.begin(), it)Quels sont les avantages et les inconvénients de ces méthodes ?
Je préférerais it - vec.begin() précisément pour la raison opposée donnée par Naveen : ainsi, elle ne serait pas compiler si vous changez le vecteur en une liste. Si vous faites cela à chaque itération, vous pourriez facilement finir par transformer un algorithme O(n) en un algorithme O(n^2).
Une autre option, si vous ne sautez pas dans le conteneur pendant l'itération, serait de conserver l'index comme deuxième compteur de boucle.
Nota: it est un nom commun pour un itérateur de conteneur, std::container_type::iterator it; .
Je suis d'accord. Je dirais que le signe moins est le meilleur, mais il serait mieux de garder un deuxième compteur de boucle que d'utiliser std::distance, précisément parce que cette fonction pourrait être lente.
Ajouter un second compteur de boucle est une solution tellement évidente que je suis gêné de ne pas y avoir pensé.
Je préférerais std::distance(vec.begin(), it) car cela me permettra de changer le conteneur sans modifier le code. Par exemple, si vous décidez d'utiliser std::list au lieu de std::vector qui ne fournit pas d'itérateur à accès aléatoire, votre code sera toujours compilé. Comme std::distance choisit la méthode optimale en fonction des traits de l'itérateur, vous n'aurez pas non plus de dégradation des performances.
Lorsque vous utilisez un conteneur sans itérateurs à accès aléatoire, il vaut mieux pas à calculer de telles distances parce que c'est inefficace.
@Eli : Je suis d'accord avec cela, mais dans un cas très spécial si c'est vraiment nécessaire, alors ce code fonctionnera quand même.
Je pense que le code doit être modifié de toute façon si le conteneur change - avoir une variable std::list nommée vec est une mauvaise nouvelle. Si le code était réécrit pour être générique, en prenant le type de conteneur comme paramètre de modèle, c'est à ce moment-là que nous pourrions (et devrions) parler de la gestion des itérateurs à accès non aléatoire ;-)
Comme l'ont montré OncleBens et Naveen, il y a de bonnes raisons pour les deux. Lequel est le "meilleur" dépend du comportement que vous souhaitez : Voulez-vous garantir un comportement en temps constant, ou voulez-vous qu'il revienne au temps linéaire si nécessaire ?
it - vec.begin() prend un temps constant, mais le operator - n'est défini que sur les itérateurs à accès aléatoire, donc le code ne compilera pas du tout avec les itérateurs de liste, par exemple.
std::distance(vec.begin(), it) fonctionne pour tous les types d'itérateurs, mais ne sera une opération en temps constant que si elle est utilisée sur des itérateurs à accès aléatoire.
Aucun n'est "meilleur". Utilisez celui qui fait ce dont vous avez besoin.
Il est plus clair d'utiliser la soustraction pour trouver la distance que d'utiliser, littéralement, le mot distance ?
@Travis, pour moi, ça l'est. C'est une question de goût et de coutume. Nous disons it++ et non quelque chose comme std::increment(it) n'est-ce pas ? Cela ne serait-il pas aussi considéré comme moins clair ?
El ++ est défini dans le cadre des séquences STL comme la façon dont nous incrémentons l'itérateur. std::distance calcule le nombre d'éléments entre le premier et le dernier élément. Le fait que le - l'opérateur fonctionne n'est qu'une coïncidence.
Si vous avez déjà restreint ou codé en dur votre algorithme à l'utilisation d'un fichier std::vector::iterator y std::vector::iterator seulement, la méthode que vous finirez par utiliser n'a pas vraiment d'importance. Votre algorithme est déjà concrétisé au-delà du point où le choix de l'une ou l'autre peut faire une quelconque différence. Les deux font exactement la même chose. C'est juste une question de préférence personnelle. Personnellement, j'utiliserais la soustraction explicite.
Si, en revanche, vous souhaitez conserver un degré de généralité plus élevé dans votre algorithme, c'est-à-dire laisser la possibilité qu'un jour, dans le futur, il puisse être appliqué à un autre type d'itérateur, alors la meilleure méthode dépend de votre intention. Elle dépend du degré de restriction que vous souhaitez appliquer au type d'itérateur qui peut être utilisé ici.
Si vous utilisez la soustraction explicite, votre algorithme sera limité à une classe assez étroite d'itérateurs : les itérateurs à accès aléatoire. (C'est ce que vous obtenez maintenant de std::vector )
Si vous utilisez distance votre algorithme supportera une classe d'itérateurs beaucoup plus large : les itérateurs d'entrée.
Bien sûr, le calcul distance pour les itérateurs à accès non aléatoire est en général une opération inefficace (alors que, là encore, pour les itérateurs à accès aléatoire, elle est aussi efficace que la soustraction). C'est à vous de décider si votre algorithme est efficace ou non. c'est logique pour les itérateurs à accès non aléatoire, en termes d'efficacité. Si la perte d'efficacité qui en résulte est dévastatrice au point de rendre votre algorithme complètement inutile, alors vous devriez vous en tenir à la soustraction, interdisant ainsi les utilisations inefficaces et forçant l'utilisateur à chercher des solutions alternatives pour d'autres types d'itérateurs. Si l'efficacité des itérateurs à accès non aléatoire reste dans une fourchette utilisable, alors vous devriez utiliser distance et documenter le fait que l'algorithme fonctionne mieux avec des itérateurs à accès aléatoire.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
