Pourquoi préférerais-je utiliser le vecteur pour déque

86

Depuis

  1. ce sont tous les deux des conteneurs de mémoire contigus;
  2. du point de vue de la fonctionnalité, deque a presque tout ce que le vecteur a mais plus, car il est plus efficace de l'insérer à l'avant.

Pourquoi quelqu'un whould préfère std::vectorà std::deque?

Léon
la source
2
L'implémentation Visual C ++ de std::dequea une très petite taille de bloc maximale (~ 16 octets, si je me souviens bien; peut-être 32), et en tant que telle, elle ne fonctionne pas très bien pour les applications réalistes. Un deque<T>where sizeof(T) > 8(ou 16? C'est un petit nombre) a à peu près les mêmes caractéristiques de performances que a vector<T*>, où chaque élément est alloué dynamiquement. D'autres implémentations ont des tailles de bloc maximales différentes, il est donc difficile d'écrire du code qui a relativement les mêmes caractéristiques de performances sur différentes plates-formes deque.
James McNellis
12
Deque n'est pas un conteneur de mémoire continue.
Mohamed El-Nakib
@ravil Non, c'est le double, pointant cette question.
1
difficile de croire qu'une question avec une erreur factuelle flagrante non résolue était assise à un équilibre de 34 voix
underscore_d
2
@underscore_d c'est pourquoi c'est une question. Histoire différente si c'était une réponse;)
Assimilater

Réponses:

115

Les éléments de a nedeque sont pas contigus en mémoire; vectorles éléments sont garantis. Donc, si vous avez besoin d'interagir avec une bibliothèque C simple qui a besoin de tableaux contigus, ou si vous vous souciez (beaucoup) de la localité spatiale, alors vous préférerez peut-être vector. De plus, étant donné qu'il y a une comptabilité supplémentaire, d'autres opérations sont probablement (légèrement) plus chères que leurs vectoropérations équivalentes . D'un autre côté, l'utilisation de nombreuses / grandes instances de vectorpeut entraîner une fragmentation inutile du tas (ralentissant les appels à new).

De plus, comme indiqué ailleurs sur StackOverflow , il y a d'autres bonnes discussions ici: http://www.gotw.ca/gotw/054.htm .

phooji
la source
3
Il semble que le lien vers «ailleurs» soit désormais mort (faute de modération?).
esilk
37

Pour connaître la différence, il faut savoir comment dequeest généralement mis en œuvre. La mémoire est allouée en blocs de tailles égales, et ils sont enchaînés (sous forme de tableau ou éventuellement de vecteur).

Donc, pour trouver le nième élément, vous trouvez le bloc approprié puis accédez à l'élément qu'il contient. C'est un temps constant, car il s'agit toujours exactement de 2 recherches, mais c'est encore plus que le vecteur.

