Pour une simple liste chaînée dans laquelle l'accès aléatoire aux éléments de la liste n'est pas une exigence, y a-t-il des avantages significatifs (performance ou autre) à utiliser la fonction std::list au lieu de std::vector ? Si une traversée en arrière est nécessaire, serait-il plus efficace d'utiliser std::slist et reverse() la liste avant d'itérer sur ses éléments ?
Réponses
Trop de publicités?
Comme d'habitude, la meilleure réponse aux questions de performance est de profil les deux implémentations pour votre cas d'utilisation et voyez laquelle est la plus rapide.
En général, si vous avez des insertions dans la structure de données (autres qu'à la fin), alors vector peut être plus lent, sinon dans la plupart des cas vector devrait être plus performant que list si seulement pour problèmes de localisation des données Cela signifie que si deux éléments adjacents dans l'ensemble de données sont adjacents dans la mémoire, l'élément suivant sera déjà dans le cache du processeur et n'aura pas à effectuer une faute de page de la mémoire vers le cache.
Gardez également à l'esprit que les frais généraux d'espace pour une vector est constant (3 pointeurs) alors que l'encombrement pour une list est payé pour chaque élément, cela réduit également le nombre d'éléments complets (données plus frais généraux) qui peuvent résider dans le cache à tout moment.
Sam
Points
733
La structure de données par défaut à laquelle il faut penser en C++ est le Vecteur .
Considérez les points suivants...
1] Traversée :
Les nœuds des listes sont éparpillés partout dans la mémoire et, par conséquent, la traversée des listes conduit à manques dans le cache . Mais le parcours des vecteurs est lisse.
2] Insertion et suppression :
En moyenne, 50% des éléments doivent être décalés lorsque vous faites cela à un Vecteur mais les caches sont très bons pour cela ! Mais, avec les listes, vous devez traverse au point d'insertion/suppression... donc encore une fois... le cache manque ! Et étonnamment les vecteurs gagnent ce cas aussi !
3] Stockage :
Lorsque vous utilisez des listes, il y a deux pointeurs par élément (en avant et en arrière), ce qui fait qu'une liste est beaucoup plus grande qu'un vecteur ! Les vecteurs nécessitent juste un peu plus de mémoire que les éléments réels.
Tout le monde devrait avoir une raison de ne pas utiliser un vecteur.
Référence :
J'ai appris cela lors d'une conférence de The Lord Bjarne Stroustrup...
http://www.youtube.com/watch?v=0iWb_qi2-uI
Votre réponse se trouve à 44:40 dans la vidéo...
gbjbaanb
Points
31045
Tout simplement non. La liste a des avantages par rapport au vecteur, mais l'accès séquentiel n'en fait pas partie - si c'est tout ce que vous faites, alors un vecteur est meilleur.
Cependant un vecteur est plus coûteux pour ajouter des éléments supplémentaires qu'une liste, surtout si vous insérez au milieu.
Comprenez comment ces collections sont mises en œuvre : un vecteur est un tableau séquentiel de données, une liste est un élément qui contient les données et des pointeurs vers les éléments suivants. Une fois que vous aurez compris cela, vous comprendrez pourquoi les listes sont bonnes pour les insertions et mauvaises pour les accès aléatoires.
(ainsi, l'itération inverse d'un vecteur est exactement la même que l'itération directe - l'itérateur soustrait simplement la taille des éléments de données à chaque fois, la liste doit toujours passer à l'élément suivant via le pointeur).
janm
Points
9310
Si vous avez besoin d'une traversée en arrière, il est peu probable qu'un slist soit la structure de données qu'il vous faut.
Une liste conventionnelle (doublement) chaînée vous donne un temps d'insertion et de suppression constant n'importe où dans la liste ; un vecteur ne donne un temps d'insertion et de suppression constant amorti qu'à la fin de la liste. Pour un vecteur, le temps d'insertion et de suppression est linéaire partout ailleurs qu'à la fin. Ce n'est pas tout, il y a aussi des facteurs constants. Un vecteur est une structure de données plus simple qui présente des avantages et des inconvénients en fonction du contexte.
La meilleure façon de comprendre cela est de comprendre comment ils sont mis en œuvre. Une liste chaînée possède un pointeur suivant et un pointeur précédent pour chaque élément. Un vecteur a un tableau d'éléments adressés par index. Vous pouvez ainsi constater que les deux types de listes peuvent effectuer un parcours efficace en avant et en arrière, alors que seul un vecteur peut fournir un accès aléatoire efficace. Vous pouvez également constater que la surcharge mémoire d'une liste liée est par élément, alors qu'elle est constante pour un vecteur. Et vous pouvez également voir pourquoi le temps d'insertion est différent entre les deux structures.
Loki Astari
Points
116129
Voir cette question pour plus de détails sur les coûts :
Quelles sont les garanties de complexité des conteneurs standard ?
Si vous avez une liste et que vous voulez maintenant la parcourir dans l'ordre inverse, pourquoi ne pas changer le type en liste partout ?
