Mettre en cache l’iterator final – Bonne idée ou mauvaise idée?

Dans le cas simple d’un vector , l’iterator end changera lorsque vous ajoutez ou supprimez des éléments du conteneur; Cependant, il est généralement plus prudent de supposer que si vous modifiez le conteneur tout en l’itérant, tous les iterators du conteneur deviennent invalides. Les iterators peuvent être implémentés différemment dans une implémentation STL donnée.

En ce qui concerne la mise en cache de l’iterator end – il est certes valide de le mettre en cache, mais pour savoir s’il est réellement plus rapide dans votre cas, le mieux est de profiler votre code et de le visualiser. Bien que l’extraction de l’iterator end partir d’un vector soit probablement une implémentation rapide avec une bibliothèque et un compilateur STL récents, j’ai déjà travaillé sur des projets antérieurs où la mise en cache de l’iterator end nous a considérablement accéléré. (C’était sur la PlayStation 2, alors prenez avec un grain de sel.)

Si nous parlons d’efficacité et de rapidité: la mise en cache de l’iterator final n’est pas nécessaire en raison des optimisations du compilateur et de l’intégration.

L’effacement d’un conteneur sur lequel vous effectuez une itération est toujours une mauvaise idée. La mise en cache réelle de votre iterator final ne va pas changer cela.

h.

De manière générale, est-ce une bonne idée de mettre en cache un iterator final (en particulier des conteneurs STL) à des fins d’efficacité et de rapidité?

Si vous utilisez les algorithmes de conteneur STL, la mise en cache de l’iterator final est néanmoins effectuée (lorsque vous transmettez le résultat de container.end () en tant que paramètre).

Si vous modifiez la mémoire du conteneur (insérer / supprimer des éléments), c’est une mauvaise idée.

Aussi, la mise en cache pour l’efficacité a rarement du sens: dans la plupart des cas, la fin () est insérée par le compilateur, et dans le cas contraire, il est très probable que votre efficacité ne dépende pas du résultat final () mis en cache. YMMV cependant.

Les règles d’invalidation (pour les iterators) sont définies très explicitement pour chaque type de conteneur. Je trouve le site SGI très utile http://www.sgi.com/tech/stl/table_of_contents.html

En particulier pour les vecteurs, je trouve:

[5] Les iterators d’un vecteur sont invalidés lorsque sa mémoire est réaffectée. De plus, l’insertion ou la suppression d’un élément au milieu d’un vecteur invalide tous les iterators qui pointent sur des éléments après le point d’insertion ou de suppression. Il s’ensuit que vous pouvez empêcher l’invalidation des iterators d’un vecteur si vous utilisez reserve () pour préallouer autant de mémoire que le vecteur n’utilisera jamais, et si toutes les insertions et les suppressions se trouvent à la fin du vecteur.

J’utilise souvent ce style pour les conteneurs itératifs:

 // typedef std::vector Persons; Persons::iterator it = persons.begin(), end = persons.end(); for (; it != end; ++it) { Person & person = *it; // ... } 

Effacer un élément d’un vecteur invalide tous les iterators après la position effacée.

Je ne suis pas certain des autres types de conteneurs. Dans tous les cas, je pense qu’il serait prudent de supposer que tous les iterators deviennent invalides après un effacement. Si vous avez vraiment besoin d’informations très spécifiques, vous pouvez toujours les consulter. J’ai rarement besoin de cela à cause de mon style de codage plutôt conservateur.

En général, cela ne devrait pas avoir d’importance si vous mettez en cache l’iterator final. Si vous pensez que cela a de l’importance, vous devriez déjà utiliser un profileur dans votre code et pouvoir profiler les deux variantes. J’imagine que cela pourrait varier en fonction du type de conteneur – mais un profileur serait le seul moyen de savoir avec certitude compte tenu de votre compilateur, de vos optimisations et de votre fournisseur STL.