vectorfonctionne également bien avec les API qui veulent un tampon contigu, car elles sont soit des API C ou sont plus polyvalentes en pouvant prendre un pointeur et une longueur. (Ainsi vous pouvez avoir un vecteur en dessous ou un tableau régulier et appeler l'API depuis votre bloc mémoire).

dequea ses plus grands avantages sont:

  1. Lors de l'agrandissement ou de la réduction de la collection de chaque extrémité
  2. Lorsque vous avez affaire à de très grandes tailles de collection.
  3. Lorsque vous traitez avec des booléens et vous voulez vraiment des booléens plutôt qu'un ensemble de bits.

Le second d'entre eux est moins connu, mais pour de très grandes tailles de collection:

  1. Le coût de la réaffectation est élevé
  2. La surcharge de devoir trouver un bloc de mémoire contigu est restrictive, vous pouvez donc manquer de mémoire plus rapidement.

Lorsque je travaillais avec de grandes collections dans le passé et que je passais d'un modèle contigu à un modèle de bloc, nous pouvions stocker environ 5 fois plus grande collection avant de manquer de mémoire dans un système 32 bits. Ceci est en partie dû au fait que, lors de la réallocation, il devait en fait stocker l'ancien bloc ainsi que le nouveau avant de copier les éléments.

Cela dit, vous pouvez avoir des problèmes avec std::dequeles systèmes qui utilisent une allocation de mémoire «optimiste». Alors que ses tentatives de demander une grande taille de tampon pour une réallocation de a vectorseront probablement rejetées à un moment donné avec a bad_alloc, la nature optimiste de l'allocateur est susceptible de toujours accorder la demande pour le plus petit tampon demandé par a dequeet qui est susceptible de provoquer le système d'exploitation pour tuer un processus pour essayer d'acquérir de la mémoire. Celui qu'il choisit n'est peut-être pas trop agréable.

Les solutions de contournement dans un tel cas sont soit de définir des indicateurs au niveau du système pour remplacer l'allocation optimiste (pas toujours faisable), soit de gérer la mémoire un peu plus manuellement, par exemple en utilisant votre propre allocateur qui vérifie l'utilisation de la mémoire ou similaire. Évidemment pas idéal. (Ce qui peut répondre à votre question de préférer le vecteur ...)

Vache à lait
la source
29

J'ai implémenté à la fois vector et deque plusieurs fois. deque est beaucoup plus compliqué du point de vue de la mise en œuvre. Cette complication se traduit par plus de code et un code plus complexe. Ainsi, vous verrez généralement une taille de code frappée lorsque vous choisissez deque sur vecteur. Vous pouvez également rencontrer un petit coup de vitesse si votre code utilise uniquement les choses dans lesquelles le vecteur excelle (c'est-à-dire push_back).

Si vous avez besoin d'une file d'attente double, deque est clairement le gagnant. Mais si vous faites la plupart de vos insertions et effacements à l'arrière, le vecteur sera clairement le gagnant. En cas de doute, déclarez votre conteneur avec un typedef (il est donc facile de basculer d'avant en arrière) et mesurez.

Howard Hinnant
la source
3
Question - Le comité a-t-il envisagé d'ajouter un hybride des deux (disons, un «deck») au C ++? (c'est-à-dire un double vector.) J'ai écrit une implémentation liée à ci-dessous dans ma réponse . Cela peut être aussi rapide qu'un, vectormais beaucoup plus largement applicable (par exemple, lors de la création d'une file d'attente rapide).
user541686
5

std::dequen'a pas de mémoire continue garantie - et c'est souvent un peu plus lent pour l'accès indexé. Un deque est généralement implémenté sous la forme d'une "liste de vecteurs".

Erik
la source
14
Je ne pense pas qu'une "liste de vecteurs" soit correcte: je crois comprendre que la plupart des implémentations étaient un "vecteur de pointeurs vers des tableaux", bien que cela dépende de votre définition de "liste" (j'ai lu "liste" comme "liste liée" , "qui ne répondrait pas aux exigences de complexité.)
James McNellis
2

Selon http://www.cplusplus.com/reference/stl/deque/ , "contrairement aux vecteurs, les deques ne sont pas garantis d'avoir tous ses éléments dans des emplacements de stockage contigus, éliminant ainsi la possibilité d'un accès sécurisé grâce à l'arithmétique des pointeurs."

Les Deques sont un peu plus compliqués, en partie parce qu'ils n'ont pas nécessairement une disposition de mémoire contiguë. Si vous avez besoin de cette fonctionnalité, vous ne devez pas utiliser de fichier deque.

(Auparavant, ma réponse évoquait un manque de standardisation (de la même source que ci-dessus, «les deques peuvent être implémentées par des bibliothèques spécifiques de différentes manières»), mais cela s'applique en fait à n'importe quel type de données de bibliothèque standard.)

