vecteur vs liste en STL

239

J'ai remarqué dans Effective STL que

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

Qu'est-ce que cela signifie? Il semble qu'ignorer l'efficacité vectorpuisse tout faire.

Quelqu'un pourrait-il m'offrir un scénario qui vectorn'est pas une option réalisable mais listdoit être utilisé?

c++ list vector stl skydoor
la source
6
Bien que ce ne soit pas ce que vous avez demandé, il convient de souligner que la valeur par défaut de vector signifie également que vous pouvez facilement interagir avec du code plus ancien, des bibliothèques C ou des bibliothèques non-modèles, car vector est un wrapper fin autour du tableau dynamique "traditionnel" d'un pointeur. et la taille.
18
Bjarne Strostrup a en fait fait un test où il a généré des nombres aléatoires et les a ensuite ajoutés à une liste et un vecteur respectivement. Les insertions ont été faites de manière à ce que la liste / le vecteur soit ordonnée en tout temps. Même s'il s'agit généralement d'un "domaine de liste", le vecteur a surclassé la liste d'une LARGE marge. La raison en est que l'accès à la mémoire est lent et que la mise en cache fonctionne mieux pour les données séquentielles. Tout est disponible dans son discours de "GoingNative 2012"
évitant le
4
baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque
Adam Burry
1
Si vous voulez voir le discours de Bjarne Stroustrup mentionné par @evading, je l'ai trouvé ici: youtu.be/OB-bdWKwXsU?t=2672
brain56

Réponses:

98

Situations où vous souhaitez insérer de nombreux éléments n'importe où, mais à la fin d'une séquence à plusieurs reprises.

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

Quelles sont les garanties de complexité des conteneurs standards?

Martin York
la source
2
L'insertion d'éléments à la fin compte également car cela peut entraîner des coûts d'allocation de mémoire et de copie d'éléments. Et aussi, insérer des elenets au début d'un vecteur est presque impossible, listapush_front
Notinlist
9
Non, l'insertion d'éléments à la fin d'un vecteur est amortie en temps constant. Les allocations de mémoire ne se produisent qu'occasionnellement et vous pouvez préallouer le vecteur pour l'empêcher. Bien sûr, si vous DEVEZ avoir garanti des insertions constantes à temps constant, je suppose que c'est toujours un problème.
Brian
16
@Notinlist - Est-ce que ce qui suit est "presque impossible" pour vous? v.insert (v.begin (), i)
Manuel
5
@Notinlist - Je suis d'accord avec vous, c'est juste que je ne voulais pas que l'OP pense que l'interface n'est pas là au cas où l'on voudrait se tirer une balle dans le pied (de performance).
Manuel
16
Bjarne Strostrup a en fait fait un test où il a généré des nombres aléatoires et les a ensuite ajoutés à une liste et un vecteur respectivement. Les insertions ont été faites de manière à ce que la liste / le vecteur soit ordonnée en tout temps. Même s'il s'agit généralement d'un "domaine de liste", le vecteur a surclassé la liste d'une LARGE marge. La raison en est que l'accès à la mémoire est lent et que la mise en cache fonctionne mieux pour les données séquentielles. Tout est disponible dans son discours de "GoingNative 2012"
évitant le
410

vecteur:

  • Mémoire contiguë.
  • Pré-alloue l'espace pour les éléments futurs, donc un espace supplémentaire requis 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 le vecteur entier chaque fois que vous ajoutez un élément.
  • Les insertions à la fin sont constantes, à temps amorti, mais les insertions ailleurs sont un O (n) coûteux.
  • Les effacements à la fin du vecteur sont à temps constant, mais pour le reste c'est O (n).
  • Vous pouvez accéder au hasard à ses éléments.
  • Les itérateurs sont invalidés si vous ajoutez ou supprimez des éléments dans ou à partir du vecteur.
  • Vous pouvez facilement accéder au tableau sous-jacent si vous avez besoin d'un tableau des é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éallouer de la mémoire pour la liste entière simplement parce que vous ajoutez un élément.
  • Les insertions et les effacements sont bon marché, peu importe où dans la liste ils se produisent.
  • Il n'est pas cher de combiner des listes avec l'épissage.
  • Vous ne pouvez pas accéder de manière aléatoire aux éléments, donc accéder à un élément particulier de la liste peut être coûteux.
  • 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 ajouter tous, car il n'y a pas de tableau sous-jacent.

