Les listes consomment la plupart de leur temps dans l'allocation de la mémoire lors de la poussée. D'autre part, 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?
5 Réponses :
La réponse dépend de l'utilisation de l'utilisation. P.s. @Quasiverse - Les vecteurs appellent Realloc lorsque la mémoire que vous ": réserve", implicitement ou explicitement, épuise
Si vous avez une liste d'adjacence en constante évolution (insertions et suppression), une liste serait la meilleure. Si vous avez une liste d'adjacents plus ou moins statique et que vous faites la plupart du temps, des traversiers / recherches, un vecteur vous donnerait la meilleure performance.
Les conteneurs STL ne sont pas définis de manière rigide, les implémentations varient donc. Si vous êtes prudent, vous pouvez écrire votre code afin qu'il ne se soucie pas de savoir s'il s'agit d'un vecteur ou d'une liste utilisée, et vous pouvez simplement les essayer de voir ce qui est plus rapide. Compte tenu de la complexité des effets de cache, etc., il est presque impossible de prédire les vitesses relatives à toute précision.
Je ne pense pas que cela puisse être répondu avec une certitude absolue. Néanmoins, j'aurais d'estimer qu'il y a au moins 90% de chances qu'un vecteur va mieux. Une liste d'adjacence a réellement tendance à favoriser un vecteur plus que de nombreuses applications, car l'ordre des éléments de la liste des adjacents ne présente pas (normalement). Cela signifie que lorsque vous ajoutez des éléments, il est normalement à la fin du conteneur et lorsque vous supprimez un élément, vous pouvez l'échanger à la fin du conteneur, de sorte que vous ne puissiez jamais ajouter ou supprimer à la fin.
Oui, un vecteur doit copier des éléments lorsqu'il s'agrandit, mais en réalité, cela n'est presque jamais une préoccupation substantielle. En particulier, le taux d'expansion exponentielle d'un vecteur signifie que le nombre moyen d'éléments de fois est copié a tendance à atteindre une constante - et dans une implémentation typique, cette constante est d'environ 3.
Si vous êtes dans une situation où la copie est un véritable problème (par exemple, des éléments de copie sont extrêmement chers), mon prochain choix après le vecteur ne serait toujours pas une liste. Au lieu de cela, j'envisagerais probablement d'utiliser STD :: Deque à la place. C'est fondamentalement un vecteur de pointeurs à bloquer des objets. Il doit rarement à copier quoi que ce soit pour faire une expansion et une occasion rare que cela doit copier, ce sont les indicateurs, pas les objets. Sauf si vous avez besoin d'autres capacités uniques d'une dentelle (insérer / supprimer en temps constant à l'une ou l'autre extrémité), un vecteur est généralement un meilleur choix, mais même une deque est presque toujours un meilleur choix qu'une liste (c'est-à-dire que le vecteur est généralement Le premier choix, deque une seconde assez proche et énumérez une dernière distante).
Vous pouvez ajouter une troisième option à cette comparaison: Liste avec un allocator spécialisé.
Utilisation d'allocateurs pour de petits objets de taille fixe peut augmenter considérablement la vitesse d'allocation / distribution ...
Ce site de tutoriel recommande d'utiliser une matrice de listes ou je suppose que vous pouvez utiliser un vecteur d'éléments de liste à la place: Array de listes Liste Adj
@Quasivers: les exigences sur
vecteur nécessitent essentiellement une copie telle qu'elle grandit.Vecteur S doit stocker leurs éléments contiguës. Lorsque vous ajoutez des éléments, vous allez éventuellement utiliser l'espace alloué et, sur l'addition suivante, vous obtiendrez une nouvelle allocation de mémoire suivie d'une copie des éléments actuels dans le nouvel espace, suivi d'une distribution de l'espace ancien. .