patrickvacek
la source
5
std::dequen'est pas moins standardisé que std::vector. Je ne pense pas que les exigences en matière de complexité std::dequepuissent être satisfaites avec un stockage contigu.
Jerry Coffin
1
Ma formulation était peut-être médiocre: bien qu'il soit vrai que la standardisation n'est pas complète, si je comprends bien, les vecteurs sont normalisés pour être une séquence conitugous, et les deques ne le sont pas. Cela semble être le seul facteur décisif.
patrickvacek
1
@JerryCoffin: Quelles exigences de complexité de dequene peuvent pas satisfaire avec le stockage contigu?
user541686
1
@Mehrdad: Pour être honnête, je ne me souviens pas de ce que j'avais en tête. Je n'ai pas examiné cette partie de la norme assez récemment pour me sentir à l'aise d'affirmer catégoriquement que mon commentaire précédent était erroné, mais en le regardant maintenant, je ne vois pas non plus comment ce serait juste.
Jerry Coffin
3
@JerryCoffin: Les exigences de complexité sont en fait insignifiantes: vous pouvez allouer un grand tableau et commencer à pousser votre séquence du milieu vers l'extérieur (je suppose que c'est ce que fait l'implémentation de Mehrdad), puis réallouer lorsque vous arrivez aux extrémités. Le problème avec cette approche est qu'elle ne satisfait pas à l'une des exigences de deque, à savoir que l'insertion aux extrémités ne doit pas invalider les références aux éléments existants. Cette exigence implique une mémoire discontinue.
Yakov Galka
0

Un deque est un conteneur de séquence qui permet un accès aléatoire à ses éléments, mais il n'est pas garanti d'avoir un stockage contigu.

Sean
la source
0

Je pense que c'est une bonne idée de faire un test de performance de chaque cas. Et prenez une décision en vous basant sur ces tests.

Je préfère std::dequeque std::vectordans la plupart des cas.

George Gaál
la source
1
La question, s'il y en a une qui peut être distillée parmi les erreurs factuelles et les mots manquants, était de savoir pourquoi quelqu'un préférerait vector. On peut en déduire que pourquoi pas est un corollaire. Dire que vous préférez deque, pour des raisons inconnues, des tests non spécifiés, n'est pas une réponse.
underscore_d
0

Vous ne préférerez pas le vecteur à deque selon ces résultats de test (avec source).

Bien sûr, vous devez tester dans votre application / environnement, mais en résumé:

  • push_back est fondamentalement le même pour tous
  • insérer, effacer dans deque sont beaucoup plus rapides que la liste et légèrement plus rapides que le vecteur

Quelques réflexions supplémentaires, et une note à prendre en compte circular_buffer.

Nick Westgate
la source
0

D'une part, le vecteur est assez souvent plus rapide que deque. Si vous n'avez pas réellement besoin de toutes les fonctionnalités de deque, utilisez un vecteur.

D'autre part, parfois vous faites des caractéristiques des besoins vecteur qui ne vous donne pas, dans ce cas , vous devez utiliser un deque. Par exemple, je mets quiconque au défi d'essayer de réécrire ce code , sans utiliser de deque, et sans modifier énormément l'algorithme.

BenGoldberg
la source
En fait, sur la même série d' opérations push_backet pop_back, deque<int>c'est toujours au moins 20% plus rapide que vector<int>dans mes tests (gcc avec O3). Je suppose que c'est pourquoi dequele choix standard pour des choses comme std::stack...
igel
-1

Notez que la mémoire vectorielle est réaffectée au fur et à mesure que le tableau grandit. Si vous avez des pointeurs vers des éléments vectoriels, ils deviendront invalides.

De plus, si vous effacez un élément, les itérateurs deviennent invalides (mais pas "for (auto ...)").

Edit: changé 'deque' en 'vector'

Pierre
la source
-1: l'insertion et l'effacement au début ou à la fin n'invalident PAS les références et les pointeurs vers d'autres éléments. (Bien que l'insertion et l'effacement au milieu le fassent)
Sjoerd
@Sjoerd Je l'ai changé en «vecteur».
Pierre