Was ist eigentlich ein Deque in STL?

Lesezeit: 14 Minuten

Was ist eigentlich ein Deque in STL
Zonko

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.

  • Mögliches Duplikat des STL-Deque-Zugriffs nach Index ist O (1)?

    – fredoverflow

    9. Juni 2011 um 12:02 Uhr

  • @Graham „dequeue“ ist ein anderer gebräuchlicher Name für „deque“. Ich habe die Bearbeitung trotzdem genehmigt, da „deque“ normalerweise der kanonische Name ist.

    – Konrad Rudolf

    9. Juni 2011 um 12:09 Uhr

  • @ Konrad Danke. Die Frage bezog sich speziell auf die C++-STL-Deque, die die kürzere Schreibweise verwendet.

    – Graham Borland

    9. Juni 2011 um 12:11 Uhr


  • deque steht für doppelte Warteschlangeobwohl die strenge Anforderung des O(1)-Zugriffs auf mittlere Elemente offensichtlich spezifisch für C++ ist

    – Matthias M.

    9. Juni 2011 um 12:11 Uhr

Was ist eigentlich ein Deque in STL
Konrad Rudolf

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.

Schematische Darstellung des Speicherlayouts einer Deque

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

  • Das ist die Definition einer Deque, wie ich sie gelernt habe, aber auf diese Weise kann sie keinen konstanten Zeitzugriff garantieren, also muss etwas fehlen.

    – stefaanv

    9. Juni 2011 um 12:02 Uhr

  • @stefaanv, @Konrad: C++-Implementierungen, die ich gesehen habe, haben ein Array von Zeigern auf Arrays mit fester Größe verwendet. Dies bedeutet effektiv, dass push_front und push_back keine wirklich konstanten Zeiten sind, aber mit intelligenten Wachstumsfaktoren erhalten Sie dennoch amortisierte konstante Zeiten, sodass O (1) nicht so fehlerhaft ist und in der Praxis schneller als Vektor ist, weil Sie tauschen einzelne Zeiger statt ganze Objekte (und weniger Zeiger als Objekte).

    – Matthias M.

    9. Juni 2011 um 12:17 Uhr

  • Ein ständiger Zugriff ist weiterhin möglich. Wenn Sie einfach einen neuen Block im Vordergrund zuweisen müssen, schieben Sie einen neuen Zeiger auf den Hauptvektor zurück und verschieben Sie alle Zeiger.

    – Xeo

    9. Juni 2011 um 12:19 Uhr

  • Wenn die Karte (die Warteschlange selbst) eine doppelseitige Liste wäre, sehe ich nicht, wie sie O (1) wahlfreien Zugriff ermöglichen könnte. Es könnte als Ringpuffer implementiert werden, was eine effizientere Größenänderung des Ringpuffers ermöglichen würde: Kopieren Sie nur die Zeiger anstelle aller Elemente in der Warteschlange. Trotzdem scheint das ein kleiner Vorteil zu sein.

    – Wernacht

    17. Februar 2013 um 13:03 Uhr


  • @JeremyWest Warum nicht? Der indizierte Zugriff geht auf das i%B-te Element im i/B-ten Block (B = Blockgröße), das ist eindeutig O(1). Sie können einen neuen Block in amortisiertem O (1) hinzufügen, daher wird das Hinzufügen von Elementen am Ende amortisiert O (1). Das Hinzufügen eines neuen Elements am Anfang ist O(1), es sei denn, es muss ein neuer Block hinzugefügt werden. Das Hinzufügen eines neuen Blocks am Anfang ist nicht O (1), es ist zwar O (N), aber in Wirklichkeit hat es einen sehr kleinen konstanten Faktor, da Sie nur N / B-Zeiger anstelle von N Elementen verschieben müssen.

    – Konrad Rudolf

    30. Mai 2014 um 8:31 Uhr

Was ist eigentlich ein Deque in STL
Jayhallo

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

Deque-Übersicht

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)

deque interne Struktur

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.

Geben Sie hier die Bildbeschreibung ein

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:

Geben Sie hier die Bildbeschreibung ein

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

push_back(3)

Geben Sie hier die Bildbeschreibung ein

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

Geben Sie hier die Bildbeschreibung ein

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.

  • Sie haben erwähnt: “Beachten Sie, wenn das push_back-Element in deque, wenn alle Karten und Chunks gefüllt sind, eine neue Karte zugewiesen und Chunks angepasst werden.” Ich frage mich, warum der C++-Standard sagt: “[26.3.8.4.3] Das Einfügen eines einzelnen Elements entweder am Anfang oder am Ende einer Deque dauert immer konstant” in N4713. Das Zuweisen eines Datenblocks dauert mehr als eine konstante Zeit. Nein?

    – HCSF

    27. Juni 2020 um 3:36 Uhr

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.

  • Sie können die inneren Vektoren als fest beschreiben Kapazität

    – Caleth

    15. Juli 2019 um 9:42 Uhr


