Was ist wirklich eine Deque in STL?

Ich habe mir STL-Container angesehen und versucht herauszufinden, was sie wirklich sind (dh die verwendete Datenstruktur), und die Deque hat mich aufgehalten: Ich dachte zuerst, dass es sich um eine doppelt verknüpfte Liste handelt, die das Einfügen und Löschen von beiden Seiten in ermöglicht konstante Zeit, aber ich bin beunruhigt über das Versprechen des Betreibers [], in konstanter Zeit zu tun. In einer verknüpften Liste sollte der willkürliche Zugriff O (n) sein, oder?

Und wenn es sich um ein dynamisches Array handelt, wie kann es Elemente in konstanter Zeit hinzufügen ? Es sollte erwähnt werden, dass eine Neuzuweisung auftreten kann und dass O (1) wie bei einem Vektor amortisierte Kosten sind .

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 wird eine doppelendige Warteschlange mit Blöcken fester Größe verwaltet. Jeder Block ist ein Vektor, und die Warteschlange („Karte“ in der Grafik unten) der Blöcke selbst ist ebenfalls ein Vektor.

Es gibt eine großartige Analyse der Leistungsmerkmale und des Vergleichs mit dem vectorOver bei CodeProject .

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

Stellen Sie es sich als einen Vektor von Vektoren vor. Nur sind sie keine 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 Raum dem Ende std::vectorzuzuweisen, teilt er den leeren Raum am Anfang und am Ende des Vektors zu gleichen Teilen auf. Dies ermöglicht push_frontund push_backauf diesem Vektor können beide in der amortisierten O (1) -Zeit auftreten.

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

Der Zugriff auf ein Element erfordert das Versetzen und Teilen 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 des deque.

deque = doppelte Warteschlange

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

Deque wird normalerweise als vectorvon implementiert vectors(eine Liste von Vektoren kann keinen zeitlich konstanten Direktzugriff ermöglichen). Während die Größe der Sekundärvektoren implementierungsabhängig ist, besteht ein üblicher Algorithmus darin, eine konstante Größe in Bytes zu verwenden.

(Dies ist eine Antwort, die ich in einem anderen Thread gegeben habe . Im Wesentlichen argumentiere ich, dass selbst ziemlich naive Implementierungen, die eine einzige verwenden vector, den Anforderungen von "konstantem nicht amortisiertem push_ {front, back}" entsprechen. Sie könnten überrascht sein und denke, dass dies unmöglich ist, aber ich habe andere relevante Zitate im Standard gefunden, die den Kontext auf überraschende Weise definieren. Bitte nehmen Sie mit, wenn ich in dieser Antwort einen Fehler gemacht habe, wäre es sehr hilfreich zu identifizieren, welche Dinge Ich habe richtig gesagt und wo meine Logik zusammengebrochen ist.)

In dieser Antwort versuche ich nicht, eine gute Implementierung zu identifizieren , sondern nur zu helfen, die Komplexitätsanforderungen im C ++ - Standard zu interpretieren. Ich zitiere aus N3242 , das laut Wikipedia das neueste frei verfügbare C ++ 11-Standardisierungsdokument ist. (Es scheint anders organisiert zu sein als der endgültige Standard, und daher werde ich die genauen Seitenzahlen nicht angeben. Natürlich haben sich diese Regeln im endgültigen Standard möglicherweise geändert, aber ich glaube nicht, dass dies geschehen ist.)

A deque<T>könnte mit a korrekt implementiert werden vector<T*>. Alle Elemente werden auf den Heap kopiert und die Zeiger in einem Vektor gespeichert. (Mehr zum Vektor später).

Warum T*statt T? Weil der Standard das verlangt

"Eine Einfügung an beiden Enden der Deque macht alle Iteratoren der Deque ungültig, hat jedoch keine Auswirkung auf die Gültigkeit von Verweisen auf Elemente der Deque. "

(meine Betonung). Das T*hilft, das zu befriedigen. Es hilft uns auch, dies zu befriedigen:

"Das Einfügen eines einzelnen Elements entweder am Anfang oder am Ende einer Deque führt immer zu einem einzelnen Aufruf eines Konstruktors von T. "

Nun zum (kontroversen) Teil. Warum ein verwenden vector, um das zu speichern T*? Es gibt uns zufälligen Zugriff, was ein guter Anfang ist. Vergessen wir für einen Moment die Komplexität des Vektors und bauen wir sorgfältig darauf auf:

Der Standard spricht von "der Anzahl der Operationen an den enthaltenen Objekten". Für deque::push_frontdiese deutlich 1 , da genau ist TGegenstand ist so konstruiert und Null der bestehenden TObjekte gelesen werden oder in irgendeiner Weise abgetastet. Diese Zahl 1 ist eindeutig eine Konstante und unabhängig von der Anzahl der Objekte, die sich derzeit in der Deque befinden. Dies erlaubt uns zu sagen, dass:

"Für uns deque::push_frontist die Anzahl der Operationen an den enthaltenen Objekten (dem Ts) festgelegt und unabhängig von der Anzahl der Objekte, die sich bereits in der Deque befinden."

