Pourquoi je préfère utiliser un vecteur deque

Question

Depuis

1. ils sont à la fois continue de mémoire contenant
2. caractéristique sage, deque a presque vecteur a plus mais, étant donné qu'il est plus efficace de les insérer dans le front.

pourquoi devrait tout préférez vecteur pour deque?

Answer 1

Éléments d'un deque sont no contiguës dans la mémoire ; vector sont garantis. Ainsi, si vous devez interagir avec une bibliothèque C simple qui a besoin de tableaux contigus, ou si vous vous souciez (beaucoup) de la localité spatiale, vous pouvez préférer vector . En outre, étant donné qu'il y a une comptabilité supplémentaire, les autres opérations sont probablement (légèrement) plus chères que leur équivalent. vector opérations. D'autre part, l'utilisation d'un grand nombre d'instances de vector peut entraîner une fragmentation inutile du tas (ce qui ralentit les appels à new ).

En outre, comme il a été souligné ailleurs sur StackOverflow Il y a d'autres bonnes discussions ici : http://www.gotw.ca/gotw/054.htm .

Answer 2

Pour faire la différence, il faut savoir comment deque est généralement mis en œuvre. La mémoire est allouée en blocs de taille égale, qui sont enchaînés les uns aux autres (sous la forme d'un tableau ou éventuellement d'un vecteur).

Pour trouver le nième élément, il faut donc trouver le bloc approprié, puis accéder à l'élément qu'il contient. C'est un temps constant, car il y a toujours exactement deux recherches, mais c'est toujours plus que le vecteur.

vector fonctionne également bien avec les API qui veulent un tampon contigu parce qu'il s'agit d'API C ou qu'elles sont plus polyvalentes en ce sens qu'elles peuvent prendre un pointeur et une longueur. (Vous pouvez donc avoir un vecteur en dessous ou un tableau normal et appeler l'API à partir de votre bloc de mémoire).

Où deque a ses plus grands avantages :

1. Lors de l'agrandissement ou du rétrécissement de la collection à partir de l'une ou l'autre extrémité
2. Lorsque vous avez affaire à des collections de très grande taille.
3. Lorsqu'il s'agit de bools et que vous voulez vraiment des bools plutôt qu'un ensemble de bits.

La seconde est moins connue, mais elle concerne des collections de très grande taille :

1. Le coût de la réaffectation 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.

Lorsque j'ai eu à traiter de grandes collections dans le passé et que je suis passé d'un modèle contigu à un modèle par blocs, nous avons pu stocker une collection environ cinq fois plus grande avant de manquer de mémoire dans un système 32 bits. Cela s'explique en partie par le fait 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.

Ceci étant dit, vous pouvez avoir des problèmes avec std::deque sur les systèmes qui utilisent une allocation de mémoire "optimiste". Alors que ses tentatives de demander une grande taille de mémoire tampon pour une réaffectation d'un fichier vector sera probablement rejetée à un moment ou à un autre avec un bad_alloc l'allocateur étant optimiste, il est probable qu'il accède toujours à la demande de la plus petite mémoire tampon demandée par un utilisateur. deque et cela peut amener le système d'exploitation à tuer un processus pour essayer d'acquérir de la mémoire. Quel que soit celui qu'il choisira, il risque de ne pas être très agréable.

Dans ce cas, les solutions de contournement consistent soit à définir des drapeaux au niveau du système pour ignorer l'allocation optimiste (ce qui n'est pas toujours possible), soit à gérer la mémoire plus manuellement, par exemple en utilisant votre propre allocateur qui vérifie l'utilisation de la mémoire, ou quelque chose de similaire. Ce n'est évidemment pas la solution idéale. (Ce qui peut répondre à votre question sur le vecteur à privilégier...)

Answer 3

J'ai mis en œuvre à la fois vector et deque à plusieurs reprises. deque est beaucoup plus compliqué du point de vue de la mise en œuvre. Cette complication se traduit par un code plus important et plus complexe. Vous constaterez donc généralement une augmentation de la taille du code lorsque vous choisirez deque plutôt que vector. Vous pouvez également constater un léger gain de vitesse si votre code n'utilise que les éléments pour lesquels le vecteur excelle (c.-à-d. push_back).

Si vous avez besoin d'une file d'attente à double extrémité, deque est le vainqueur incontesté. Mais si vous effectuez la plupart de vos insertions et effacements à l'arrière, vector sera le grand gagnant. Si vous n'êtes pas sûr de vous, déclarez votre conteneur avec un typedef (pour qu'il soit facile de passer de l'un à l'autre), et mesurez.

Answer 4

std::deque n'a pas de mémoire continue garantie - et il est souvent un peu plus lent pour l'accès indexé. Un deque est typiquement implémenté comme une "liste de vecteurs".

Answer 5

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