Qu'est-ce qu'un deque en STL?

194

Je regardais les conteneurs STL et essayais de comprendre ce qu'ils sont vraiment (c'est-à-dire la structure de données utilisée), et le deque m'a arrêté: j'ai d'abord pensé que c'était une double liste chaînée, ce qui permettrait l'insertion et la suppression des deux extrémités dans temps constant, mais je suis troublé par la promesse faite par l'opérateur [] de se faire en temps constant. Dans une liste chaînée, l'accès arbitraire doit être O (n), non?

Et si c'est un tableau dynamique, comment peut-il ajouter des éléments en temps constant? Il faut mentionner qu'une réallocation peut se produire, et que O (1) est un coût amorti, comme pour un vecteur .

Je me demande donc quelle est cette structure qui permet un accès arbitraire en temps constant, et en même temps n'a jamais besoin d'être déplacée vers un nouvel endroit plus grand.

Zonko
la source
4
duplicata possible de l' accès STL deque par index est O (1)?
fredoverflow le
1
@Graham «dequeue» est un autre nom commun pour «deque». J'ai toujours approuvé la modification car «deque» est généralement le nom canonique.
Konrad Rudolph le
@Konrad Merci. La question portait spécifiquement sur le deque C ++ STL, qui utilise l'orthographe plus courte.
Graham Borland
2
dequesignifie file d'attente double , bien que, évidemment, l'exigence stricte d'accès O (1) aux éléments du milieu soit particulière à C ++
Matthieu M.

Réponses:

186

Un deque est défini de manière quelque peu récursive: en interne, il maintient une file d'attente à deux extrémités de blocs de taille fixe. Chaque morceau est un vecteur, et la file d'attente («carte» dans le graphique ci-dessous) des morceaux elle-même est également un vecteur.

schéma de la disposition de la mémoire d'un deque

Il y a une excellente analyse des caractéristiques de performance et de la façon dont elles se comparent vectorà celles de CodeProject .

L'implémentation de la bibliothèque standard GCC utilise en interne a T**pour représenter la carte. Chaque bloc de données est un T*qui est alloué avec une taille fixe __deque_buf_size(qui dépend de sizeof(T)).

Konrad Rudolph
la source
28
C'est la définition d'un deque tel que je l'ai appris, mais de cette façon, il ne peut pas garantir un accès à temps constant, il doit donc manquer quelque chose.
stefaanv
14
@stefaanv, @Konrad: les implémentations C ++ que j'ai vues utilisaient un tableau de pointeurs vers des tableaux de taille fixe. Cela signifie effectivement que push_front et push_back ne sont pas vraiment des temps constants, mais avec des facteurs de croissance intelligents, vous obtenez toujours des temps constants amortis, donc O (1) n'est pas si erroné, et en pratique, il est plus rapide que le vecteur car vous échangez des pointeurs uniques plutôt que des objets entiers (et moins de pointeurs que des objets).
Matthieu M.
5
L'accès à temps constant est toujours possible. Juste, si vous avez besoin d'allouer un nouveau bloc à l'avant, repoussez un nouveau pointeur sur le vecteur principal et décalez tous les pointeurs.
Xeo
4
Si la carte (la file d'attente elle-même) était une liste à deux extrémités, je ne vois pas comment elle pourrait permettre l'accès aléatoire à O (1). Il pourrait être implémenté comme un tampon circulaire, ce qui permettrait au redimensionnement circulaire du tampon d'être plus efficace: Copiez uniquement les pointeurs au lieu de tous les éléments de la file d'attente. Cela semble néanmoins être un petit avantage.
Wernight
15
@JeremyWest Pourquoi pas? L'accès indexé va à l'élément i% B-ème dans le bloc i / B-ème (B = taille du bloc), c'est clairement O (1). Vous pouvez ajouter un nouveau bloc dans O (1) amorti, donc l'ajout d'éléments est amorti O (1) à la fin. Ajouter un nouvel élément au début est O (1) à moins qu'un nouveau bloc ne doive être ajouté. Ajouter un nouveau bloc au début n'est pas O (1), c'est vrai, c'est O (N) mais en réalité, il a un très petit facteur constant car il suffit de déplacer N / B pointeurs plutôt que N éléments.
Konrad Rudolph
22

Imaginez-le comme un vecteur de vecteurs. Seulement, ils ne sont pas des std::vectorarticles standard .

Le vecteur externe contient des pointeurs vers les vecteurs internes. Lorsque sa capacité est modifiée par réallocation, plutôt que d'allouer tout l'espace vide à la fin comme le std::vectorfait, il divise l'espace vide en parties égales au début et à la fin du vecteur. Cela permet à push_frontet push_backsur ce vecteur de se produire tous les deux en temps O (1) amorti.

Le comportement du vecteur interne doit changer selon qu'il se trouve à l'avant ou à l'arrière du fichier deque. À l'arrière, il peut se comporter comme un standard std::vectorlà où il pousse à la fin et push_backse produit en temps O (1). À l'avant, il doit faire le contraire, en grandissant au début avec chacun push_front. En pratique, ceci est facilement réalisé en ajoutant un pointeur sur l'élément avant et la direction de croissance avec la taille. Avec cette simple modification push_frontpeut également être le temps O (1).

L'accès à n'importe quel élément nécessite un décalage et une division à l'indice de vecteur externe approprié qui se produit dans O (1), et une indexation dans le vecteur interne qui est également O (1). Cela suppose que les vecteurs internes sont tous de taille fixe, à l'exception de ceux du début ou de la fin du deque.

Mark Ransom
la source
1
Vous pouvez décrire les vecteurs internes comme ayant une capacité
Caleth
18

deque = file d'attente double

Un contenant qui peut pousser dans les deux sens.

Deque est généralement implémenté comme un vectorof vectors(une liste de vecteurs ne peut pas donner un accès aléatoire à temps constant). Alors que la taille des vecteurs secondaires dépend de l'implémentation, un algorithme courant consiste à utiliser une taille constante en octets.

Alok Save
la source
6
Ce n'est pas tout à fait des vecteurs en interne. Les structures internes peuvent avoir une capacité allouée mais inutilisée au début comme à la fin
Mooing Duck
@MooingDuck: C'est vraiment une implémentation définie. Cela peut être un tableau de tableaux ou un vecteur de vecteurs ou tout ce qui peut fournir le comportement et la complexité imposés par la norme.
Alok Enregistrer
1
@Als: Je ne pense à arrayrien ni à quoi que ce soit vectorqui puisse promettre O(1)push_front amorti . L'intérieur des deux structures au moins doit pouvoir avoir un O(1)push_front, ce que ni un arrayni un vectorne peuvent garantir.
Mooing Duck
4
@MooingDuck, cette exigence est facilement satisfaite si le premier morceau se développe de haut en bas plutôt que de bas en haut. De toute évidence, une norme vectorne fait pas cela, mais c'est une modification assez simple pour le rendre ainsi.
Mark Ransom
3
@ Mooing Duck, push_front et push_back peuvent être facilement réalisés en O amorti (1) avec une structure vectorielle unique. C'est juste un peu plus la comptabilité d'un tampon circulaire, rien de plus. Supposons que vous ayez un vecteur régulier de capacité 1000 avec 100 éléments aux positions 0 à 99. Maintenant, quand un push_Front se produit, vous appuyez simplement à la fin, c'est-à-dire à la position 999, puis 998 etc. jusqu'à ce que les deux extrémités se rencontrent. Ensuite, vous réallouez (avec une croissance exponentielle pour garantir des temps constants d'amortissement) comme vous le feriez avec un vecteur ordinaire. Donc, effectivement, vous avez juste besoin d'un pointeur supplémentaire vers le premier el.
plamenko le
14

(C'est une réponse que j'ai donnée dans un autre thread . Essentiellement, je soutiens que même les implémentations assez naïves, en utilisant un seul vector, sont conformes aux exigences de "push_ {front, back} constant non amorti". Vous pourriez être surpris , et je pense que cela est impossible, mais j'ai trouvé d'autres citations pertinentes dans la norme qui définissent le contexte de manière surprenante. Veuillez me supporter; si j'ai fait une erreur dans cette réponse, il serait très utile d'identifier les éléments J'ai dit correctement et où ma logique est tombée en panne.)

Dans cette réponse, je n'essaie pas d'identifier une bonne implémentation, j'essaie simplement de nous aider à interpréter les exigences de complexité de la norme C ++. Je cite N3242 , qui est, selon Wikipédia , le dernier document de normalisation C ++ 11 disponible gratuitement. (Il semble être organisé différemment de la norme finale, et je ne citerai donc pas les numéros de page exacts. Bien sûr, ces règles ont peut-être changé dans la norme finale, mais je ne pense pas que cela se soit produit.)

A deque<T>pourrait être implémenté correctement en utilisant un vector<T*>. Tous les éléments sont copiés sur le tas et les pointeurs stockés dans un vecteur. (Plus d'informations sur le vecteur plus tard).

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

"Une insertion à l'une ou l'autre extrémité du deque invalide tous les itérateurs du deque, mais n'a aucun effet sur la validité des références aux éléments du deque. "

(je souligne). Les T*aides pour satisfaire cela. Cela nous aide également à satisfaire ceci:

"L'insertion d'un seul élément au début ou à la fin d'un deque toujours ..... provoque un seul appel à un constructeur de T. "

Maintenant pour le peu (controversé). Pourquoi utiliser un vectorpour stocker le T*? Cela nous donne un accès aléatoire, ce qui est un bon début. Oublions un instant la complexité du vecteur et construisons-y soigneusement:

La norme parle du "nombre d'opérations sur les objets contenus". Car deque::push_frontc'est clairement 1 car exactement un Tobjet est construit et aucun des Tobjets existants n'est lu ou scanné de quelque manière que ce soit. Ce nombre, 1, est clairement une constante et est indépendant 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 (les Ts) est fixe et est indépendant du nombre d'objets déjà dans le deque."

Bien sûr, le nombre d'opérations sur le T*ne sera pas aussi bien comporté. Lorsque le vector<T*>fichier devient trop grand, il sera réaffecté et de nombreux T*s seront copiés. Alors oui, le nombre d'opérations sur le T*variera énormément, mais le nombre d'opérations sur Tne sera pas affecté.

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

Toutes les exigences de complexité de cette clause sont énoncées uniquement en termes de nombre d'opérations sur les objets contenus.

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

Je n'ai pas beaucoup parlé de la façon dont un vecteur se comporterait dans une deque. Peut-être que nous l'interpréterions comme un tampon circulaire (avec le vecteur prenant toujours son maximum capacity(), puis réallouer tout dans un tampon plus grand lorsque le vecteur est plein. Les détails n'ont pas d'importance.

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

Oui, la complexité Operations-On-T * est amortie (en raison de la vector), mais nous ne nous intéressons qu'à la complexité Operations-On-T * et c'est constant (non amorti).

La complexité de vector :: push_back ou vector :: push_front n'est pas pertinente dans cette implémentation; ces considérations impliquent des opérations T*et ne sont donc pas pertinentes. Si le standard faisait référence à la notion théorique «conventionnelle» de complexité, alors ils ne se seraient pas explicitement limités au «nombre d'opérations sur les objets contenus». Est-ce que je surinterprète cette phrase?

Aaron McDaid
la source
8
Cela me ressemble beaucoup à de la triche! Lorsque vous spécifiez la complexité d'une opération, vous ne le faites pas sur une partie des données uniquement: vous voulez avoir une idée de la durée d'exécution attendue de l'opération que vous appelez, quel que soit son fonctionnement. Si je suis votre logique sur les opérations sur T, cela voudrait dire que vous pourriez vérifier si la valeur de chaque T * est un nombre premier à chaque fois qu'une opération est effectuée et toujours respecter la norme puisque vous ne touchez pas Ts. Pouvez-vous préciser d'où viennent vos devis?
Zonko
2
Je pense que les rédacteurs standard savent qu'ils ne peuvent pas utiliser la théorie de la complexité conventionnelle parce que nous n'avons pas de système entièrement spécifié où nous connaissons, par exemple, la complexité de l'allocation de mémoire. Il n'est pas réaliste de prétendre que la mémoire peut être allouée pour un nouveau membre de a listquelle que soit la taille actuelle de la liste; si la liste est trop grande, l'allocation sera lente ou échouera. Par conséquent, pour autant que je sache, le comité a pris la décision de ne spécifier que les opérations qui peuvent être objectivement comptées et mesurées. (PS: j'ai une autre théorie à ce sujet pour une autre réponse.)
Aaron McDaid
Je suis à peu près sûr O(n)que le nombre d'opérations est asymptotiquement proportionnel au nombre d'éléments. IE, les méta-opérations comptent. Sinon, limiter la recherche à O(1). Ergo, les listes liées ne sont pas éligibles.
Mooing Duck
8
C'est une interprétation très intéressante, mais par cette logique, a listpourrait également être implémenté en tant que vectorpointeurs (les insertions au milieu se traduiront par un seul appel de constructeur de copie, quelle que soit la taille de la liste, et le O(N)brassage des pointeurs peut être ignoré car ce ne sont pas des opérations sur T).
Mankarse
1
C'est un bon langage juridique (même si je ne vais pas essayer de déterminer si c'est réellement correct ou s'il y a un point subtil dans la norme qui interdit cette implémentation). Mais ce ne sont pas des informations utiles en pratique, car (1) les implémentations courantes ne sont pas implémentées de dequecette manière et (2) "tricher" de cette manière (même si cela est autorisé par la norme) lorsque le calcul de la complexité algorithmique n'est pas utile pour écrire des programmes efficaces .
Kyle Strand
13

Vue d'ensemble, vous pouvez penser dequecomme undouble-ended queue

Présentation de deque

Les données dans dequesont stockées par des morceaux de vecteur de taille fixe, qui sont

pointé par a map(qui est aussi un morceau de vecteur, mais sa taille peut changer)

deque structure interne

Le code de la partie principale du deque iteratorest comme ci-dessous:

/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
    typedef __deque_iterator<T, buff_size>              iterator;
    typedef T**                                         map_pointer;

    // pointer to the chunk
    T* cur;       
    T* first;     // the begin of the chunk
    T* last;      // the end of the chunk

    //because the pointer may skip to other chunk
    //so this pointer to the map
    map_pointer node;    // pointer to the map
}

Le code de la partie principale du dequeest comme ci-dessous:

/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
    public:
        typedef T              value_type;
        typedef T&            reference;
        typedef T*            pointer;
        typedef __deque_iterator<T, buff_size> iterator;

        typedef size_t        size_type;
        typedef ptrdiff_t     difference_type;

    protected:
        typedef pointer*      map_pointer;

        // allocate memory for the chunk 
        typedef allocator<value_type> dataAllocator;

        // allocate memory for map 
        typedef allocator<pointer>    mapAllocator;

    private:
        //data members

        iterator start;
        iterator finish;

        map_pointer map;
        size_type   map_size;
}

Ci-dessous, je vais vous donner le code de base de deque, principalement environ trois parties:

  1. itérateur

  2. Comment construire un deque

1. itérateur ( __deque_iterator)

Le principal problème de l'itérateur est, quand ++, - iterator, il peut passer à un autre morceau (s'il pointe vers le bord du morceau). Par exemple, il y a trois morceaux de données: chunk 1, chunk 2, chunk 3.

Les pointer1pointeurs vers le début de chunk 2, lorsque l'opérateur --pointerpointera vers la fin de chunk 1, de manière à ce que le pointer2.

entrez la description de l'image ici

Ci-dessous, je vais donner la fonction principale de __deque_iterator:

Tout d'abord, passez à n'importe quel morceau:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

Notez que, la chunk_size()fonction qui calcule la taille du morceau, vous pouvez penser qu'elle renvoie 8 pour simplifier ici.

operator* obtenir les données dans le bloc

reference operator*()const{
    return *cur;
}

operator++, --

// formes de préfixe d'incrément

self& operator++(){
    ++cur;
    if (cur == last){      //if it reach the end of the chunk
        set_node(node + 1);//skip to the next chunk
        cur = first;
    }
    return *this;
}

// postfix forms of increment
self operator++(int){
    self tmp = *this;
    ++*this;//invoke prefix ++
    return tmp;
}
self& operator--(){
    if(cur == first){      // if it pointer to the begin of the chunk
        set_node(node - 1);//skip to the prev chunk
        cur = last;
    }
    --cur;
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}
itérateur sauter n étapes / accès aléatoire
self& operator+=(difference_type n){ // n can be postive or negative
    difference_type offset = n + (cur - first);
    if(offset >=0 && offset < difference_type(buffer_size())){
        // in the same chunk
        cur += n;
    }else{//not in the same chunk
        difference_type node_offset;
        if (offset > 0){
            node_offset = offset / difference_type(chunk_size());
        }else{
            node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
        }
        // skip to the new chunk
        set_node(node + node_offset);
        // set new cur
        cur = first + (offset - node_offset * chunk_size());
    }

    return *this;
}

// skip n steps
self operator+(difference_type n)const{
    self tmp = *this;
    return tmp+= n; //reuse  operator +=
}

self& operator-=(difference_type n){
    return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
    self tmp = *this;
    return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
    return *(*this + n);
}

2. Comment construire un deque

fonction commune de deque

iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
    //invoke __deque_iterator operator*
    // return start's member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish's  *cur
}

reference operator[](size_type n){
    //random access, use __deque_iterator operator[]
    return start[n];
}


template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
    fill_initialize(n, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
    // allocate memory for map and chunk
    // initialize pointer
    create_map_and_nodes(n);

    // initialize value for the chunks
    for (map_pointer cur = start.node; cur < finish.node; ++cur) {
        initialized_fill_n(*cur, chunk_size(), value);
    }

    // the end chunk may have space node, which don't need have initialize value
    initialized_fill_n(finish.first, finish.cur - finish.first, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
    // the needed map node = (elements nums / chunk length) + 1
    size_type num_nodes = num_elements / chunk_size() + 1;

    // map node num。min num is  8 ,max num is "needed size + 2"
    map_size = std::max(8, num_nodes + 2);
    // allocate map array
    map = mapAllocator::allocate(map_size);

    // tmp_start,tmp_finish poniters to the center range of map
    map_pointer tmp_start  = map + (map_size - num_nodes) / 2;
    map_pointer tmp_finish = tmp_start + num_nodes - 1;

    // allocate memory for the chunk pointered by map node
    for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
        *cur = dataAllocator::allocate(chunk_size());
    }

    // set start and end iterator
    start.set_node(tmp_start);
    start.cur = start.first;

    finish.set_node(tmp_finish);
    finish.cur = finish.first + num_elements % chunk_size();
}

