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

Les éléments d’une deque ne sont pas contigus en mémoire; vector éléments vector sont garantis. Donc, si vous avez besoin d’interagir avec une bibliothèque C ordinaire qui nécessite des tableaux contigus, ou si vous vous souciez beaucoup de la localisation spatiale, vous préférerez peut-être le vector . De plus, comme il existe une comptabilité supplémentaire, les autres opérations sont probablement (légèrement) plus chères que leurs opérations vector équivalentes. D’un autre côté, l’utilisation de plusieurs / grandes instances de vector peut entraîner une fragmentation inutile du tas (ralentissement des appels vers de new ).

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

Pour connaître la différence, il faut savoir comment deque est généralement mis en œuvre. La mémoire est allouée en blocs de tailles égales et ils sont chaînés ensemble (en tant que tableau ou éventuellement 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 y a toujours exactement 2 recherches, mais c’est encore plus que le vecteur.

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

Où deque a ses plus grands avantages sont:

1. Lors de la croissance ou de la réduction de la collection des deux côtés
2. Lorsque vous avez affaire à de très grandes tailles de collection.
3. Lorsque vous avez affaire à des bools et que vous voulez vraiment des bools plutôt que des bitset.

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

1. Le coût de la réaffectation est important
2. La surcharge liée à la recherche d’un bloc de mémoire contigu est ressortingctive. Vous pouvez donc manquer de mémoire plus rapidement.

Lorsque je traitais de grandes collections par le passé et que je passais d’un modèle contigu à un modèle de bloc, nous avons pu stocker environ 5 fois plus de collection avant de manquer de mémoire dans un système 32 bits. C’est en partie parce que, lors de la réallocation, il était nécessaire de stocker l’ancien bloc ainsi que le nouveau avant de copier les éléments.

Cela dit, vous pouvez avoir des problèmes avec std::deque sur des systèmes utilisant une allocation de mémoire “optimiste”. Alors que ses tentatives pour demander une grande taille de tampon pour une réallocation d’un vector seront probablement rejetées à un moment donné avec un bad_alloc , la nature optimiste de l’allocateur est susceptible de toujours accorder la demande du plus petit tampon demandé par un deque susceptible d’entraîner le système d’exploitation à supprimer un processus pour tenter d’acquérir de la mémoire. Quel que soit celui qu’il choisit peut-être pas trop agréable.

Les solutions de contournement dans ce cas consistent à définir des indicateurs au niveau du système pour remplacer l’allocation optimiste (pas toujours faisable) ou à gérer la mémoire un peu plus manuellement, par exemple en utilisant votre propre allocateur pour vérifier l’utilisation de la mémoire ou similaire. Evidemment pas idéal. (Qui peut répondre à votre question comme préférer le vecteur …)

J’ai implémenté le vecteur et le deque plusieurs fois. Deque est énormément plus compliqué du sharepoint 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 un code de taille frappé lorsque vous choisissez deque over vector. Vous pouvez également rencontrer une petite vitesse si votre code utilise uniquement les éléments sur lesquels le vecteur excelle (c’est-à-dire push_back).

Si vous avez besoin d’une queue double, deque est le gagnant évident. Mais si vous faites la plupart de vos insertions et effacez à l’arrière, le vecteur sera le gagnant. Lorsque vous n’êtes pas sûr, déclarez votre conteneur avec un typedef (il est donc facile de basculer) et mesurez.

std::deque n’a pas de mémoire continue garantie – et il est souvent un peu plus lent pour l’access 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, il n’est pas garanti que les deques possèdent tous leurs éléments dans des emplacements de stockage contigus, éliminant ainsi la possibilité d’un access sécurisé par arithmétique de pointeur».

Les déques sont un peu plus compliquées, en partie parce qu’elles n’ont pas nécessairement une disposition de mémoire contiguë. Si vous avez besoin de cette fonctionnalité, vous ne devez pas utiliser de deque.

(Auparavant, ma réponse évoquait un manque de standardisation (de la même source que ci-dessus, “les deques peuvent être implémentés de différentes manières par des bibliothèques spécifiques”), mais cela s’applique en fait à presque tous les types de données standard.

Un deque est un conteneur de séquence qui permet un access aléatoire à ses éléments, mais il n’est pas garanti qu’il possède un stockage contigu.

Je pense que cette bonne idée de faire le test de performance de chaque cas. Et prendre la décision en s’appuyant sur ces tests.

Je préférerais std::deque que std::vector dans la plupart des cas.

Vous ne préféreriez pas que le vecteur soit défini en fonction de ces résultats de test (avec la source).

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

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

Encore quelques reflections, et une note à considérer circular_buffer.

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

D’un autre côté, vous avez parfois besoin de caractéristiques que le vecteur ne vous donne pas, auquel cas vous devez utiliser un deque. Par exemple, je défie quiconque de tenter de réécrire ce code sans utiliser de deque et sans modifier énormément l’algorithme.