STL Deque durch den Index zugreift ist O (1)?

Question

Ich habe gelesen, dass Zugriff auf Elemente von Positionsindex können in konstanter Zeit in einem STL deque erfolgen. Soweit ich weiß, Elemente in einer deque kann in mehreren nicht zusammenhängenden Orten gespeichert werden, einen sicheren Zugang durch Pointer-Arithmetik zu beseitigen. Zum Beispiel:

abc-> defghi-> jkl-> mnop

Die Elemente der deque besteht über ein einzelnes Zeichen. Der Satz von Zeichen in einer Gruppe anzuzeigen, dass es in zusammenhängendem Speicher zugeordnet ist (beispielsweise ABC in einem einzigen Speicherblock ist, defhi in einem anderen Block des Speichers angeordnet ist, etc.). Kann mir jemand erklären, wie durch Positionsindex zugreifen kann in konstanter Zeit durchgeführt werden, vor allem, wenn das Element zugegriffen werden soll, im zweiten Block ist? Oder hat ein deque einen Zeiger auf die Gruppe von Blöcken?

Update:? Oder gibt es eine andere gemeinsame Implementierung für eine deque

Answer 1

Ich fand diese deque Implementierung von Wikipedia :

Speicher von Inhalten in mehreren kleineren Arrays, Aufteilung zusätzliche Arrays am Anfang oder Ende nach Bedarf. Indexieren wird implementiert, indem ein dynamisches Array hält Zeiger auf jedem der kleineren Arrays enthält.

Ich denke, es beantwortet meine Frage.

Answer 2

Die Daten in deque durch chuncks feste Größe Vektor gespeichert sind, welche

pointered durch eine map (die auch ein Stück des Vektors ist, aber seine Größe ändern kann)

Der Hauptteil-Code des 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 Hauptteil-Code des 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;
}

Im Folgenden gebe ich Ihnen den Kern-Code von deque, vor allem über zwei Teile:

1. Iterator

2. Wie Random Access ein deque realize

1. Iterator (__deque_iterator)

Das Hauptproblem der Iterator ist, wenn ++, - Iterator, kann es zu anderen chunk überspringen (wenn es zum Rand des chunk pointer). Zum Beispiel gibt es drei Datenabschnitte: chunk 1, chunk 2, chunk 3

.

Die pointer1 Zeiger auf den Beginn von chunk 2, wenn der Bediener --pointer es bis zum Ende der chunk 1 Zeiger, um auf den pointer2.

Im Folgenden werde ich die Hauptfunktion von __deque_iterator geben:

Zunächst fahren Sie mit jedem Brocken:

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 zu berechnen, können Sie denken, davon 8 gibt für simplify hier.

erhalten operator* die Daten im Chunk

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

operator++, --

// Präfix Formen des Schrittweite

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 überspringen n Schritte / random access

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. Random access deque Elemente

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

Sie sehen auch diese Frage, die den Hauptcode von deque geben

https://stackoverflow.com/a/50959796/6329006

Answer 3

Eine der möglichen Implementierung kann ein dynamisches Array von const-sized Arrays; Eine solche const-sized Array kann mit jedem Ende hinzugefügt werden, wenn mehr Platz benötigt wird. Alle die Arrays sind voll außer, vielleicht, für den ersten und den letzten, die leer werden zum Teil können. Das bedeutet, dass die Größe jedes Array und die Anzahl der verwendeten Elemente in der ersten Anordnung eine leicht zu wissen, kann eine Position eines Elements durch den Index finden.
http: // CPP tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html

Answer 4

Wenn deque implementiert ist als ein Ringpuffer oben auf std::vector, die neu verteilt sich, wenn es wächst in Größe, dann mit dem Index den Zugriff auf in der Tat ist O (1).

Die Norm gibt Hinweise darauf, dass eine solche Umsetzung gemeint war - zumindest entspricht es Standard in Komplexität Schätzungen. Klauseln 23.2.1.3/4 und 23.2.1.3/5 erfordern, dass

• Einfügen zum Anfang oder zum Ende einer deque benötigt konstante Zeit, während Einfügung in die Mitte des lineare Zeit von deque Größe erfordert

• , wenn die Elemente von den Deque Löschen, kann es so viele Zuweisungsoperator nennt, wie der Abstand von den Elementen zu dem Ende der Deque gelöscht werden wird.

Und natürlich, Sie auf Standardanforderungen anstelle der eigenen Vision zählen sollen, wie Container und Algorithmen umgesetzt werden könnten.

Hinweis , dass der Standard oben aufgeführten mehr als diese zwei Punkte benötigt. Es stellt auch Voraussetzung, dass die Verweise auf Elemente zwischen Einfügungen auf der Vorder- oder Rückseite des deque gültig bleiben müssen. Dies kann zufrieden sein, wenn der Ringpuffer Zeiger auf die tatsächlichen Elemente eher als die Elemente enthält sich. Wie auch immer, zeigt meine Antwort nur die Idee, dass mehrere Implementierungen bestimmte Anforderungen erfüllen können.