c++ - vecteur vs liste dans la STL

88

Les Situations où vous souhaitez insérer un grand nombre d'éléments dans n'importe où, mais la fin d'une séquence à plusieurs reprises.

Découvrez la complexité des garanties pour chaque type de conteneur:

Ce sont la complexité des garanties de la norme des containers?
- L'insertion d'éléments en fin de compte, elle aussi, car elle peut conduire à l'allocation de la mémoire et de l'élément des frais de copie. Et aussi, l'insertion elenets au début d'un vecteur est à peu près impossible, list a push_front
- Non, l'insertion d'éléments à la fin d'un vecteur est amorti en temps constant. Les allocations de mémoire se produisent seulement sur l'occasion, et vous pouvez préallouer le vecteur pour l'en empêcher. Bien sûr, si vous DOIT ont garanti conforme à temps constant insertions, je suppose que c'est toujours un problème.
- Est le suivant "impossible" pour vous? v. insert(v. begin(), i)
- dans l'application que nous avons à insérer un grand nombre d'éléments dans le milieu d'une séquence à plusieurs reprises?
- Oui, il peut être commandé dans 20 caractères ou de quelque chose, mais là où elle mène? Selon l'application, il peut signifier une copie de tous les éléments à chaque fois. La facilité d'utilisation de fentes (entre la taille() et la capacité()) sont à la fin, pas au début.
- Je suis d'accord avec vous, c'est juste que je ne voulais pas que l'OP à penser que l'interface n'est pas là dans le cas où l'on veut se tirer dans le (performance) pied.
- Si la commande est en quelque sorte important, il pourrait être désiré, et vous savez le commander à l'avance. Toutefois, si vous insérez des données qui n'est pas ordonné, et pas près d'-commandé un arbre de recherche binaire est une meilleure solution que la structure elle-même maintient de la commande, il offre également beaucoup plus rapidement les recherches qu'un (lié) liste (tant que les cas mentionnés ci-dessus ne sont pas remplies.) Si les données insérées dans l'arbre est ordonné à ou près de l'a commandé plus ou moins dégénère en une liste, et rien n'est gagné. Qui peut être évité en utilisant un auto-équilibrage de l'arbre, mais ils sont plus compliqués.
- Et hashmaps, ils n'ont pas à maintenir l'ordre, mais ont généralement très rapide de recherche de temps (plus vite que les arbres binaires)
- Un traitement de texte.
- Pas nécessairement plus rapide que les techniciennes se chargent; la complexité algorithmique dans le formulaire de big-O notation est concerné avec des catégories plutôt que la vitesse réelle. Voir les différentes réponses/commentaires stackoverflow.com/questions/2196995/...
- Pate: Bon point, merci. Et si vous avez besoin d'écrire la structure-même je m'attendrais à un BST pour être plus simple de faire du droit.
- Bjarne Strostrup effectivement fait un test où il nombres aléatoires générés et puis ajoutés à une liste et un vecteur respectivement. Les insertions ont été faites pour que la liste/vecteur a été commandé à tout moment. Même si c'est généralement "liste de domaine" le vecteur a surclassé la liste par une marge importante. La raison étant que la mémoire d'accès est lent et la mise en cache fonctionne mieux pour les données séquentielles. Tout est disponible dans son discours de "GoingNative 2012"
InformationsquelleAutor Martin York
382

