Qu'est-ce qu'une déque en STL?

Question

Je cherchais à conteneurs STL et à essayer de comprendre ce qu'ils sont vraiment (c'est à dire la structure de données utilisée), et de la deque m'a arrêté: je pensais au début que c'était une double liste chaînée, ce qui permettrait l'insertion et la suppression de deux extrémités en temps constant, mais je suis troublé par la promesse faite par l'opérateur [] à faire en temps constant. Dans une liste, l'arbitraire, l'accès devrait être O(n), droit?

Et si c'est un tableau dynamique, comment peut-il ajouter des éléments dans la constante de temps? Il convient de mentionner que la réaffectation peut arriver, et que O(1) est un coût non amorti, comme pour un vecteur.

Donc, je me demande ce qu'est cette structure qui permet à l'arbitraire de l'accès en temps constant, et en même temps ne doit jamais être déplacé vers un nouvel endroit plus grand.

Answer 1

Une deque est un peu définie de manière récursive: en interne, il maintient un double clos de la file d'attente de morceaux ("blocs" dans le graphique ci-dessous) de taille fixe. Chaque morceau est un vecteur, et la file d'attente ("map" dans le graphique ci-dessous) de morceaux de lui-même, est également un vecteur.

^_[Source]

Il y a une excellente analyse des caractéristiques de performance et comment il se compare à l' vector de plus à CodeProject.

