Pourquoi je préférerais utiliser vector pour deque

pour connaître la différence, il faut savoir comment deque est généralement mis en œuvre. La mémoire est attribuée en blocs de tailles égales, et ils sont enchaînés ensemble (comme un tableau ou peut-être un vecteur).

ainsi pour trouver l'élément nth, vous trouvez le bloc approprié puis accédez à l'élément à l'intérieur de celui-ci. C'est de la constante de temps, car c'est toujours exactement 2 recherches, mais c'est encore plus que le vecteur.

vector fonctionne aussi bien avec APIs qui veulent un tampon contigu parce qu'ils sont soit des APIs ou sont plus polyvalents en pouvant prendre un pointeur et une longueur. (Vous pouvez donc avoir un vecteur en dessous ou un tableau régulier et appeler L'API à partir de votre bloc mémoire).

où deque a ses plus grands avantages sont:

1. lors de la croissance ou rétrécissement de la collection à partir de l'une ou l'autre extrémité
2. Lorsqu'il s'agit de collections de très grande taille.
3. quand vous avez affaire à bools et vous voulez vraiment bools plutôt qu'un bitset.

le second est moins connu, mais pour de très grandes tailles de collecte:

1. le coût de réallocation est élevé
2. le fait de devoir trouver un bloc de mémoire contigu est restrictif, de sorte que vous pouvez manquer de mémoire plus rapidement.

grandes collections dans le passé, nous sommes passés d'un modèle contigu à un modèle en bloc, nous avons pu stocker environ 5 fois plus d'une collection avant de manquer de mémoire dans un système de 32 bits. C'est en partie parce que, lors de la ré-allocation, nécessaire pour stocker l'ancien bloc ainsi que la nouvelle avant qu'il copié les éléments sur.

cela dit, vous pouvez avoir des problèmes avec std::deque sur les systèmes qui utilisent une allocation de mémoire" optimiste". Tandis que ses tentatives pour demander une grande taille de tampon pour une réallocation d'un vector sera probablement rejetée à un moment donné avec un bad_alloc , la nature optimiste de l'allocateur est susceptible d'accorder toujours la demande pour le plus petit tampon demandé par un deque et qui est susceptible d'amener le système d'exploitation à tuer un processus pour essayer d'acquérir de la mémoire. Selon elle prend peut-être pas trop agréable.

les solutions de rechange dans un tel cas sont soit la mise à niveau du système options pour outrepasser l'allocation optimiste (pas toujours faisable) ou 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 comme préférant vecteur...)

j'ai implémenté 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 plus de code complexe. Ainsi, vous verrez généralement une taille de code frappé lorsque vous choisissez deque plus vecteur. Vous pouvez également connaître une petite vitesse de frappe si votre code utilise seulement les choses que le vecteur excelle (i.e. push_back).

si vous avez besoin d'une file d'attente double, deque est le gagnant. Mais si vous faites la plupart de vos inserts et effaces à l'arrière, vecteur va être le gagnant clair. Quand vous n'êtes pas sûr, déclarez votre conteneur avec un typedef (il est donc facile de passer d'avant en arrière), et mesurer.

std::deque n'a pas de mémoire continue garantie - et il est souvent un peu plus lent pour l'accès indexé. Une deque est généralement mis en œuvre comme une "liste de vecteur".

selon http://www.cplusplus.com/reference/stl/deque / , " contrairement aux vecteurs, les deques ne sont pas garanties d'avoir tous ses éléments dans des emplacements de stockage contigus, éliminant ainsi la possibilité d'un accès sûr par l'arithmétique pointer."

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

(Auparavant, ma réponse a soulevé un manque de standardisation (à partir de la même source que ci-dessus, "deques peut être mis en œuvre par des bibliothèques spécifiques de différentes façons"), mais cela s'applique en fait à peu près n'importe quel type de données de bibliothèque standard.)

un deque est un conteneur séquentiel 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 le test de perfomance de chaque cas. Et prendre une décision en se basant sur ces tests.

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

vous ne préférez pas vector à deque selon ces résultats d'essai (avec source).

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

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

encore quelques réflexions, et une note à envisagez circular_buffer.

d'une part, vector est assez souvent simplement plus rapide que deque. Si vous n'avez pas réellement besoin toutes les caractéristiques de deque, utilisez un vecteur.

par contre, parfois vous do avez besoin de caractéristiques que le vecteur ne vous donne pas, auquel cas vous devez utiliser une déque. Par exemple, je défie quiconque d'essayer de réécrire ce code , sans utiliser une deque, et sans énormément modifier l'algorithme.