vecteur:
- De mémoire contiguë.
- Pré-alloue de l'espace pour les futurs éléments, de sorte que l'espace supplémentaire requis au-delà de ce qui est nécessaire pour les éléments eux-mêmes.
- Chaque élément nécessite seulement l'espace pour le type de l'élément lui-même (sans supplément de pointeurs).
- Pouvez ré-allouer de la mémoire pour l'ensemble de vecteur à chaque fois que vous ajoutez un élément.
- Insertions à la fin sont constants, amorti temps, mais les insertions d'ailleurs sont un coûteux en O(n).
- Ratures à la fin du vecteur sont des constantes de temps, mais pour le reste c'est de O(n).
- Vous pouvez accéder de manière aléatoire à l'un de ses éléments.
- Les itérateurs sont invalidés si vous ajoutez ou supprimez des éléments ou à partir du vecteur.
- Vous pouvez facilement obtenir à la sous-jacentes de tableau, si vous avez besoin d'un tableau des éléments.
liste:
- Non contigu de mémoire.
- Pas de pré-alloué de la mémoire. La charge de la mémoire pour la liste elle-même est constante.
- Chaque élément nécessite de l'espace supplémentaire pour le nœud qui détient l'élément, y compris les pointeurs vers le suivant et précédent éléments dans la liste.
- N'a jamais ré-allouer de la mémoire pour l'ensemble de la liste juste parce que vous ajoutez un élément.
- Des Insertions et des ratures sont pas cher n'importe où dans la liste qu'ils se produisent.
- C'est pas cher pour combiner des listes avec d'épissage.
- Vous ne pouvez pas accéder de manière aléatoire des éléments, ainsi pour en arriver à un élément particulier de la liste peut être coûteux.
- Itérateurs restent valables, même si 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 ajoutez-les tous, car il n'existe pas de tableau sous-jacent.
En général, l'utilisation de vecteur lorsque vous ne vous souciez pas de ce type de conteneur séquentiel que vous utilisez, mais si vous faites beaucoup d'insertions ou des ratures et ce, partout dans le conteneur autre que de la fin, vous allez avoir à utiliser la liste. Ou si vous avez besoin d'un accès aléatoire, alors vous allez vouloir vecteur, pas de liste. Autre que cela, il y a naturellement le cas où vous êtes va avoir besoin de l'un ou l'autre en fonction de votre application, mais en général, ce sont de bonnes lignes directrices.
- Aussi, l'allocation à partir du magasin libre n'est pas gratuit. 🙂 L'ajout de nouveaux éléments à un vecteur effectue en O(log n) libre allocations de magasin, mais vous pouvez l'appeler reserve() le ramener à O(1). L'ajout de nouveaux éléments à une liste (c'est à dire pas d'épissage de mer) effectue en O(n) libre allocations de magasin.
- Une autre considération est que list libère de la mémoire lors de l'effacement d'éléments, mais vector ne le fait pas. Un vector ne pas réduire sa capacité lorsque vous réduisez sa taille, sauf si vous utilisez le swap() truc.
- Je veux vraiment savoir votre tour dans la réserve (les) et le swap() 🙂
- si vous avez besoin d'ajouter des N éléments d'un vecteur, appelez v. réserve(v. size()+N), de sorte qu'il n'effectue qu'un magasin libre d'affectation. Le swap() astuce est ici: stackoverflow.com/questions/253157/how-to-downsize-stdvector
- Notes: vector avant-l'allocation: Ce peut consommer beaucoup de mémoire pour les grands vecteurs si vous ne connaissez pas la taille à l'avance et ne sont pas en mesure de reserve. // vector re-l'allocation: Cela peut être un cher pour les grands-ish objets (et de grands vecteurs).
- Je pense que vous voulez dire "non" et pas "si" dans le point n ° 2 de vecteur
- Pas de. Ce qu'il dit est correct. vecteur alloue de l'espace supplémentaire au-delà de l'espace pour les éléments actuellement dans le vecteur; que la capacité supplémentaire est ensuite utilisée pour pousser le vecteur de sorte que la culture il est amorti O(1).
- après c++11, vous pouvez appeler ‘std::vector::shrink_to_fit()’
InformationsquelleAutor Jonathan M Davis
30

Si vous n'avez pas besoin d'insérer des éléments souvent alors un vecteur le plus efficace. Il a beaucoup plus de cache du PROCESSEUR, de la localité de une liste. En d'autres termes, l'accès à un élément rend très probable que le prochain élément est présent dans le cache, et peut être récupéré sans avoir à lire lente RAM.

InformationsquelleAutor Hans Passant
28

Plus de réponses ici, en oubliez un détail important: pour quoi?

Que voulez-vous garder dans la containter?

Si c'est une collection de ints, puis std::list perdra dans tous les cas de figure, peu importe si vous pouvez réaffecter, vous ne retirez de l'avant, etc. Les listes sont plus lents à la traverse, chaque insertion frais vous une interaction avec l'allocateur. Il serait extrêmement difficile de préparer un exemple, où list<int> beats vector<int>. Et même alors, deque<int> peut-être mieux ou à proximité, ne pas justyfing l'utilisation de listes, ce qui aura une plus grande surcharge de la mémoire.

Toutefois, si vous êtes aux prises avec de gros, laid gouttes de données - et de quelques-uns d'entre eux - vous ne voulez pas overallocate lors de l'insertion, et de la copie en raison de la réallocation de la serait une catastrophe - alors vous pouvez peut-être être mieux avec une list<UglyBlob> que vector<UglyBlob>.

