Vecteur et liste en STL

Question

J'ai remarqué dans Effective STL que

Le vecteur est le type de séquence qui devrait être utilisé par défaut.

Qu'est-ce que ça veut dire ? Il semble qu'ignorer l'efficacité vector peut faire n'importe quoi.

Quelqu'un pourrait-il me proposer un scénario où vector n'est pas une option réalisable mais list doit être utilisé ?

Answer 1

vecteur :

• Mémoire contiguë.
• Pré-affectation d'espace pour les éléments futurs, donc espace supplémentaire requis au-delà de ce qui est nécessaire pour les éléments eux-mêmes.
• Chaque élément ne requiert que l'espace nécessaire pour le type d'élément lui-même (pas de pointeurs supplémentaires).
• Peut réallouer la mémoire pour le vecteur entier chaque fois que vous ajoutez un élément.
• Les insertions à la fin sont constantes, en temps amorti, mais les insertions ailleurs sont coûteuses O(n).
• Les effacements à la fin du vecteur sont en temps constant, mais pour le reste c'est O(n).
• Vous pouvez accéder à ses éléments de manière aléatoire.
• Les itérateurs sont invalidés si vous ajoutez ou retirez des éléments au vecteur.
• Vous pouvez facilement accéder au tableau sous-jacent si vous avez besoin d'un tableau d'éléments.

liste :

• Mémoire non contiguë.
• Pas de mémoire pré-allouée. La surcharge de mémoire pour la liste elle-même est constante.
• Chaque élément nécessite un espace supplémentaire pour le nœud qui le contient, y compris les pointeurs vers les éléments suivants et précédents de la liste.
• Il n'est jamais nécessaire de réallouer de la mémoire pour toute la liste juste parce que vous ajoutez un élément.
• Les insertions et les effacements sont peu coûteux, quel que soit l'endroit de la liste où ils se produisent.
• Il est bon marché de combiner des listes avec des épissures.
• Il n'est pas possible d'accéder aux éléments de manière aléatoire, de sorte que l'obtention d'un élément particulier de la liste peut être coûteuse.
• Les itérateurs restent valides même lorsque vous ajoutez ou supprimez des éléments de la liste.
• Si vous avez besoin d'un tableau des éléments, vous devrez en créer un nouveau et les y ajouter tous, puisqu'il n'y a pas de tableau sous-jacent.

En général, utilisez vectoriel quand vous ne vous souciez pas du type de conteneur séquentiel que vous utilisez, mais si vous faites beaucoup d'insertions ou d'effacements vers et depuis n'importe quel endroit du conteneur autre que la fin, vous voudrez utiliser liste. Ou si vous avez besoin d'un accès aléatoire, alors vous voudrez un vecteur, pas une liste. En dehors de cela, il y a naturellement des cas où vous aurez besoin de l'un ou l'autre en fonction de votre application, mais en général, ce sont de bonnes directives.

Answer 2

Situations dans lesquelles vous souhaitez insérer un grand nombre d'éléments n'importe où, sauf à la fin d'une séquence, de manière répétée.

Vérifiez les garanties de complexité pour chaque type de conteneur :

Quelles sont les garanties de complexité des conteneurs standard ?

Answer 3

Si vous n'avez pas besoin d'insérer des éléments souvent, un vecteur sera plus efficace. La localisation du cache du CPU est bien meilleure que celle d'une liste. En d'autres termes, l'accès à un élément le rend très Il est probable que l'élément suivant soit présent dans le cache et puisse être récupéré sans avoir à lire la RAM lente.

Answer 4

La plupart des réponses omettent un détail important : pour quoi faire ?

Que voulez-vous garder dans le conteneur ?

S'il s'agit d'une collection de int s, alors std::list perdront dans tous les scénarios, peu importe que vous puissiez réaffecter, que vous ne retiriez que du front, etc. Les listes sont plus lentes à parcourir, chaque insertion vous coûte une interaction avec l'allocateur. Il serait extrêmement difficile de préparer un exemple dans lequel list<int> battements vector<int> . Et même là, deque<int> peut être meilleure ou proche, sans se contenter de l'utilisation de listes, qui auront une plus grande surcharge de mémoire.

Cependant, si vous avez affaire à des données volumineuses et peu nombreuses, que vous ne voulez pas surallouer lors de l'insertion, et que la copie due à la réallocation serait un désastre, alors il est peut-être préférable d'utiliser une méthode d'allocation de données. list<UglyBlob> que vector<UglyBlob> .

Pourtant, si vous passez à vector<UglyBlob*> ou même vector<shared_ptr<UglyBlob> > Encore une fois, la liste sera à la traîne.

Ainsi, le modèle d'accès, le nombre d'éléments cibles, etc. influencent toujours la comparaison, mais à mon avis, la taille des éléments, le coût de la copie, etc.

Answer 5

Une capacité spéciale de std::list est l'épissage (lier ou déplacer une partie ou la totalité d'une liste dans une autre liste).

Ou peut-être si vos contenus sont très chers à copier. Dans ce cas, il peut être plus économique, par exemple, de trier la collection à l'aide d'une liste.

Notez également que si la collection est petite (et que le contenu n'est pas particulièrement coûteux à copier), un vecteur peut toujours être plus performant qu'une liste, même si vous insérez et effacez n'importe où. Une liste alloue chaque nœud individuellement, ce qui peut être beaucoup plus coûteux que de déplacer quelques objets simples.

Je ne pense pas qu'il y ait de règles très strictes. Cela dépend de ce que vous voulez faire avec le conteneur, ainsi que de la taille du conteneur et du type de contenu. Un vecteur est généralement supérieur à une liste, parce qu'il alloue son contenu sous la forme d'un seul bloc contigu (il s'agit en fait d'un tableau alloué dynamiquement, et dans la plupart des cas, un tableau est le moyen le plus efficace de contenir un ensemble de choses).