Was ist eigentlich ein Deque in STL?

Ich habe mir STL-Container angesehen und versucht herauszufinden, was sie wirklich sind (dh die verwendete Datenstruktur) und die deque hielt mich auf: Ich dachte zuerst, dass es sich um eine doppelt verknüpfte Liste handelt, die das Einfügen und Löschen von beiden Enden in konstanter Zeit ermöglichen würde, aber ich bin beunruhigt darüber das gemachte Versprechen durch den Betreiber [] in konstanter Zeit zu erledigen. In einer verketteten Liste sollte der beliebige Zugriff O(n) sein, richtig?

Und wenn es ein dynamisches Array ist, wie kann es Elemente hinzufügen in konstanter Zeit? Es sollte erwähnt werden, dass es zu einer Neuzuweisung kommen kann und dass O(1) Amortisationskosten sind, wie für einen Vektor.

Ich frage mich also, was diese Struktur ist, die willkürlichen Zugriff in konstanter Zeit ermöglicht und gleichzeitig nie an einen neuen, größeren Ort verlegt werden muss.

Eine deque ist etwas rekursiv definiert: intern verwaltet sie eine doppelendige Warteschlange von Brocken von fester Größe. Jeder Chunk ist ein Vektor, und die Warteschlange („Map“ in der Grafik unten) von Chunks selbst ist ebenfalls ein Vektor.

Es gibt eine großartige Analyse der Leistungsmerkmale und wie sie mit denen verglichen werden vector bei CodeProject.

Die Implementierung der GCC-Standardbibliothek verwendet intern a T** die Karte darzustellen. Jeder Datenblock ist a T* die mit einer festen Größe zugewiesen ist __deque_buf_size (was davon abhängt sizeof(T)).

Aus der Übersicht können Sie denken deque Als ein double-ended queue

Die Daten in deque werden durch Chunks mit Vektoren fester Größe gespeichert, die sind

verwiesen durch a map(Das ist auch ein Teil des Vektors, aber seine Größe kann sich ändern)

Der Hauptteilcode der deque iterator ist wie folgt:

/*
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
}

Der Hauptteilcode der deque ist wie folgt:

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

Unten gebe ich Ihnen den Kerncode von dequehauptsächlich über drei Teile:

1. Iterator

2. Wie baut man ein deque

1. Iterator (__deque_iterator)

Das Hauptproblem des Iterators ist, wenn ++, — Iterator zu einem anderen Chunk springen kann (wenn er auf den Rand des Chunks zeigt). Beispielsweise gibt es drei Datenblöcke: chunk 1,chunk 2,chunk 3.

Die pointer1 Hinweise auf den Anfang von chunk 2wenn Betreiber --pointer es zeigt auf das Ende von chunk 1um die pointer2.

Im Folgenden werde ich die Hauptfunktion von angeben __deque_iterator:

Springen Sie zunächst zu einem beliebigen Chunk:

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

Notiere dass der chunk_size() Funktion, die die Chunk-Größe berechnet, können Sie sich vorstellen, dass sie hier zur Vereinfachung 8 zurückgibt.

operator* Holen Sie sich die Daten im Chunk

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

operator++, --

// Präfixformen des Inkrements

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

Iterator überspringt n Schritte / Direktzugriff

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. Wie konstruiere ich a deque

gemeinsame Funktion von 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();
}

Angenommen i_deque hat 20 int-Elemente 0~19 dessen Chunk-Größe 8 ist, und push_back nun 3 Elemente (0, 1, 2) an i_deque:

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

Es ist interne Struktur wie unten:

Dann push_back erneut, es wird aufgerufen, einen neuen Chunk zuzuweisen:

push_back(3)

Wenn wir push_frontes wird ein neuer Chunk vor dem vorherigen zugewiesen start

Notieren Sie wann push_back Element in deque, wenn alle Maps und Chunks gefüllt sind, wird es eine neue Map zuweisen und Chunks anpassen. Aber der obige Code könnte ausreichen, um Sie zu verstehen deque.

Stellen Sie es sich als Vektor von Vektoren vor. Nur sind sie nicht Standard std::vectorS.

Der äußere Vektor enthält Zeiger auf die inneren Vektoren. Wenn seine Kapazität durch Neuzuweisung geändert wird, anstatt den gesamten leeren Speicherplatz bis zum Ende zuzuweisen std::vector tut, wird der leere Raum am Anfang und am Ende des Vektors in gleiche Teile geteilt. Dies erlaubt push_front und push_back auf diesem Vektor, um beide in amortisierter Zeit O(1) aufzutreten.

Das Verhalten des inneren Vektors muss sich ändern, je nachdem, ob es vorne oder hinten ist deque. Auf der Rückseite kann es sich wie ein Standard verhalten std::vector wo es am Ende wächst, und push_back tritt in O(1)-Zeit auf. An der Front muss es das Gegenteil tun, am Anfang mit jedem wachsen push_front. In der Praxis wird dies leicht erreicht, indem dem vorderen Element ein Zeiger und die Wachstumsrichtung zusammen mit der Größe hinzugefügt werden. Mit dieser einfachen Modifikation push_front kann auch O(1)-Zeit sein.

Der Zugriff auf ein beliebiges Element erfordert das Versetzen und Dividieren auf den richtigen äußeren Vektorindex, der in O (1) auftritt, und das Indizieren in den inneren Vektor, der ebenfalls O (1) ist. Dies setzt voraus, dass die inneren Vektoren alle eine feste Größe haben, mit Ausnahme derjenigen am Anfang oder am Ende von deque.

deque = doppelseitige Warteschlange

Ein Behälter, der in beide Richtungen wachsen kann.

Deque ist typisch umgesetzt als vector von vectors (Eine Liste von Vektoren kann keinen konstanten zufälligen Zugriff geben). Während die Größe der sekundären Vektoren implementierungsabhängig ist, besteht ein üblicher Algorithmus darin, eine konstante Größe in Bytes zu verwenden.

Ich habe “Datenstrukturen und Algorithmen in C++” von Adam Drozdek gelesen und fand das nützlich. HTH.

Ein sehr interessanter Aspekt von STL deque ist seine Implementierung. Eine STL-Deque wird nicht als verknüpfte Liste implementiert, sondern als ein Array von Zeigern auf Blöcke oder Arrays von Daten. Die Anzahl der Blöcke ändert sich dynamisch je nach Speicherbedarf, und die Größe des Arrays von Zeigern ändert sich entsprechend.

Sie können in der Mitte das Array von Zeigern auf die Daten (Chunks auf der rechten Seite) sehen, und Sie können auch feststellen, dass sich das Array in der Mitte dynamisch ändert.

Ein Bild sagt mehr als tausend Worte.

Während der Standard keine bestimmte Implementierung vorschreibt (nur wahlfreien Zugriff zu konstanter Zeit), wird eine Deque normalerweise als Sammlung zusammenhängender Speicher-“Seiten” implementiert. Neue Seiten werden nach Bedarf zugewiesen, aber Sie haben immer noch wahlfreien Zugriff. nicht wie std::vectorwird Ihnen nicht versprochen, dass Daten zusammenhängend gespeichert werden, aber wie bei Vektoren erfordern Einfügungen in der Mitte viele Verschiebungen.

deque könnte als Ringpuffer mit einem Array fester Größe implementiert werden:

• Verwenden Sie einen Ringpuffer, damit wir an beiden Enden wachsen/schrumpfen können, indem wir ein Array fester Größe mit O(1)-Komplexität hinzufügen/entfernen
• Verwenden Sie ein Array mit fester Größe, damit der Index einfach berechnet werden kann. Daher greifen Sie über den Index mit zwei Zeigerdereferenzen zu – auch O (1).