Natürlich wird sich die Anzahl der Operationen auf dem T*nicht so gut benehmen. Wenn das vector<T*>zu groß wird, wird es neu zugewiesen und viele T*s werden kopiert. Ja, die Anzahl der Operationen auf dem T*wird stark variieren, aber die Anzahl der Operationen auf Twird nicht beeinflusst.

Warum interessiert uns diese Unterscheidung zwischen Zählvorgängen Tund Zählvorgängen T*? Es ist, weil der Standard sagt:

Alle Komplexitätsanforderungen in dieser Klausel werden ausschließlich in Bezug auf die Anzahl der Operationen an den enthaltenen Objekten angegeben.

Für die dequesind die enthaltenen Objekte die T, nicht die T*, was bedeutet, dass wir jede Operation ignorieren können, die a kopiert (oder neu zuordnet) T*.

Ich habe nicht viel darüber gesagt, wie sich ein Vektor in einer Deque verhalten würde. Vielleicht würden wir es als kreisförmigen Puffer interpretieren (wobei der Vektor immer sein Maximum capacity()einnimmt und dann alles in einen größeren Puffer umverteilt, wenn der Vektor voll ist. Die Details spielen keine Rolle.

In den letzten Absätzen haben wir deque::push_frontdie Beziehung zwischen der Anzahl der Objekte in der Deque und der Anzahl der Operationen, die push_front für enthaltene TObjekte ausführt, analysiert. Und wir fanden heraus, dass sie unabhängig voneinander waren. Da der Standard vorschreibt, dass Komplexität in Bezug auf den Betrieb im Betrieb ist T, können wir sagen, dass dies eine konstante Komplexität aufweist.

Ja, die Operations-On-T * -Komplexität wird (aufgrund der vector) amortisiert , aber wir sind nur an der Operations-On-T-Komplexität interessiert und diese ist konstant (nicht amortisiert).

Die Komplexität von vector :: push_back oder vector :: push_front spielt bei dieser Implementierung keine Rolle. Diese Überlegungen betreffen Operationen an T*und sind daher irrelevant. Wenn sich der Standard auf den "konventionellen" theoretischen Begriff der Komplexität beziehen würde, hätten sie sich nicht explizit auf die "Anzahl der Operationen an den enthaltenen Objekten" beschränkt. Interpretiere ich diesen Satz über?

Aus der Übersicht können Sie dequeals denkendouble-ended queue

Die Daten in dequewerden durch Chuncks mit festem Vektor gespeichert, die sind

Zeiger durch a map(das ist auch ein Stück Vektor, aber seine Größe kann sich ändern)

Der Hauptteilcode von deque iteratorlautet 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 von dequelautet 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;
}

Im Folgenden werde ich Ihnen den Kerncode von dequehauptsächlich drei Teilen geben:

1. Iterator

2. Wie konstruiere ich eine deque

1. iterator ( __deque_iterator)

Das Hauptproblem des Iterators besteht darin, dass er beim ++, - Iterator möglicherweise zu einem anderen Block springt (wenn er auf die Kante des Blocks zeigt). Zum Beispiel gibt es drei Datenabschnitte: chunk 1, chunk 2, chunk 3.

Die pointer1Zeiger auf den Anfang von chunk 2, wenn der Operator --pointerauf das Ende von zeigt chunk 1, auf den pointer2.

Im Folgenden werde ich die Hauptfunktion von geben __deque_iterator:

Überspringen Sie zunächst einen beliebigen Abschnitt:

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

Beachten Sie, dass die chunk_size()Funktion, die die Blockgröße berechnet, zur Vereinfachung 8 zurückgibt.

operator* Holen Sie sich die Daten in den Block

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

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

Nehmen wir an, es i_dequegibt 20 int-Elemente mit einer 0~19Blockgröße von 8 und jetzt push_back 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:

Drücken Sie dann erneut push_back, um einen neuen Block zuzuweisen:

push_back(3)

Wenn wir push_front, wird es neuen Block vor dem vorherigen zuweisenstart

Beachten Sie, dass beim push_backElement in deque, wenn alle Karten und Blöcke gefüllt sind, eine neue Karte zugewiesen und Blöcke angepasst werden. Der obige Code kann jedoch ausreichen, um Sie zu verstehen deque.

Ich habe "Datenstrukturen und Algorithmen in C ++" von Adam Drozdek gelesen und fand dies 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 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 Zeigerarrays ändert sich entsprechend.

Sie können in der Mitte das Array von Zeigern auf die Daten (Blöcke rechts) feststellen, 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 zeitlich konstanter Direktzugriff), wird eine Deque normalerweise als Sammlung zusammenhängender "Speicherseiten" implementiert. Neue Seiten werden nach Bedarf zugewiesen, Sie haben jedoch weiterhin wahlfreien Zugriff. Im Gegensatz dazu std::vectorwird Ihnen nicht versprochen, dass Daten zusammenhängend gespeichert werden, aber wie bei einem Vektor erfordern Einfügungen in der Mitte viele Verschiebungen.