Quand faut-il utiliser le vecteur / la liste?

17

Je peux comprendre quand utiliser des listes, mais je ne comprends pas quand il vaut mieux utiliser des vecteurs que d'utiliser des listes dans les jeux vidéo: quand est-il préférable d'avoir un accès aléatoire rapide?

(Et je comprends pourquoi il est plus rapide d'insérer / supprimer dans les listes car il supprime / ajoute simplement des pointeurs, mais il doit toujours trouver l'élément correspondant ...)

c++ algorithm data-structure jokoon
la source
Ajout d'une balise vectorielle à cela - si la liste est une balise valide, alors le vecteur l'est aussi.
Kylotan
Vraisemblablement, le vecteur a été supprimé car il est utilisé pour désigner le vecteur mathématique, pas std :: vector.
1
que diriez-vous de les nix tous les deux et de les mettre container.
deft_code
@Kylotan: C'est comme Joe l'a dit. Cette question concernait certainement les vecteurs, mais elle n'appartenait pas à la balise vector.
doppelgreener
1
Supprimons-nous donc toute balise ambiguë? Cela me semble être une mauvaise décision - mieux vaut que votre recherche révèle trop d'informations que pas assez. Il est plus facile de sauter des résultats indésirables que de réfléchir pour trouver des synonymes.
Kylotan

Réponses:

29

Ma règle d'or, et je suis sûr qu'il y aura un débat à ce sujet, est de ne jamais utiliser de listes (sauf si vous devez supprimer très, très fréquemment des choses du milieu de grandes listes).

La vitesse que vous gagnerez en ayant tous vos éléments dans votre conteneur dans une mémoire contiguë (et donc plus compatible avec le cache) vaut la compensation des coûts supplémentaires d'ajout / suppression / redimensionnement du vecteur.

Edit: Juste pour clarifier un peu plus, bien sûr, il va sans dire que toute sorte de question "qui est plus rapide" devrait être testée sur n'importe quelle plate-forme avec tous les ensembles de données correspondant à vos besoins particuliers. Si j'ai juste besoin d'une collection d'éléments, j'utilise simplement vector (ou deque, ce qui est presque la même chose) à moins qu'il n'y ait une bonne raison de ne pas le faire.

Tetrad
la source
1
Je pense que cela dépend fortement de vos besoins, si vous n'avez jamais besoin d'accéder à un élément spécifique et qu'il vous suffit de les lire tous et que vous ajoutez et supprimez des éléments fréquemment, la liste est une meilleure solution.
Frédérick Imbeault
11
@ Frédérick: C'est la sagesse C ++ standard, mais c'est aussi presque toujours faux. Les vecteurs, en particulier lorsqu'il s'agit de vecteurs de pointeurs (que vous utilisez presque toujours pour les jeux), sont extrêmement rapides pour supprimer des éléments du milieu - c'est du temps linéaire, mais c'est un très petit surcoût par élément. Il est également beaucoup plus rapide d'itérer de manière séquentielle sur un vecteur.
1
Je ne sais pas exactement à quel type de structure vous vous adressez - ce type d'optimisation nécessite des exemples concrets pour dire quoi que ce soit de manière définitive. Par exemple, ma première réaction à votre cas d'utilisation serait un ensemble non ordonné, qui permet une insertion, une suppression et une recherche tout aussi rapides; dans mon expérience, les ensembles sont parfaits pour les objets dans les éditeurs. Mais comme les éditeurs ont des exigences de performances en temps réel beaucoup plus laxistes - par exemple, c'est bien si répondre à une pression sur le bouton "Supprimer" prend 1 / 20e de seconde ou prend 1 / 2ème de seconde 10% du temps - ce niveau d'optimisation s'applique également rarement à eux.
1
@ Frédérick Imbeault Modifié n'est pas vraiment un problème, c'est Add \ Remove qui pose problème. Du point d'ajout \ supprimé à la fin du vecteur est copié pour garder le vecteur contigu. Si l'ordre des éléments n'a pas d'importance, vous pouvez échanger l'élément supprimé avec le dernier élément, puis pop celui pour supprimer et ajouter à la fin pour ajouter.
stonemetal
4
Bien sûr, prendre l'adresse d'un élément dans un vecteur et la stocker n'est pas sûr. Mais en règle générale, vous ne faites pratiquement jamais cela, préférant plutôt avoir un vecteur de pointeurs d'éléments et copier le pointeur (ou quelque chose de similaire).
Tetrad
8

Utilisez une liste lorsque l'invalidation de l'itérateur causée par la modification du milieu de votre structure de données va causer un problème, ou si vous devez conserver vos éléments triés afin que le swap et le pop pop pour les suppressions rapides de la collection du milieu ne fonctionnent pas et que vous ayez un grand nombre de suppressions de milieu de collection.

Vous pouvez également envisager d'utiliser un Deque. Il a des caractéristiques de performances similaires à un vecteur mais n'a pas besoin de mémoire contiguë pour le vecteur et est un peu plus flexible.

stonemetal
la source
+1 pour être la seule personne à mentionner deques - vous bénéficiez de la mémoire contiguë et des avantages de vitesse de recherche des vecteurs, avec une insertion / suppression rapide aux deux extrémités.
5

Votre choix doit refléter vos besoins. Tous les éléments des vecteurs sont continus en mémoire et les listes ont des pointeurs vers les éléments suivants / précédents afin qu'ils aient chacun leurs avantages / désavantages:

Listes :

  • Chaque élément prend 2 entiers pour pointer les éléments précédents et suivants, donc le plus souvent, cela fait 8 octets de plus pour chaque élément de votre liste
  • L'insertion est linéaire dans le temps: O (n)
  • Supprimer est une opération constante: O (1)
  • L'accès à l'élément x est linéaire dans le temps: O (n)

Vecteurs:

  • Nécessite moins de mémoire (pas de pointeurs vers d'autres éléments, c'est un simple algorithme mathématique)
  • La suppression est linéaire dans le temps: O (n)
  • L'accès à l'élément x est constant: O (1) (C'est parce que les éléments sont continus en mémoire donc c'est une opération mathématique simple vectorPtr + (x * bytesOfTheType))
  • L'insertion peut être en temps linéaire, mais le plus souvent, c'est une opération constante: O (1) (C'est parce que le vecteur dans un tableau mais réserve toujours 2 fois sa capacité lorsque le tableau est plein, donc la copie du tableau n'est pas fréquente)

La liste est donc meilleure lorsque votre programme doit ajouter et supprimer des éléments fréquemment, mais jamais accéder (ou rarement accéder) à un élément particulier sans avoir besoin des autres auparavant. Le vecteur doit être utilisé pour un meilleur temps d'accès, mais manque d'efficacité lorsque vous devez supprimer ou ajouter des éléments.

Consultez cet article sur stackoverflow, il présente un très joli graphique avec des questions de base sur vos besoins qui vous conduit à un conteneur spécifique en fonction de vos réponses:

/programming/366432/extending-stdlist

Frédérick Imbeault
la source
3
Ce graphique doit vraiment commencer par un nœud "Stockez-vous des pointeurs et moins de mille? Non -> vecteur".
Oui peut-être que vous avez raison, je n'ai pas considéré le type stocké, il faut également l'analyser.
Frédérick Imbeault
2

Habituellement, les listes sont utilisées pour les structures comme les files d'attente où il y a beaucoup d'opérations d'ajout et de suppression. Exemple: une liste d'entités en constante évolution qui doit être mise à jour. La liste elle-même ne contient que des entités à l'écran et change donc fréquemment.

Les vecteurs (ou tableaux) sont mieux adaptés à une collection qui ne change pas beaucoup et où vous avez besoin d'un accès rapide aux éléments individuels de la collection. Exemple: une tuile-carte où vous devez rechercher des tuiles à un index donné.

L'opinion de Tetrads est peut-être vraie, mais elle dépend du langage de programmation utilisé. Je vois que vous avez marqué votre question c++, mais j'ai essayé de donner une réponse qui n'est pas spécifique à la langue.

bummzack
la source
Eh bien, j'aurais peut-être aussi mis C, mais il n'y a pas de tels conteneurs en C, mais c'est quelque chose à penser: y a-t-il une bibliothèque de type STL pour C?
jokoon
J'ai utilisé glib ( library.gnome.org/devel/glib ) dans le passé, qui implémente un certain nombre de structures de données standard pour C. Je le détestais parce qu'il est généralement trop verbeux et veut désespérément être C ++, mais il est mature et stable.
0

Dans les jeux sur console, nous n'utilisons jamais std :: list car:

  1. il fait des allocations de mémoire chaque fois que vous ajoutez un nouvel élément. les allocations de mémoire sont lentes.
  2. c'est plein de pointeurs. les pointeurs sont mauvais. un pointeur est un cache raté. une erreur de cache est mauvaise.

même std :: vector perd la faveur des consoles car:

  1. vous vous souciez souvent uniquement, par exemple, de la position de tous les objets. comme par exemple, vous voulez entrer en collision les objets les uns avec les autres, auquel cas vous ne vous souciez pas de leur couleur. vous voulez donc que toutes les positions soient contiguës en mémoire et vous voulez que les couleurs soient ailleurs loin, pour éviter de polluer le cache. mais std :: vector vous oblige à tout stocker pour chaque objet dans un morceau de mémoire contigu (par exemple position puis couleur.) donc si vous travaillez qui ne lit que les positions, vous devez également lire toutes les couleurs dans le cache, même si vous ne les utilisez pas. c'est du gaspillage.
bmcnett
la source
5
@bmcnett "[] .. mais std :: vector vous oblige à tout stocker pour chaque objet dans un morceau de mémoire contigu" - ce n'est pas une question de conteneur, c'est une question de disposition des données, vous pouvez avoir toutes les positions dans un morceau de mémoire continu avec un std :: vector:struct point{float x, y, z, w}; std::vector<point> positions;
Maik Semder
mon école va adorer ça :)
jokoon
2
-1 parce que cette réponse n'ajoute rien à la discussion liste vs vecteur déjà ici, et son affirmation sur le vecteur polluant le cache est fausse, comme le dit Maik.
vous avez mal compris ma demande. je n'ai jamais dit que parmi tous les conteneurs std :: vector est particulièrement coupable de polluer le cache. tous les conteneurs, et en fait même les tableaux, sont à peu près également coupables de cela. std :: vector tombe en disgrâce car les objets C ++ eux - mêmes tombent en disgrâce. C ++ exige que les données de chaque objet soient contiguës en mémoire. vous pouvez contourner cela en évitant les objets C ++, par exemple en utilisant std :: vector <position> comme mentionné ci-dessus.
bmcnett
3
Except pointest un objet C ++ (tel quel std::vector, comme c'est quelque chose d'aussi simple que float). Je connais la distinction que vous essayez de faire, mais vous expliquez mal.