Encore, si vous passez à vector<UglyBlob*> ou même vector<shared_ptr<UglyBlob> >, nouveau - liste de retard.

Donc, motif de l'accès, de la cible de l'élément de comptage etc. affecte encore la comparaison, mais à mon avis, les éléments de la taille - le coût de la copie, etc.
- Une réflexion à laquelle j'ai eu lors de la lecture de "Effective STL" par Meyers: une propriété particulière de list<T> est la possibilité de splice dans O(1). Si vous avez besoin de la constante de temps de l'épissage, la liste peut également être la structure de choix 😉
- +1 - Il n'a même pas à être un UglyBlob - même des objets avec juste un peu de chaîne les membres peuvent facilement être d'un coût prohibitif pour copier, de sorte que les réaffectations est coût. Aussi: Ne négligez pas l'espace supplémentaire à la croissance exponentielle d'une vector tenant des objets de quelques dizaines d'octets la taille peut causer (si vous ne pouvez pas reserve à l'avance).
- Comme pour vector<smart_ptr<Large>> vs list<Large> -- je dirais, si vous avez besoin d'un accès aléatoire aux éléments, le vector de sens. Si vous n'avez pas besoin d'un accès aléatoire, la list semble plus simple et devrait effectuer aussi.
InformationsquelleAutor Tomasz Gandor
16