La GCC de la bibliothèque standard de mise en œuvre utilise en interne une T** pour représenter la carte. Chaque bloc de données est un T* qui est allouée à certains de taille fixe __deque_buf_size (qui dépend de l' sizeof(T)).

Answer 2

L'imaginer comme un vecteur de vecteurs. Seulement, ils ne sont pas standard std::vectors.

L'extérieur vecteur contient des pointeurs à l'intérieur des vecteurs. Lorsque sa capacité est modifié par la réaffectation, plutôt que d'allouer tout l'espace vide à la fin, comme std::vector n', il divise l'espace vide à l'égalité des parties au début et à la fin du vecteur. Cela permet d' push_front et push_back sur ce vecteur à la fois de se produire dans amorti O(1) fois.

L'intérieur de vecteur de comportement doit changer selon qu'il est à l'avant ou à l'arrière de l' deque. À l'arrière, il peut se comporter comme une norme std::vector où elle pousse à la fin, et push_back se produit en O(1) fois. À l'avant, il a besoin de faire le contraire, de plus en plus au début avec chaque push_front. Dans la pratique, cela est facilement réalisable par l'ajout d'un pointeur vers l'élément avant et la direction de la croissance ainsi que la taille. Avec cette simple modification push_front peut également être O(1) fois.

L'accès à tout élément de compensation et en divisant le bon extérieur vecteur d'index qui se produit en O(1), et l'indexation dans l'intérieur de vecteur, qui est également en O(1). Cela suppose que l'intérieur vecteurs sont tous de taille fixe, sauf pour ceux qui sont au début ou à la fin de l' deque.

Answer 3

deque = file d'attente double

Un conteneur qui peut pousser dans les deux sens.

Deque est implémenté sous forme de vector de vectors (une liste de vecteurs donne un accès aléatoire à temps constant). La taille des vecteurs secondaires dépend de la mise en œuvre. Un algorithme courant consiste à utiliser une taille constante en octets.

Answer 4

(C'est une réponse que j'ai donné dans un autre thread. Essentiellement, je suis en arguant de même assez naïf implémentations, à l'aide d'un seul vector, conforme aux exigences de la "constante de non-amorti push_{avant,à l'arrière}". Vous pourriez être surpris, et pense que c'est impossible, mais j'ai trouvé d'autres devis dans la norme qui définissent le contexte d'une façon surprenante. S'il vous plaît garder avec moi; si j'ai fait une erreur dans cette réponse, il serait très utile pour identifier des choses qui m'ont dit correctement et où ma logique est en panne. )

Dans cette réponse, je ne cherche pas à identifier une bonne mise en œuvre, je suis purement et simplement d'essayer de nous aider à interpréter la complexité des exigences de la norme C++. Je suis citant N3242, qui est, selon Wikipedia, les dernières disponibles gratuitement de C++11 de la normalisation document. (Il semble être organisées différemment de la version finale de la norme, et donc je ne vais pas citer exactement les numéros de page. Bien sûr, ces règles ont peut-être changé dans la norme finale, mais je ne pense pas que ce qui s'est passé.)

Un deque<T> pourrait être correctement mis en œuvre à l'aide d'un vector<T*>. Tous les éléments sont copiés sur le tas et les pointeurs stockés dans un vecteur. (Plus sur le vecteur plus tard).

Pourquoi T* au lieu de T? Parce que la norme exige que

"Une insertion à la fin de la deque annule tous les itérateurs de la deque, mais n'a aucun effet sur la validité des références à les éléments de la deque."

(mon emphase). L' T* aide à satisfaire que. Il nous aide aussi à répondre à cette:

"L'insertion d'un élément unique, soit au début ou à la fin d'une deque toujours ..... les causes d'un seul appel à un constructeur de T."

Maintenant, pour la (controversée) bits. Pourquoi utiliser un vector pour stocker l' T*? Il nous donne accès aléatoire, qui est un bon point de départ. Oublions la complexité de vecteur pour un moment et de construire jusqu'à ce soin:

La norme parle de la "le nombre d'opérations sur les objets contenus.". Pour deque::push_front c'est clairement 1 parce que c'est précisément un T objet est construit et zéro de l'existant, T des objets sont en lecture ou numérisés en aucune façon. De ce nombre, 1, est clairement une constante et indépendante du nombre d'objets actuellement dans le deque. Cela nous permet de dire que:

"Pour notre deque::push_front, le nombre d'opérations sur les objets contenus (Ts) est fixe et est indépendant du nombre d'objets déjà dans le deque.'

Bien sûr, le nombre d'opérations de l' T* ne sera pas très bien élevés. Lorsque l' vector<T*> devient trop gros, ça va être realloced et nombre T*s sera copié autour de. Donc oui, le nombre d'opérations de l' T* varient grandement, mais le nombre d'opérations sur T ne seront pas affectés.

Pourquoi nous soucions-nous de cette distinction entre les opérations de comptage sur T et comptage des opérations sur T*? C'est parce que la norme dit:

Toutes les exigences de complexité dans la présente clause sont exprimés uniquement en termes de nombre d'opérations sur les objets contenus.

Pour l' deque, les objets contenus sont l' T, pas l' T*, ce qui signifie que nous pouvons ignorer toute opération de copie (ou reallocs) T*.

Je n'ai pas dit beaucoup sur la façon dont un vecteur se comporter dans un deque. Peut-être que nous pourrions interpréter comme un tampon circulaire (avec le vecteur tenant toujours son maximum capacity(), puis realloc tout dans une plus grande mémoire tampon lorsque le vecteur est plein. Les détails n'ont pas d'importance.

Dans les derniers paragraphes, nous avons analysé deque::push_front et la relation entre le nombre d'objets dans la deque déjà et le nombre d'opérations effectuées par push_front sur les contenus T-objets. Et nous avons trouvé qu'ils étaient indépendants les uns des autres. Comme la norme mandats que la complexité est en termes d'opérations-sur-T, alors on peut dire que cela a constante de la complexité.

Oui, les Opérations Sur T*-la Complexité est amorti (en raison de l' vector), mais nous sommes seulement intéressés par les Opérations-Sur-T-Complexité et elle est constante (non amorti).

La complexité de vecteur::push_back ou vecteur::push_front est pas pertinent dans cette mise en œuvre; ces considérations impliquent des opérations sur T* et sont donc hors de propos. Si la norme se réfère à la "classique" théorique de la notion de complexité, alors ils n'auraient pas explicitement restreint à la "certain nombre d'opérations sur les objets contenus". Suis-je overinterpreting cette phrase?

Answer 5

Bien que la norme ne requière aucune implémentation particulière (uniquement un accès aléatoire à temps constant), un deque est généralement implémenté sous la forme d'une collection de "pages" de mémoire contiguë. De nouvelles pages sont allouées au besoin, mais vous avez toujours un accès aléatoire. Contrairement à std::vector , on ne vous promet pas que les données sont stockées de manière contiguë, mais comme pour les vecteurs, les insertions au milieu nécessitent beaucoup de déplacements.