Des Conteneurs STL - différence entre le vecteur de la liste et deque

Dois-je utiliser deque au lieu de vecteur si j'aimerais pousser éléments au début du conteneur? Quand devrais-je utiliser la liste et à quoi sert-elle?

InformationsquelleAutor fex | 2012-03-10
  1. 14

    Utilisation deque si vous avez besoin d'efficace d'insertion/retrait au début et à la fin de la séquence et de l'accès aléatoire; l'utilisation list si vous avez besoin d'efficace d'insertion n'importe où, au prix du sacrifice de l'accès aléatoire. Les itérateurs et les références à list éléments sont très stables dans presque n'importe mutation du récipient, tandis que deque a très particulière itérateur de référence et d'invalidation des règles (donc vérifier soigneusement).

    Aussi, list est un nœud conteneur, tandis qu'un deque utilise des morceaux de mémoire contiguë, de sorte localité de mémoire peuvent avoir des effets sur les performances qui ne peuvent pas être capturées par la complexité asymptotique des estimations.

    deque peut servir comme un remplacement pour vector presque partout et doit probablement été considéré comme le "par défaut" conteneur en C++ (en raison de sa plus souple que les exigences de mémoire); la seule raison de préférer vector, c'est quand vous devez disposer d'une garantie de mémoire contiguë de mise en page de votre séquence.

    • vector presque toujours plus performante que la deque, dans mon expérience.
    • cela dépend du cas d'utilisation, et le profilage est vraiment la seule réponse. Un vecteur peut-être la lutte si vous voulez attribuer une vaste gamme, tandis que le deque peut attribuer de nouveaux morceaux sans déplacer les anciens. Et bien sûr, cela dépend de ce que vous faites.
    • Pourriez-vous donner quelques données de profilage ici. Qui sera très évident dans la détermination de la performance.
    • Ce n'est pas une très bonne réponse. Alors que "deque" est en principe une bonne idée, il y a beaucoup de mauvaises implémentations de là que l'utilisation d'un trop petit morceau de la taille et de ce fait se transformer en listes chaînées. Si vous aurez certainement besoin de comparer et de profil; std::vector souvent de meilleures performances, même pour les insertions d'autres qu'à la fin pour beaucoup de "typique" de la taille des contenants.
    InformationsquelleAutor Kerrek SB
  2. 12

    deque et vector fournir un accès aléatoire, list fournit seulement linéaire accède. Donc, si vous devez être en mesure de faire conteneur[i], que les règles list. D'autre part, vous pouvez insérer et supprimer des éléments n'importe où dans un list efficacement, et de l'exploitation dans le milieu de vector et deque sont lents.

    deque et vector sont très similaires, et sont fondamentalement interchangeables pour la plupart des besoins. Il y a seulement deux différences dignes de mention. Tout d'abord, vector ne peut efficacement ajouter de nouveaux éléments à la fin, alors que deque pouvez ajouter des éléments à chaque extrémité de manière efficace. Alors pourquoi voudriez-vous jamais utiliser un vector alors? Contrairement à deque, vector garantir que tous les éléments seront stockés dans la mémoire contiguë endroits, ce qui rend une itération à travers plus rapidement dans certaines situations.

    • Pourriez-vous donner quelques données de profilage ici. Qui sera très évident dans la détermination de la performance.
    InformationsquelleAutor deong