Une capacité de std::list est épissage (liaison ou le déplacement d'une partie ou toute une liste dans une autre liste).

Ou peut-être si votre contenu est très cher à copier. Dans un tel cas, il pourrait être moins cher, par exemple, pour trier la collection avec une liste.

Notez également que si la collection est petite (et le contenu ne sont pas particulièrement cher pour copier), un vecteur peut toujours mieux que une liste, même si vous insérer et effacer n'importe où. Une liste alloue à chaque nœud individuellement, et qui peut être beaucoup plus coûteux que le déménagement quelques objets simples autour.

Je ne pense pas qu'il y a de très dur règles. Cela dépend de ce que la plupart veulent faire avec le conteneur, ainsi que sur la façon dont grand vous attendez le conteneur et le contenu type. Un vecteur en général l'emporte sur une liste, car elle alloue à son contenu comme un seul bloc contigu (il est en fait un tableau alloué dynamiquement, et dans la plupart des cas d'un tableau est le moyen le plus efficace pour contenir un tas de choses).
- +1. L'épissage est plus à négliger, mais, malheureusement, n'est pas constante-temps comme il le souhaite. :(( (Il ne peut pas être si la liste::la taille est constante en temps.)
- Je suis tout à fait sûr de liste: la taille de l'est (permis de l'être) linéaire pour cette raison.
- n'est pas nécessairement constante de temps. Voir stackoverflow.com/questions/228908/is-listsize-really-on et gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
- Que la norme est plutôt vague, et que, par conséquent, vous ne pouvez pas compter sur la "conformité" des implémentations rend encore plus d'un problème. Vous avez littéralement à éviter la stdlib pour obtenir un portable fiable et garantie.
- oui, malheureusement. Mon projet actuel repose fortement sur l'épissage des opérations et que la structure est presque droites, C. Encore plus malheureusement, dans N3000 séquence splice entre les différentes listes est spécifié comme linéaire de la complexité et de size est spécifiquement constante. Donc, pour accueillir les novices qui itérer sur size ou que ce soit, toute une classe d'algorithmes est hors de portée pour la STL, ou "conforme" conteneurs de la période.
InformationsquelleAutor UncleBens
13

Bien les élèves de ma classe me semble tout à fait incapable de m'expliquer quand il est plus efficace d'utiliser des vecteurs, mais ils ont l'air tout à fait heureux quand me conseiller d'utiliser des listes.

C'est la façon dont je le comprends

Listes:
Chaque élément contient une adresse à l'autre ou de l'élément précédent, donc, avec cette fonctionnalité, vous pouvez générer aléatoirement des éléments, même si elles ne sont pas triées, l'ordre ne change pas: c'est efficace si vous la mémoire est fragmentée.
Mais il a aussi un autre très gros avantage: vous pouvez facilement insérer/supprimer des éléments, parce que la seule chose que vous devez faire est de changer certaines de pointeurs.
Inconvénient:
Pour lire de façon aléatoire un seul élément, vous devez sauter d'un point à un autre jusqu'à ce que vous trouver la bonne adresse.

Vecteurs:
Lors de l'utilisation de vecteurs, la mémoire est beaucoup plus organisés en rangées régulières: chaque n-ième éléments sont stockées juste après (n-1)ème élément et avant (n+1)ème élément.
Pourquoi est-il mieux que la liste ?
Parce que c'permettre à accès aléatoire rapide.
Voici comment: si vous connaissez la taille d'un élément dans un vecteur, et si elles sont contiguës en mémoire, vous pouvez facilement prédire où la n-ième élément est; vous n'avez pas à parcourir tous les éléments d'une liste à lire celui que vous voulez, avec un vecteur, directement à vous lire, avec une liste vous ne pouvez pas.
D'autre part, de modifier le tableau de vecteurs ou de modifier une valeur est beaucoup plus lente.

Listes sont plus appropriés pour garder la trace des objets qui peuvent être ajoutés/supprimés de la mémoire.
Les vecteurs sont plus appropriés lorsque vous souhaitez accéder à un élément d'une grande quantité d'articles simples.

Je ne sais pas comment sont les listes optimisé, mais vous devez savoir que si vous voulez l'accès en lecture rapide, vous devez utiliser des vecteurs, parce que la qualité de la STL fixer des listes, il n'est pas aussi rapide de l'accès en lecture de vecteur.
- "modifier le tableau de vecteurs ou de modifier une valeur est beaucoup plus lent" - comme lire, cela semble en contradiction avec ce que vous avez dit juste avant de le sujet vecteur d'être prédisposé pour un bon rendement en raison de leur faible niveau et contigus de la nature. avez-vous dire que réaffectation le vector causé par la modification de ses taille peut être lent? alors d'accord, mais dans les cas où reserve() peut être utilisé, qui évite ces problèmes.
InformationsquelleAutor jokoon
10

Fondamentalement, un vecteur est un tableau avec gestion automatique de la mémoire. Les données sont contigus en mémoire. Essayez d'insérer des données dans le milieu est une opération coûteuse.

Dans une liste les données sont stockées en indépendants des emplacements de mémoire. L'insertion dans le milieu n'est pas de la copie de certaines données pour faire de la place pour la nouvelle.

Pour répondre plus spécifiquement à votre question, je vais vous citer cette page

vecteurs sont généralement les plus efficaces dans le temps pour accéder à des éléments, et d'ajouter ou supprimer des éléments à partir de la fin de la séquence. Pour les opérations qui impliquent l'insertion ou la suppression d'éléments à des positions autres que de la fin, ils effectuent pire que deques et des listes, et ont de moins en moins cohérente les itérateurs et les références de listes.

InformationsquelleAutor f4.
9

Tout moment, vous ne pouvez pas avoir les itérateurs invalidé.
- Mais ne jamais sauter à la conclusion sur les itérateurs, sans nous demander si persistante références dans un deque suffirait.
InformationsquelleAutor dirkgently
8

Quand vous avez beaucoup d'insertion ou délétion dans le milieu de la séquence. par exemple, un gestionnaire de mémoire.
- donc, la différence entre eux est juste de l'efficacité, pas de la fonctionnelle de la question.
- Ils ont tous deux un modèle ordre des éléments de cours. Il y a une petite différence dans l'utilisation, comme indiqué par @dirkgently mais vous devez regarder à la complexité de votre "fait souvent" des opérations de décider qui séquence de choisir(@Martin réponse).
- Il y a quelques différences fonctionnelles. Par exemple, seul vecteur de la maladie prend en charge à accès aléatoire (c'est à dire, peut être indexé).
- l'efficacité se traduit par des performances. La mauvaise performance peut ruiner la fonctionnalité. La Performance est l'avantage du C++, après tout.
InformationsquelleAutor AraK
4

La préservation de la validité des itérateurs est l'une des raisons pour utiliser une liste. L'autre, c'est quand vous ne voulez pas un vecteur de réaffecter lors de la poussée des éléments. Cela peut être géré par une utilisation intelligente de la réserve(), mais dans certains cas, il peut être plus facile ou plus possible d'utiliser une liste.

InformationsquelleAutor John Dibling
4

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

Par exemple, un graphe de l'algorithme de partitionnement peut avoir un nombre constant d'objets de manière récursive divisé entre un nombre croissant de conteneurs. Les objets doivent être initialisés à la fois et de toujours rester au même endroit dans la mémoire. C'est beaucoup plus rapide pour les réorganiser en réassocier que par la réaffectation des.

Edit: que les bibliothèques se préparer à mettre en œuvre C++0x, le cas général de l'épissage une sous-suite dans une liste est de plus en complexité linéaire avec la longueur de la séquence. C'est parce que splice (maintenant) doit effectuer une itération sur la séquence de compter le nombre d'éléments. (Parce que la liste doit enregistrer sa taille.) Un simple comptage et le rétablissement du lien entre la liste est encore plus rapide que toute autre alternative, et l'épissage de l'ensemble d'une liste ou d'un seul élément sont des cas particuliers avec la constante de la complexité. Mais, si vous avez de longues séquences d'épissage, vous pourriez avoir à creuser autour pour une meilleure, à l'ancienne, non conforme conteneur.

InformationsquelleAutor Potatoswatter
2

La seule règle absolue où list doit être utilisé est de l'endroit où vous devez distribuer des pointeurs vers des éléments du conteneur.

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

(Techniquement, un vector de *_ptr également de travailler mais dans ce cas, vous êtes à l'émulation list donc, c'est juste de la sémantique.)

Autre soft règles ont trait aux problèmes de performance de l'insertion d'éléments dans le milieu d'un conteneur, après quoi list serait préférable.

InformationsquelleAutor iPherian
1

Les listes sont un wrapper pour un doublement LinkedList dans la stl, offrant ainsi des fonctionnalités que vous pouvez attendre de la part de d-linklist à savoir O(1) d'insertion et de suppression.
Alors que les vecteurs sont contagieux séquence de données qui fonctionne comme un tableau dynamique.P.S - plus facile à traverser.

InformationsquelleAutor Ritankar Paul
1

Faire simple-

À la fin de la journée quand vous êtes confus de choisir des contenants en C++, l'utilisation de ce diagramme de flux de l'image ( Dis merci pour moi ) :-
entrez la description de l'image ici

Vecteur-

1. vecteur est basé sur contagieux mémoire

2. vecteur est le chemin à parcourir pour petit ensemble de données

3. vecteur d'effectuer plus rapidement tout en se déplaçant sur le jeu de données

4. vecteur d'insertion suppression est lent sur le vaste ensemble de données, mais très rapide
petite

Liste-

1. la liste est basée sur un segment de mémoire

2. liste de chemin à faire pour un très vaste ensemble de données

3. la liste est relativement lent sur la traversée de petits jeux de données, mais rapide à
vaste ensemble de données

4. liste d'insertion suppression est rapide sur vaste ensemble de données, mais lente sur les petits
ceux

InformationsquelleAutor xyz xyz
0

Dans le cas d'un vecteur et liste, les principales différences qui se collent à moi sont les suivants:

vecteur
- Un vecteur stocke ses éléments dans la mémoire contiguë. Par conséquent, aléatoire
  l'accès 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 il suffit de multiplier le
  adresse de base avec l'index de l'élément pour accéder à cet élément. En fait, il
  ne prend que O(1) ou à temps constant à cet effet.
- Depuis un vecteur de coeur encapsule un tableau, chaque fois que vous insérez un
  élément dans le vecteur (tableau dynamique), il a pour redimensionner lui-même par
  trouver un nouveau bloc contigu de mémoire pour accueillir les nouveaux
  les éléments de ce qui est coûteux.
- Il ne consomme pas de mémoire supplémentaire pour stocker les pointeurs vers d'autres
  éléments à l'intérieur d'elle.
liste
- Une liste stocke ses éléments non contigus en mémoire. Par conséquent,
  accès aléatoire n'est pas possible à l'intérieur d'une liste, ce qui signifie que le
  d'accéder à ses éléments, nous devons utiliser les pointeurs et les traverse
  la liste qui est plus lent par rapport à un vecteur. Cela prend un temps O(n) ou un temps linéaire qui est
  plus lent que O(1).
- Depuis une liste des utilisations non contigu de mémoire, le temps pris pour insérer un
  élément à l'intérieur d'une liste est beaucoup plus efficace que dans le cas de son
  vecteur homologue parce que la redistribution de la mémoire est à éviter.
- 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 à l'esprit ces différences, nous avons l'habitude de considérer mémoire, fréquentes accès aléatoire et insertion pour décider du vainqueur de vecteur vs liste dans un scénario donné.

InformationsquelleAutor Ardent Coder

Vous devez vous connecter pour publier un commentaire.