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

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.

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.

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)).

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.

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.

(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?

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

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)

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.

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;
}

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:

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

push_back(3)

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

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.

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.

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.