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

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?

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 .

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).

Où 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 ...)

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.

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".

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.)

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.

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.

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.

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.

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'