Les listes consomment la majeure partie de leur temps en allouant de la mémoire lors de pushing_back. D'un autre côté, les vecteurs doivent copier leurs éléments lorsqu'un redimensionnement est nécessaire. Quel conteneur est donc le plus efficace pour stocker une liste d'adjacence?STL vector vs list: Le plus efficace pour les listes d'adjacence de graphes?
Je ne pense pas que cela puisse être répondu avec une certitude absolue. Néanmoins, j'estime qu'il y a au moins 90% de chances qu'un vecteur fasse mieux. Une liste d'adjacence a tendance à favoriser un vecteur plus que de nombreuses applications, car l'ordre des éléments dans la liste d'adjacence n'a pas (normalement) d'importance. Cela signifie que lorsque vous ajoutez des éléments, c'est normalement à la fin du conteneur, et lorsque vous supprimez un élément, vous pouvez d'abord l'échanger à la fin du conteneur, vous n'aurez donc qu'à l'ajouter ou à le supprimer à la fin.
Oui, un vecteur doit copier des éléments quand il se dilate, mais en réalité ce n'est presque jamais une préoccupation substantielle. En particulier, le taux d'expansion exponentiel d'un vecteur signifie que le nombre moyen d'éléments copiés tend vers une constante - et dans une implémentation typique, cette constante est d'environ 3.
Si vous êtes dans une situation où la copie est honnêtement un vrai problème (par exemple, la copie des éléments est extrêmement coûteux), mon prochain choix après le vecteur ne serait toujours pas la liste. Au lieu de cela, je envisagerais probablement d'utiliser std :: deque à la place. C'est fondamentalement un vecteur de pointeurs vers des blocs d'objets. Il a rarement besoin de copier quoi que ce soit pour faire une expansion, et dans les rares occasions où cela se produit, tout ce qu'il a à copier, ce sont les pointeurs, pas les objets. Sauf si vous avez besoin des autres capacités uniques d'un deque (insérer/supprimer en temps constant à chaque extrémité), un vecteur est généralement un meilleur choix, mais même si une deque est presque toujours un meilleur choix qu'une liste (ie, le vecteur est généralement le premier choix, deque une seconde assez proche, et liste un dernier lointain).
La réponse dépend du cas d'utilisation. P.S. @quasiverse - les vecteurs appellent realloc lorsque la mémoire que vous ":: réserve", implicitement ou explicitement, est épuisée
Si vous avez une liste d'adjacence qui change constamment (insertions et suppressions), une liste serait la meilleure. Si vous avez une liste d'adjacence plus ou moins statique, et que vous faites la plupart du temps des parcours/recherches, alors un vecteur vous donnera les meilleures performances.
Les conteneurs STL ne sont pas définis de manière rigide, les implémentations varient donc. Si vous faites attention, vous pouvez écrire votre code pour qu'il ne se soucie pas de savoir si c'est un vecteur ou une liste qui est utilisée, et vous pouvez simplement les essayer pour voir lequel est le plus rapide. Compte tenu de la complexité des effets de cache, etc., il est presque impossible de prédire les vitesses relatives avec précision.
Vous pouvez ajouter une troisième option à cette comparaison: liste avec allocateur spécialisé.
L'utilisation d'allocateurs pour les petits objets de taille fixe peut augmenter considérablement la vitesse d'allocation/désallocation ...
Qui a dit que les vecteurs effectuaient une copie? – quasiverse
@quasiverse: les exigences sur 'vector' nécessitent essentiellement une copie à mesure qu'elle grandit. les 'vecteurs' sont requis pour stocker leurs éléments de manière contiguë. Au fur et à mesure que vous ajoutez des éléments, vous finirez par utiliser l'espace alloué, et lors de l'ajout suivant vous obtiendrez une nouvelle allocation de mémoire suivie d'une copie des éléments en cours dans le nouvel espace, suivie d'une désallocation de l'ancien espace . –