STL deque accesso tramite indice è O(1)?

Question

Ho letto che l'accesso a elementi di posizione indice può essere fatto in un tempo costante in un STL deque.Per quanto ne so, gli elementi in una deque possono essere memorizzati in diversi non-luoghi contigui, eliminando l'accesso sicuro attraverso aritmetica dei puntatori.Per esempio:

abc->defghi->jkl->mnop

Gli elementi del deque sopra consiste di un singolo carattere.Il set di caratteri in un gruppo indicare che è allocato in memoria contigua (ad es.abc è in un unico blocco di memoria, defhi si trova in un altro blocco di memoria, etc.).Qualcuno può spiegare come si accede dalla posizione di indice può essere fatto in un tempo costante, soprattutto se l'elemento a cui accedere è nel secondo blocco?O è una deque un puntatore al gruppo di blocchi?

Aggiornamento:O c'è qualche altro di attuazione comune per una deque?

Answer 1

Ho trovato questa implementazione deque da Wikipedia :

Memorizzazione contenuti in più array piccole, ripartizione array aggiuntivi all'inizio o alla fine come necessario. Indicizzazione è implementato mantenendo un array dinamico contenente puntatori a ciascuna delle matrici più piccole.

Credo che risponde alla mia domanda.

Answer 2

I dati in deque vengono memorizzati chuncks di vettore dimensioni fisse, che sono

pointered da un map (che è anche un pezzo di vettore, ma le sue dimensioni possono cambiare)

Il codice parte principale del deque iterator è il seguente:

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

Il codice parte principale del deque è il seguente:

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

Di seguito vi darò il codice di base di deque, principalmente di due parti:

1. iteratore

2. Come l'accesso a caso un deque realizzare

1. iterator (__deque_iterator)

Il problema principale è iteratore, quando ++, - iteratore, si può passare alla altro pezzo (se puntatore al bordo del pezzo). Per esempio, ci sono tre blocchi di dati: chunk 1, chunk 2, chunk 3

.

I puntatori pointer1 alla iniziano di chunk 2, quando l'operatore --pointer sarà puntatore al fine di chunk 1, così come per la pointer2.

Qui di seguito vi darò la funzione principale di __deque_iterator:

In primo luogo, passare a qualsiasi pezzo:

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

Si noti che la funzione chunk_size() cui calcolare la dimensione del blocco, si può pensare di restituisce 8 per semplificare qui.

operator* ottenere i dati nel blocco

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

operator++, --

// forme prefisso di incremento

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 saltare n passi / accesso casuale

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. elementi ad accesso casuale deque

funzione comune di 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];
}

Si vede anche a questa domanda che danno il codice principale del deque

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

Answer 3

Uno dei possibili attuazione può essere un array dinamico di array const dimensioni; tale matrice const dimensioni può essere aggiunto al fine quando è necessario più spazio. Tutte le matrici sono pieni tranne, forse, per la prima e gli ultimi che possono essere parzialmente vuoto. Ciò significa che conoscendo la dimensione di ogni matrice e il numero degli elementi utilizzati nella prima matrice si può facilmente trovare una posizione di un elemento da indice.
http: // cpp- tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html

Answer 4

Se deque è implementato come un buffer circolare in cima std::vector, che rialloca sé, quando si cresce in dimensioni, quindi accesso tramite indice è infatti O(1).

La norma fornisce la prova che tale adempimento è stato significato, o almeno lo è conforme alla norma nella complessità delle stime.Clausole 23.2.1.3/4 e 23.2.1.3/5 richiede che

• inserendo all'inizio o alla fine di una deque richiedono la costante di tempo, mentre l'inserimento di mezzo richiede tempo lineare di deque dimensioni

• durante la cancellazione di elementi del deque, si può chiamare come molti operatori di assegnazione, come la distanza tra gli elementi cancellati alla fine del deque è.

E, naturalmente, non si dovrebbe contare su di requisiti standard invece della propria visione su come contenitori e algoritmi potrebbero essere attuate.

NOTA che la norma richiede più di questi due punti sopra elencati.Si pone anche il requisito che i riferimenti a elementi deve rimanere valido tra le inserzioni per il posteriore o anteriore del deque.Questo può essere soddisfatta se il buffer circolare che contiene i puntatori agli elementi effettivi piuttosto che gli elementi stessi.Comunque, la mia risposta dimostra solo l'idea che più implementazioni possono soddisfare determinati requisiti.