Supposons qu'il y i_dequeait 20 éléments int 0~19dont la taille de bloc est de 8, et maintenant push_back 3 éléments (0, 1, 2) à i_deque:

i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);

C'est la structure interne comme ci-dessous:

entrez la description de l'image ici

Puis push_back à nouveau, il invoquera allouer un nouveau bloc:

push_back(3)

entrez la description de l'image ici

Si nous push_front, il allouera un nouveau morceau avant le précédentstart

entrez la description de l'image ici

Notez lorsque l' push_backélément dans deque, si toutes les cartes et les morceaux sont remplis, cela provoquera l'allocation d'une nouvelle carte et l'ajustement des morceaux.Mais le code ci-dessus peut être suffisant pour que vous compreniez deque.

Jayhello
la source
Vous avez mentionné, "Notez lorsque l'élément push_back dans deque, si toutes les cartes et les morceaux sont remplis, cela provoquera l'allocation d'une nouvelle carte et ajuster les morceaux". Je me demande pourquoi la norme C ++ dit "[26.3.8.4.3] L'insertion d'un seul élément au début ou à la fin d'un deque prend toujours un temps constant" dans N4713. L'allocation d'un bloc de données prend plus qu'un temps constant. Non?
HCSF
7

Je lisais "Structures de données et algorithmes en C ++" par Adam Drozdek, et j'ai trouvé cela utile. HTH.