En général, utilisez vector lorsque vous ne vous souciez pas du type de conteneur séquentiel que vous utilisez, mais si vous effectuez de nombreuses insertions ou suppressions vers et depuis n'importe où dans le conteneur autre que la fin, vous allez vouloir pour utiliser la liste. Ou si vous avez besoin d'un accès aléatoire, alors 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 l'autre en fonction de votre application, mais en général, ce sont de bonnes lignes directrices.

Jonathan M Davis
la source
2
En outre, l'allocation à partir du magasin gratuit n'est pas gratuite. :) L'ajout de nouveaux éléments à un vecteur effectue des allocations de magasin gratuit O (log n), mais vous pouvez appeler reserve()pour le réduire à O (1). L'ajout de nouveaux éléments à une liste (c'est-à-dire leur non-épissage) permet d'effectuer O (n) allocations de magasin gratuit.
bk1e
7
Une autre considération est que cela listlibère de la mémoire lorsque vous effacez des éléments, mais ce vectorn'est pas le cas. A vectorne réduit pas sa capacité lorsque vous réduisez sa taille, sauf si vous utilisez l' swap()astuce.
bk1e
@ bk1e: Je veux vraiment connaître votre astuce dans reserve () et swap () :)
Dzung Nguyen
2
@nXqd: si vous devez ajouter N éléments à un vecteur, appelez v.reserve (v.size () + N) pour qu'il n'effectue qu'une seule allocation de banque gratuite. L'astuce swap () est ici: stackoverflow.com/questions/253157/how-to-downsize-stdvector
bk1e
1
@simplename No. Ce qu'il dit est correct. le vecteur alloue un espace supplémentaire au-delà de l'espace pour les éléments actuellement dans le vecteur; cette capacité supplémentaire est ensuite utilisée pour faire croître le vecteur de sorte que sa croissance soit amortie O (1).
Jonathan M Davis
35

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

Hans Passant
la source
32

La plupart des réponses ici manquent un détail important: pourquoi?

Que voulez-vous garder dans le conteneur?

S'il s'agit d'une collection de ints, alors std::listperdra dans chaque scénario, peu importe si vous pouvez réallouer, vous ne supprimez que par le devant, 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ù list<int>bat vector<int>. Et même dans ce cas, il deque<int>peut être préférable ou proche, et non pas simplement d'utiliser des listes, qui auront une surcharge de mémoire plus importante.

Cependant, si vous avez affaire à de gros et moches blobs de données - et peu d'entre eux - vous ne voulez pas surallouer lors de l'insertion, et la copie en raison de la réallocation serait un désastre - alors vous pourriez peut-être être mieux avec un list<UglyBlob>que vector<UglyBlob>.

Pourtant, si vous passez à vector<UglyBlob*>ou même vector<shared_ptr<UglyBlob> >, encore une fois - la liste sera en retard.

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

Tomasz Gandor
la source
1
Encore une réflexion, que j'ai eue en lisant "Effective STL" de Meyers: une propriété particulière de list<T>est la possibilité de splicedans O (1) . Si vous avez besoin d'épissage à temps constant, la liste peut également être la structure de choix;)
Tomasz Gandor
1 - Il n'a même pas besoin d' être UglyBlob- même un objet avec seulement quelques membres de la chaîne peuvent facilement être prohibitif de copier, de sorte que les réaffectations ne coûtera. Aussi: Ne négligez pas l'espace au-dessus de la croissance exponentielle d'un vectorobjet de taille de quelques dizaines d'octets (si vous ne pouvez pas reserveà l'avance).
Martin Ba
Quant à vector<smart_ptr<Large>>vs list<Large>- je dirais que si vous avez besoin d'un accès aléatoire aux éléments, cela a du vectorsens. Si vous n'avez pas besoin d'un accès aléatoire, le listsemble plus simple et devrait fonctionner de la même manière.
Martin Ba
19

