Pourquoi std :: vector est-il tellement plus populaire que std :: deque?

Question

Double Possible:
Pourquoi je préfère utiliser un vecteur deque

Je suis curieux de savoir pourquoi est-ce que std::vector est donc beaucoup plus populaire qu' std::deque. Deque est presque aussi efficace dans la recherche, plus efficace dans l'insert (sans vecteur::reserve)et permet l'insertion, la suppression de l'avant.

Herb Sutter la fois recommandé que si vous voulez utiliser le vecteur préfèrent deque (je paraphrase). Toutefois, dans une récente conférence sur l'Écriture de C++Moderne , il a de nouveau fortement recommande de penser d' std::vector comme un conteneur par défaut. Selon le GOTW j'ai fait un lien plus tôt, même le standard a une formulation similaire.

Quelle est la raison de cette disparité? Est-il juste qu' vector est plus simple et plus bien connus, ou est-il une raison technique? Ou est-ce que vector est juste une glacière nom .. ?

Answer 1

Je ne peux pas parler pour tout le monde, mais je ne peux moi-même.

Quand j'ai lu sur std::deque, je pensais que c'était assez cool qui pendant un certain temps, j'ai considéré non seulement comme le conteneur par défaut, mais comme à peu près le seul conteneur que j'ai utilisé.

Ensuite, quelqu'un a demandé pourquoi, et j'ai expliqué en long et en ses vertus et de ses pourquoi il était le meilleur conteneur à utiliser pour pratiquement tout, et la façon dont il a été beaucoup plus polyvalent que l' std::vector.

Heureusement, le gars questionnement de ma décision, il a été assez persuasif que j'ai fait quelques tests. Les tests ont montré que dans presque tous les cas, std::deque a été plus lente qu' std::vector -- souvent par un important facteur (par exemple, autour de 2). En fait, le code que j'avais écrit à l'aide d' std::deque, juste en remplaçant std::deque avec std::vector a donné une accélération dans tous les cas sauf une poignée.

Je l'ai utilisé, std::deque dans quelques cas, depuis lors, mais certainement ne pas la traiter en tant que par défaut. Le simple fait est que dans la mise en oeuvre habituelle, c'est nettement plus lent que l' std::vector pour les plus fins.

Je dois ajouter, cependant, que je suis raisonnablement certain que la bonne mise en œuvre, il pourrait être à peu près équivalent à std::vector dans pratiquement tous les cas. La plupart utilisent une représentation qui est sans doute une grande à partir d'un point de vue asymptotique, mais ne fonctionne pas tout à fait à merveille (pour de nombreuses raisons) dans le monde réel.

Answer 2

std::vector est très bien compris, simple et est compatible avec C (à la fois en termes de disposition de la mémoire et d'utilisation de pointeurs comme itérateurs).

Pour certaines opérations, il est également plus efficace que std::deque . L'accès aux éléments par index en est un exemple.

Pour une tâche donnée, il est judicieux d'utiliser le conteneur le plus simple qui fait le travail correctement. Dans de nombreux cas, le conteneur le plus simple est std::vector .

Answer 3

La structure de l' std::deque est un peu plus complexe, ce qui rend naïf itération un peu plus cher que d' std::vector. Les insertions en std::vector avec ses réaffectations ont tendance à ne pas être gros problème, en particulier lors de l'utilisation d' reserve() et seulement en ajoutant à la fin. Aussi, il y a de plus facile à comprendre invalidation des règles pour l' std::vector bien qu'il est en fait un avantage de l' std::deque que des objets de rester sur place lors de l'insertion/retrait seulement à la fin (note qu' std::deque itérateurs obtenir invalider lors de chaque insertion, indépendant de l'endroit où l'insertion). Un autre plus pour std:vector est la garantie que les valeurs sont contigus en mémoire l'amenant à faire moins d'allocations de mémoire.

Je suppose, je recommande l'utilisation de std::deque algorithmes ont été constamment optimisé pour l'utilisation sectorielle de séquences (je ne suis pas conscient de ce que toute la bibliothèque C++ standard n'cette optimisation) et les utilisateurs ont accès à des séquences de façon constante à l'aide d'algorithmes (autant que je puisse en dire, seulement une petite fraction des utilisateurs considère la possibilité d'utiliser des algorithmes). Sinon, je dirais qu' std::deque , est la meilleure option à l'égard de la performance uniquement si vous profitez de ses propriétés spécifiques (par exemple, que les objets de rester sur place et que vous pouvez insérer/enlever à la fin). Il vaut la peine de profilage, les deux possibilités.

Answer 4

Hormis std::vector étant le plus communément appelée classe de conteneur, il a aussi plusieurs avantages par rapport std::deque, à savoir:

• Un typique std::deque nécessite une indirection supplémentaire pour accéder à la elments contrairement à ce qu'en cas d' std::vector.
• Les itérateurs en cas d' std::deque doivent être des pointeurs intelligents et pas de pointeurs, comme dans le cas d' std::vector.
• Les éléments de l' std::vector sont garantis d'être contiguës, et par conséquent, il est compatible avec le c-style de fonctions qui prennent des tableaux comme paramètres.
• std::deque fournissons pas de support pour le contrôle de la capacité et le moment de la redistribution.

En particulier, le dernier point est à noter.

Answer 5

Les gens d'utiliser std::vector sur std::deque pour une raison simple. Ils l'interface avec beaucoup de bibliothèques C et ils ont des fonctions avec des paramètres qui nécessitent un pointeur de stockage contigu, qui std::deque n'est pas (ne peuvent pas) de garantie.

Une autre raison est lorsque vous générez le code en fonction std::deque et que vos besoins changent, de sorte que vous avez à l'appui de contiguë d'accès, vous allez avoir un peu de refactoring de le faire.

Je suis obligé de mentionner qu'il existe des bibliothèques de là dont les auteurs prétendent avoir créé plus de vecteur efficace implémentations dans le but d'éliminer les pratiques inefficaces lorsque la capacité est augmentée.