Itérateurs C++ et optimisation des boucles

Question

Je vois beaucoup de code c++ qui ressemble à ça :

for( const_iterator it = list.begin(),
     const_iterator ite = list.end();
     it != ite; ++it)

Par opposition à la version plus concise :

for( const_iterator it = list.begin();
     it != list.end(); ++it)

Y aura-t-il une différence de vitesse entre ces deux conventions ? Naïvement, la première sera légèrement plus rapide puisque list.end() n'est appelé qu'une seule fois. Mais puisque l'itérateur est const, il semble que le compilateur retirera ce test de la boucle, générant un assemblage équivalent pour les deux.

Answer 1

Les deux versions ne sont cependant pas les mêmes. Dans la deuxième version, il compare l'itérateur à list.end() à chaque fois, et ce list.end() évalue à pourrait changer au cours de la boucle. Maintenant, bien sûr, vous ne pouvez pas modifier list par l'intermédiaire du const_iterator it ; mais rien n'empêche le code à l'intérieur de la boucle de simplement appeler les méthodes sur list directement et la modifier, ce qui pourrait (selon le type de structure de données) list est) changer l'itérateur de fin. Il pourrait donc être incorrect, dans certaines circonstances, de stocker l'itérateur de fin au préalable, car il pourrait ne plus être l'itérateur de fin correct au moment où vous l'atteignez.

Answer 2

Je mentionnerai juste pour mémoire que la norme C++ impose que l'appel begin() y end() sur tout le type de conteneur (que ce soit vector , list , map etc.) ne doit prendre qu'un temps constant . En pratique, ces appels seront presque certainement inlined à une comparaison de pointeur unique si vous compilez avec les optimisations activées.

Notez que cette garantie n'est pas nécessairement valable pour les "conteneurs" supplémentaires fournis par les fournisseurs qui ne respectent pas les exigences formelles d'un conteneur définies dans le chapitre 23 de la norme (par exemple, la liste à lien unique slist ).

Answer 3

Le premier sera probablement presque toujours plus rapide, mais si vous pensez que cela fera une différence, toujours profil premier pour voir lequel est le plus rapide et de combien.

Le compilateur sera probablement capable de mettre en ligne l'appel à end() dans les deux cas, bien que si end() est suffisamment compliqué, il peut choisir de ne pas l'intégrer. Cependant, la clé de l'optimisation est de savoir si le compilateur peut ou non exécuter mouvement de code invariant en boucle . Je dirais que dans la plupart des cas, le compilateur ne peut pas être certain que la valeur de l'option end() ne changera pas pendant l'itération de la boucle, auquel cas il n'a pas d'autre choix que d'appeler end() après chaque itération.

Answer 4

Je choisirais l'option la plus concise et la plus lisible. N'essayez pas de deviner le compilateur et les optimisations qu'il pourrait effectuer. N'oubliez pas que la grande majorité de votre code n'aura absolument aucun effet sur les performances globales. Ce n'est que si cette section de code est critique en termes de performances que vous devez prendre le temps de la profiler et de choisir une représentation source efficace.

En référence spécifique à votre exemple, la première version fait un copie de la end() l'itérateur, en invoquant le code qui s'exécute pour le constructeur de copie de l'objet itérateur. Les conteneurs STL contiennent généralement des end() Le compilateur a donc tout le loisir d'optimiser la deuxième version, même si vous n'essayez pas de l'aider. Laquelle est la meilleure ? Mesurez-les.

Answer 5

Vous pouvez rendre la première version plus concise et obtenir le meilleur des deux :

for( const_iterator it = list.begin(), ite = list.end();
     it != ite; ++it)

P.S. Les itérateurs ne sont pas const, ce sont des itérateurs vers une référence const. Il y a une grande différence.