Un aspect très intéressant de STL deque est sa mise en œuvre. Un deque STL n'est pas implémenté comme une liste chaînée mais comme un tableau de pointeurs vers des blocs ou des tableaux de données. Le nombre de blocs change de manière dynamique en fonction des besoins de stockage et la taille du tableau de pointeurs change en conséquence.

Vous pouvez remarquer au milieu se trouve le tableau de pointeurs vers les données (morceaux à droite), et vous pouvez également remarquer que le tableau au milieu change dynamiquement.

Une image vaut mille mots.

entrez la description de l'image ici

Keloo
la source
1
Merci d'avoir référé un livre. J'ai lu la dequepartie et c'est assez bon.
Rick
@Rick heureux d'entendre ça. Je me souviens avoir fouillé dans le deque à un moment donné parce que je ne pouvais pas comprendre comment vous pouvez avoir un accès aléatoire (opérateur []) dans O (1). Prouver également que (push / pop) _ (back / front) a amorti la complexité O (1) est un «moment aha» intéressant.
Keloo
6

Bien que la norme n'impose aucune implémentation particulière (uniquement un accès aléatoire à temps constant), un deque est généralement implémenté comme une collection de "pages" mémoire contiguës. De nouvelles pages sont allouées selon les besoins, mais vous avez toujours un accès aléatoire. Contrairement à std::vector, vous n'êtes pas promis que les données sont stockées de manière contiguë, mais comme le vecteur, les insertions au milieu nécessitent beaucoup de déplacement.

Kerrek SB
la source
4
ou les suppressions au milieu nécessitent beaucoup de relocalisation
Mark Hendrickson
Si insertnécessite beaucoup de délocalisation, comment l'expérience 4 montre-t-elle ici une différence stupéfiante entre vector::insert()et deque::insert()?
Bula
1
@Bula: Peut-être en raison d'une mauvaise communication des détails? La complexité de l'insertion de deque est «linéaire dans le nombre d'éléments insérés plus la moindre des distances au début et à la fin de la deque». Pour ressentir ce coût, vous devez insérer dans le milieu actuel; est-ce ce que fait votre benchmark?
Kerrek SB
@KerrekSB: l'article avec benchmark a été référencé dans la réponse de Konrad ci-dessus. En fait, je n'ai pas remarqué la section des commentaires de l'article ci-dessous. Dans le fil "Mais deque a un temps d'insertion linéaire?" L'auteur a mentionné qu'il a utilisé l'insertion à la position 100 à travers tous les tests, ce qui rend les résultats un peu plus compréhensibles.
Bula