1646899224 477 Was ist eigentlich ein Deque in STL
Alok Speichern

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.

  • Es kommt mir sehr nach Betrug vor! Wenn Sie die Komplexität einer Operation angeben, tun Sie dies nicht nur für einen Teil der Daten: Sie möchten eine Vorstellung von der erwarteten Laufzeit der aufgerufenen Operation haben, unabhängig davon, was sie verarbeitet. Wenn ich Ihrer Logik zu Operationen mit T folge, würde dies bedeuten, dass Sie bei jeder Ausführung einer Operation überprüfen könnten, ob der Wert jedes T * eine Primzahl ist, und dennoch den Standard respektieren, da Sie Ts nicht berühren. Können Sie angeben, woher Ihre Zitate stammen?

    – Zonko

    28. Dezember 2011 um 9:52 Uhr


  • Ich denke, die Standardautoren wissen, dass sie die herkömmliche Komplexitätstheorie nicht anwenden können, weil wir kein vollständig spezifiziertes System haben, in dem wir beispielsweise die Komplexität der Speicherzuweisung kennen. Es ist nicht realistisch, so zu tun, als könne einem neuen Mitglied von a Speicher zugewiesen werden list unabhängig von der aktuellen Größe der Liste; Wenn die Liste zu groß ist, ist die Zuordnung langsam oder schlägt fehl. Daher hat der Ausschuss meines Erachtens entschieden, nur die Operationen zu spezifizieren, die objektiv gezählt und gemessen werden können. (PS: Ich habe Ein weiterer Theorie dazu für eine andere Antwort.)

    – Aaron McDaid

    28. Dezember 2011 um 16:52 Uhr


  • Dies ist eine sehr interessante Interpretation, aber nach dieser Logik a list könnte als implementiert werden vector von Zeigern (Einfügungen in die Mitte führen zu a Einzel Kopieren des Konstruktoraufrufs, unabhängig von der Listengröße, und die O(N) das Mischen der Zeiger kann ignoriert werden, da es sich nicht um Operationen auf T handelt).

    – Mankarse

    11. März 2012 um 14:18 Uhr

  • Das ist nettes Sprachrecht (obwohl ich nicht versuchen werde, herauszufinden, ob es tatsächlich richtig ist oder ob es einen subtilen Punkt im Standard gibt, der diese Implementierung verbietet). In der Praxis sind dies jedoch keine nützlichen Informationen, da (1) gängige Implementierungen nicht implementiert werden deque auf diese Weise und (2) auf diese Weise “schummeln” (auch wenn der Standard dies zulässt), wenn die Berechnung algorithmischer Komplexität beim Schreiben effizienter Programme nicht hilfreich ist.

    – Kyle Strand

    22. Dezember 2015 um 19:31 Uhr

  • @Kyle Strand, gängige Implementierungen ersetzen Zeiger auf einzelne Ts durch Zeiger auf im Wesentlichen feste Arrays von Ts (plus eine winzige Menge an Buchhaltungsdaten, die entweder zusammen mit den Zeigern oder mit den Arrays aufbewahrt werden). Sie haben immer noch die gleichen asymptotischen Eigenschaften, nur Konstanten erweisen sich typischerweise als günstiger.

    – seb

    4. Juni 2017 um 16:05 Uhr

1646899224 713 Was ist eigentlich ein Deque in STL
Kelu

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.

Geben Sie hier die Bildbeschreibung ein

  • Vielen Dank für die Buchempfehlung. Ich lese das deque Teil und es ist ziemlich gut.

    – Rick

    9. Dezember 2019 um 1:19 Uhr


  • @Rick freut mich das zu hören. Ich erinnere mich, dass ich irgendwann in die Deque gegraben habe, weil ich nicht verstehen konnte, wie Sie wahlfreien Zugriff haben können ([]Operator) in O(1). Auch der Beweis, dass (push/pop)_(back/front) die O(1)-Komplexität amortisiert hat, ist ein interessanter „Aha-Moment“.

    – Kelu

    9. Dezember 2019 um 18:34 Uhr

1646899225 725 Was ist eigentlich ein Deque in STL
Kerrek SB

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.

  • Vielen Dank für die Buchempfehlung. Ich lese das deque Teil und es ist ziemlich gut.

    – Rick

    9. Dezember 2019 um 1:19 Uhr


  • @Rick freut mich das zu hören. Ich erinnere mich, dass ich irgendwann in die Deque gegraben habe, weil ich nicht verstehen konnte, wie Sie wahlfreien Zugriff haben können ([]Operator) in O(1). Auch der Beweis, dass (push/pop)_(back/front) die O(1)-Komplexität amortisiert hat, ist ein interessanter „Aha-Moment“.

    – Kelu

    9. Dezember 2019 um 18:34 Uhr

1646899226 621 Was ist eigentlich ein Deque in STL
Baiyan Huang

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

986990cookie-checkWas ist eigentlich ein Deque in STL?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy