vecteur vs liste en STL

Situations dans lesquelles vous souhaitez insérer de nombreux éléments partout ailleurs que la fin d’une séquence.

Découvrez les garanties de complexité pour chaque type de conteneur:

Quelles sont les garanties de complexité des conteneurs standard?

vecteur:

• Mémoire contiguë
• Pré-alloue de l’espace pour les éléments futurs, donc plus d’espace nécessaire au-delà de ce qui est nécessaire pour les éléments eux-mêmes.
• Chaque élément nécessite uniquement l’espace pour le type d’élément lui-même (pas de pointeurs supplémentaires).
• Peut ré-allouer de la mémoire pour tout le vecteur chaque fois que vous ajoutez un élément.
• Les insertions à la fin sont des durées d’amortissement constantes, mais les insertions ailleurs constituent un coût O (n) coûteux.
• Les effacements à la fin du vecteur sont des temps constants, mais pour le rest, c’est O (n).
• Vous pouvez accéder de manière aléatoire à ses éléments.
• Les iterators sont invalidés si vous ajoutez ou supprimez des éléments du 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 contient l’élément, y compris les pointeurs vers les éléments suivants et précédents de la liste.
• Vous n’avez jamais à réaffecter de la mémoire pour toute la liste simplement parce que vous ajoutez un élément.
• Les insertions et les effacements sont bon marché, peu importe où ils se trouvent dans la liste.
• Il est bon marché de combiner des listes avec des épissures.
• Vous ne pouvez pas accéder aléatoirement à des éléments, donc obtenir un élément particulier dans la liste peut coûter cher.
• Les iterators restnt valides même lorsque vous ajoutez ou supprimez des éléments de la liste.
• Si vous avez besoin d’un tableau d’éléments, vous devrez en créer un nouveau et les append tous, car il n’y a pas de tableau sous-jacent.

En général, utilisez vector quand vous ne vous souciez pas du type de conteneur séquentiel que vous utilisez, mais si vous effectuez de nombreuses insertions ou effacements de n’importe où dans le conteneur autre que la fin, vous allez vouloir utiliser la liste. Ou si vous avez besoin d’un access aléatoire, vous allez vouloir un vecteur, pas une liste. En dehors de cela, il y a naturellement des cas où vous allez avoir besoin de l’un ou de l’autre en fonction de votre application, mais en général, ce sont de bonnes directives.

Si vous n’avez pas besoin d’insérer des éléments souvent, un vecteur sera plus efficace. Il a une meilleure localisation de cache de processeur qu’une liste. En d’autres termes, l’access à un élément rend très probable la présence de l’élément suivant dans le cache et peut être récupéré sans avoir à lire une mémoire vive lente.

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

Que voulez-vous garder dans le contenant?

Si c’est une collection de int , alors std::list perd dans tous les scénarios, peu importe si vous pouvez réaffecter, vous ne supprimez que de l’avant, 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, où la list bat le vector . Et même alors, deque peut être meilleur ou proche, sans se contenter d’utiliser des listes, ce qui entraînera une surcharge de mémoire plus importante.

Cependant, si vous avez affaire à de gros tas de données laides – et peu d’entre elles – vous ne souhaitez pas les transférer lors de l’insertion et que la copie suite à une réallocation serait un désastre – alors vous pouvez peut-être être mieux avec une list que le vector .

Cependant, si vous passez au vector ou même au vector > , à nouveau, la liste sera en retard.

Ainsi, le modèle d’access, le nombre d’éléments cibles, etc. affectent toujours la comparaison, mais à mon avis – la taille des éléments – le coût de la copie, etc.

Une des fonctions spéciales de std :: list est le raccordement (lier ou déplacer une partie ou une liste entière dans une liste différente).

Ou peut-être si votre contenu est très coûteux à copier. Dans un tel cas, il peut être moins coûteux, par exemple, de sortinger la collection avec 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 surpasser une liste, même si vous insérez et effacez n’importe où. Une liste atsortingbue chaque nœud individuellement, ce qui peut coûter beaucoup plus cher que de déplacer quelques objects simples.

Je ne pense pas qu’il y ait des règles très ssortingctes. Cela dépend de ce que vous voulez principalement faire avec le conteneur, ainsi que de la taille que vous attendez du conteneur et du type contenu. Un vecteur l’emporte généralement sur une liste, car il alloue son contenu sous la forme d’un bloc contigu unique (il s’agit essentiellement d’un tableau alloué dynamicment et, dans la plupart des cas, un tableau est le moyen le plus efficace de contenir un tas de choses).

Eh bien, les élèves de ma classe semblent tout à fait incapables de m’expliquer quand il est plus efficace d’utiliser des vecteurs, mais ils semblent très heureux lorsqu’ils me conseillent d’utiliser des listes.

Voici comment je le comprends

Listes : chaque élément contient une adresse à l’élément suivant ou précédent. Avec cette fonctionnalité, vous pouvez randomiser les éléments, même s’ils ne sont pas sortingés, l’ordre ne changera pas: c’est efficace si votre mémoire est fragmentée. Mais il a aussi un autre avantage très important: vous pouvez facilement insérer / supprimer des éléments, car la seule chose à faire est de changer certains pointeurs. Inconvénient: pour lire un élément unique au hasard, vous devez sauter d’un élément à un autre jusqu’à ce que vous trouviez la bonne adresse.

Vecteurs : Lorsque vous utilisez des vecteurs, la mémoire est beaucoup plus organisée que les tableaux classiques: chaque n-ème élément est stocké juste après (n-1) e élément et avant (n + 1) ème élément. Pourquoi est-ce préférable à la liste? Parce qu’il permet un access aléatoire rapide. Voici comment: si vous connaissez la taille d’un élément dans un vecteur et si ces éléments sont contigus en mémoire, vous pouvez facilement prédire où se trouve le n-ième élément; vous n’avez pas besoin de parcourir tout l’élément d’une liste pour lire celui que vous voulez, avec vector, vous le lisez directement, avec une liste impossible. En revanche, modifier le tableau vectoriel ou modifier une valeur est beaucoup plus lent.

Les listes sont plus appropriées pour suivre les objects qui peuvent être ajoutés / supprimés en mémoire. Les vecteurs sont plus appropriés lorsque vous souhaitez accéder à un élément à partir d’une grande quantité d’éléments uniques.

Je ne sais pas comment les listes sont optimisées, mais vous devez savoir que si vous voulez un access en lecture rapide, vous devriez utiliser des vecteurs, car la qualité de la liste dépend de la qualité de lecture.

Chaque fois que vous ne pouvez pas invalider les iterators.

Fondamentalement, un vecteur est un tableau avec gestion automatique de la mémoire. Les données sont contiguës en mémoire. Essayer d’insérer des données au milieu est une opération coûteuse.

Dans une liste, les données sont stockées dans des emplacements mémoire indépendants. L’insertion au milieu n’implique pas de copier certaines des données pour faire place au nouveau.

Pour répondre plus précisément à votre question, je citerai cette page

Les vecteurs sont généralement les plus efficaces dans le temps pour accéder aux éléments et pour append ou supprimer des éléments à la fin de la séquence. Pour les opérations impliquant l’insertion ou la suppression d’éléments à des positions autres que la fin, elles sont moins performantes que les deques et les listes et ont des iterators et des références moins cohérents que les listes.

Lorsque vous avez beaucoup d’insertion ou de suppression au milieu de la séquence. par exemple un gestionnaire de mémoire.

Préserver la validité des iterators est une raison d’utiliser une liste. Une autre est lorsque vous ne voulez pas qu’un vecteur soit réaffecté lorsque vous poussez des éléments. Cela peut être géré par une utilisation intelligente de reserve (), mais dans certains cas, il peut être plus facile ou plus simple d’utiliser une liste.

Lorsque vous souhaitez déplacer des objects entre des conteneurs, vous pouvez utiliser list::splice .

Par exemple, un algorithme de partitionnement de graphe peut avoir un nombre constant d’objects divisés récursivement entre un nombre croissant de conteneurs. Les objects doivent être initialisés une fois et restr toujours aux mêmes endroits en mémoire. Il est beaucoup plus rapide de les réorganiser en les reliant qu’en les réaffectant.

Edit: à mesure que les bibliothèques se préparent à implémenter C ++ 0x, le cas général de l’épissage d’une sous-séquence dans une liste devient une complexité linéaire avec la longueur de la séquence. En effet, splice (maintenant) doit parcourir la séquence pour compter le nombre d’éléments qu’il contient. (Parce que la liste doit enregistrer sa taille.) Le simple fait de compter et de lier à nouveau la liste est toujours plus rapide que n’importe quelle alternative, et épisser une liste entière ou un seul élément est un cas particulier avec une complexité constante. Toutefois, si vous avez de longues séquences à épisser, vous devrez peut-être chercher un conteneur plus ancien, non conforme.

La seule règle ssortingcte où la list doit être utilisée est celle où vous devez dissortingbuer des pointeurs vers les éléments du conteneur.

Contrairement à vector , vous savez que la mémoire des éléments ne sera pas réallouée. Si cela peut être alors vous pourriez avoir des pointeurs vers de la mémoire inutilisée, ce qui est au mieux un grand no-no et au pire un SEGFAULT .

(Techniquement, un vector de *_ptr fonctionnerait aussi, mais dans ce cas, vous émulez la list , ce n’est que de la sémantique.)

D’autres règles souples ont trait aux problèmes de performances possibles liés à l’insertion d’éléments au milieu d’un conteneur, après quoi la list serait préférable.