Une capacité spéciale de std :: list est l'épissage (liaison ou déplacement d'une partie ou d'une liste entière dans une liste différente).

Ou peut-être si votre contenu coûte très cher à copier. Dans un tel cas, il pourrait être moins coûteux, par exemple, de trier 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 l'insérez et l'effacez n'importe où. Une liste alloue chaque nœud individuellement, et cela pourrait être beaucoup plus coûteux que de déplacer quelques objets simples.

Je ne pense pas qu'il existe des règles très strictes. 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 en un seul bloc contigu (il s'agit essentiellement d'un tableau alloué dynamiquement, et dans la plupart des cas, un tableau est le moyen le plus efficace de contenir un tas de choses).

UncleBens
la source
1
+1. L'épissage est trop négligé, mais n'est malheureusement pas à temps constant comme souhaité. : (((Cela ne peut pas être si list :: size est à temps constant.)
Je suis tout à fait sûr que list :: size est (autorisé à être) linéaire pour cette raison.
UncleBens
1
@Roger: list::sizen'est pas nécessairement un temps constant. Voir stackoverflow.com/questions/228908/is-listsize-really-on et gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
Potatoswatter
@Potatoswatter: Le fait que la norme soit vague et que vous ne pouvez donc pas compter sur des implémentations "conformes" en fait encore plus un problème. Vous devez littéralement éviter le stdlib pour obtenir une garantie portable et fiable.
@Roger: oui, malheureusement. Mon projet actuel repose fortement sur les opérations d'épissure et cette structure est presque droite C. Encore plus malheureusement, dans la séquence N3000 spliceentre différentes listes est spécifiée comme une complexité linéaire et sizeest spécifiquement constante. Ainsi, pour accommoder les novices qui itèrent sizeou quoi que ce soit, toute une classe d'algorithmes est hors de portée pour la STL, ou toute période de conteneurs «conforme».
Potatoswatter
13

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 ont l'air plutôt contents de me conseiller d'utiliser des listes.

Voilà comment je le comprends

Listes : Chaque élément contient une adresse vers l'élément suivant ou précédent, donc avec cette fonctionnalité, vous pouvez randomiser les éléments, même s'ils ne sont pas triés, l'ordre ne changera pas: c'est efficace si votre mémoire est fragmentée. Mais il a également un autre très gros avantage: vous pouvez facilement insérer / supprimer des éléments, car la seule chose que vous devez faire est de changer certains pointeurs. Inconvénient: pour lire un seul élément au hasard, vous devez passer 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 comme les tableaux ordinaires: chaque nième éléments est stocké juste après (n-1) e élément et avant (n + 1) e élément. Pourquoi est-ce mieux que la liste? Parce qu'il permet un accès aléatoire rapide. Voici comment: si vous connaissez la taille d'un élément dans un vecteur et s'ils sont contigus en mémoire, vous pouvez facilement prédire où se trouve le n-ième élément; vous n'avez pas à parcourir tous les éléments d'une liste pour lire celui que vous voulez, avec vector, vous le lisez directement, avec une liste que vous ne pouvez pas. En revanche, modifier le tableau vectoriel ou changer une valeur est beaucoup plus lent.

Les listes sont plus appropriées pour garder une trace des objets 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'articles uniques.

Je ne sais pas comment les listes sont optimisées, mais vous devez savoir que si vous voulez un accès rapide en lecture, vous devez utiliser des vecteurs, car à quel point les listes de fixation STL sont bonnes, l'accès en lecture ne sera pas aussi rapide que vector.

jokoon
la source
"modifier le tableau de vecteurs ou changer une valeur est beaucoup plus lent" - comme lu, cela semble contredire ce que vous avez dit juste à propos de la prédisposition des vecteurs à de bonnes performances en raison de leur faible niveau et de leur nature contiguë. vouliez-vous dire que la réaffectation du vectorcausé par le changement de sa taille peut être lente? alors convenu, mais dans les cas où il reserve()peut être utilisé, cela évite ces problèmes.
underscore_d
10

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 de mémoire non liés. L'insertion au milieu n'implique pas la copie de certaines données pour faire de la place pour la nouvelle.

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 ajouter ou supprimer des éléments à la fin de la séquence. Pour les opérations qui impliquent l'insertion ou la suppression d'éléments à des positions autres que la fin, elles fonctionnent moins bien que les deques et les listes, et ont des itérateurs et des références moins cohérents que les listes.

f4.
la source
9

Chaque fois que vous ne pouvez pas faire invalider les itérateurs.

dirkgently
la source
2
Mais ne sautez jamais à cette conclusion sur les itérateurs sans demander si des références persistantes dans un dequesuffiraient.
Potatoswatter
8

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

AraK
la source
donc la différence entre eux est juste l'efficacité, pas le problème fonctionnel.
skydoor
Bien entendu, ils modélisent tous deux une séquence d'éléments. Il y a une petite différence d'utilisation, comme mentionné par @dirkgently mais vous devez regarder la complexité de vos opérations "souvent effectuées" pour décider quelle séquence choisir (réponse @Martin).
AraK
@skydoor - Il existe quelques différences fonctionnelles. Par exemple, seul le vecteur prend en charge l'accès aléatoire (c'est-à-dire qu'il peut être indexé).
Manuel
2
@skydoor: l'efficacité se traduit par la performance. De mauvaises performances peuvent ruiner la fonctionnalité. Les performances sont l'avantage du C ++, après tout.
Potatoswatter
4

La préservation de la validité des itérateurs est l'une des raisons d'utiliser une liste. Un autre est lorsque vous ne voulez pas qu'un vecteur se réalloue lors de la poussée d'éléments. Cela peut être géré par une utilisation intelligente de reserve (), mais dans certains cas, il peut être plus facile ou plus pratique d'utiliser simplement une liste.

John Dibling
la source
4

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

Par exemple, un algorithme de partitionnement de graphe peut avoir un nombre constant d'objets répartis récursivement entre un nombre croissant de conteneurs. Les objets doivent être initialisés une fois et restent toujours aux mêmes emplacements en mémoire. Il est beaucoup plus rapide de les réorganiser en reconnectant qu'en réallouant.

Edit: à mesure que les bibliothèques se préparent à implémenter C ++ 0x, le cas général de l'épissure d'une sous-séquence en une liste devient de plus en plus complexe avec la longueur de la séquence. C'est parce que splice(maintenant) doit itérer sur la séquence pour compter le nombre d'éléments qu'elle contient. (Parce que la liste doit enregistrer sa taille.) Le simple comptage et la nouvelle liaison de la liste est encore plus rapide que n'importe quelle alternative, et l'épissage d'une liste entière ou d'un seul élément sont des cas spéciaux avec une complexité constante. Mais, si vous avez de longues séquences à épisser, vous devrez peut-être chercher un meilleur conteneur à l'ancienne et non conforme.

Potatoswatter
la source
2

La seule règle stricte où listdoit être utilisée est l'endroit où vous devez distribuer des pointeurs aux éléments du conteneur.

Contrairement à avec vector, vous savez que la mémoire des éléments ne sera pas réallouée. Si c'est le cas, vous pourriez avoir des pointeurs vers la mémoire inutilisée, ce qui est au mieux un grand non-non et au pire un SEGFAULT.

(Techniquement, un vectorde *_ptrfonctionnerait également, mais dans ce cas, vous émulez listdonc c'est juste de la sémantique.)

D'autres règles souples concernent les éventuels problèmes de performances liés à l'insertion d'éléments au milieu d'un conteneur, ce listqui serait préférable.

iPherian
la source
2

Rendez-le simple -
À la fin de la journée, lorsque vous ne savez pas choisir des conteneurs en C ++, utilisez cette image de l'organigramme (dites-moi merci): - entrez la description de l'image ici

Vecteur -
1. le vecteur est basé sur la mémoire contagieuse
2. le vecteur est le chemin à parcourir pour un petit ensemble de données
3. le vecteur est plus rapide lors de la traversée sur l'ensemble de données
4. la suppression d'insertion de vecteur est lente sur un énorme ensemble de données mais rapide pour les très petits

Liste -
1. La liste est basée sur la mémoire de tas
2. La liste est le chemin à parcourir pour un ensemble de données très volumineux
3. La liste est relativement lente pour parcourir un petit ensemble de données mais rapide pour un ensemble de données énorme
4. La suppression d'insertion de liste est rapide énorme ensemble de données mais lent sur les plus petits

xyz xyz
la source
1

Les listes ne sont qu'un encapsuleur pour une double liste de liens dans stl, offrant ainsi la fonctionnalité que vous pourriez attendre de d-linklist, à savoir l'insertion et la suppression de O (1). Alors que les vecteurs sont une séquence de données contagieuse qui fonctionne comme un tableau dynamique.PS- plus facile à parcourir.

Ritankar Paul
la source
0

Dans le cas d'un vecteur et d'une liste , les principales différences qui me viennent à l'esprit sont les suivantes:

vecteur

  • Un vecteur stocke ses éléments dans une mémoire contiguë. Par conséquent, l'accès aléatoire est possible à l'intérieur d'un vecteur, ce qui signifie que l'accès à un élément d'un vecteur est très rapide car nous pouvons simplement multiplier l'adresse de base par l'index de l'élément pour accéder à cet élément. En fait, cela ne prend que O (1) ou un temps constant à cet effet.

  • Puisqu'un vecteur enveloppe un tableau, chaque fois que vous insérez un élément dans le vecteur (tableau dynamique), il doit se redimensionner en trouvant un nouveau bloc de mémoire contigu pour accueillir les nouveaux éléments, ce qui est coûteux en temps.

  • Il ne consomme pas de mémoire supplémentaire pour stocker des pointeurs vers d'autres éléments qu'il contient.

liste

  • Une liste stocke ses éléments dans une mémoire non contiguë. Par conséquent, l'accès aléatoire n'est pas possible à l'intérieur d'une liste, ce qui signifie que pour accéder à ses éléments, nous devons utiliser les pointeurs et parcourir la liste qui est plus lente par rapport au vecteur. Cela prend O (n) ou un temps linéaire qui est plus lent que O (1).

  • Puisqu'une liste utilise de la mémoire non contiguë, le temps nécessaire pour insérer un élément à l'intérieur d'une liste est beaucoup plus efficace que dans le cas de son homologue vectoriel car la réallocation de la mémoire est évitée.

  • Il consomme de la mémoire supplémentaire pour stocker des pointeurs vers l'élément avant et après un élément particulier.

Donc, en gardant ces différences à l'esprit, nous considérons généralement la mémoire , les accès aléatoires fréquents et l' insertion pour décider du gagnant du vecteur par rapport à la liste dans un scénario donné.

Ardent Coder
la source
0

La liste est une liste double liée, il est donc facile d'insérer et de supprimer un élément. Nous devons simplement changer les quelques pointeurs, alors qu'en vecteur si nous voulons insérer un élément au milieu, chaque élément doit ensuite se déplacer d'un index. De plus, si la taille du vecteur est pleine, il doit d'abord augmenter sa taille. C'est donc une opération coûteuse. Ainsi, chaque fois que des opérations d'insertion et de suppression doivent être effectuées plus souvent dans une telle liste de cas, il convient d'utiliser.

Siddesh Pawar
la source