¿Qué es realmente un deque en STL?

Estaba mirando los contenedores STL y tratando de calcular cuáles son realmente (es decir, la estructura de datos utilizada), y el deque me detuvo: al principio pensé que era una lista de doble enlace, que permitiría la inserción y eliminación de ambos extremos en tiempo constante, pero me preocupa la promesa hecha por el operador [] de hacerse en tiempo constante. En una lista vinculada, el acceso arbitrario debe ser O (n), ¿verdad?

Y si es una matriz dinámica, ¿cómo puede agregar elementos en tiempo constante? Cabe mencionar que puede ocurrir una reasignación, y que O (1) es un costo amortizado, como para un vector .

Entonces, me pregunto cuál es esta estructura que permite el acceso arbitrario en tiempo constante y, al mismo tiempo, nunca necesita ser trasladado a un lugar nuevo más grande.

Una deque se define de forma recursiva: mantiene internamente una cola de doble extremo de fragmentos de tamaño fijo. Cada fragmento es un vector, y la cola ("mapa" en el gráfico a continuación) de los fragmentos en sí también es un vector.

Hay un gran análisis de las características de rendimiento y cómo se compara con el anterior vectoren CodeProject .

La implementación de la biblioteca estándar de GCC usa internamente a T**para representar el mapa. Cada bloque de datos es un T*que se asigna con un tamaño fijo __deque_buf_size(que depende de sizeof(T)).

Imagínelo como un vector de vectores. Solo que no son std::vectors estándar .

El vector externo contiene punteros a los vectores internos. Cuando su capacidad se cambia mediante la reasignación, en lugar de asignar todo el espacio vacío al final como lo std::vectorhace, divide el espacio vacío en partes iguales al principio y al final del vector. Esto permite push_fronty push_backen este vector para tanto se producen en tiempo amortizado O (1).

El comportamiento del vector interno debe cambiar dependiendo de si está en la parte frontal o posterior de la deque. En la parte posterior, puede comportarse como un estándar std::vectordonde crece al final y push_backocurre en el tiempo O (1). En el frente, debe hacer lo contrario, crecer al principio con cada uno push_front. En la práctica, esto se logra fácilmente agregando un puntero al elemento frontal y la dirección de crecimiento junto con el tamaño. Con esta simple modificación push_fronttambién puede ser O (1) tiempo.

El acceso a cualquier elemento requiere compensación y división en el índice del vector externo apropiado que ocurre en O (1), e indexación en el vector interno que también es O (1). Esto supone que los vectores internos son todos de tamaño fijo, excepto los que están al principio o al final de deque.

deque = cola de doble finalización

Un contenedor que puede crecer en cualquier dirección.

Deque generalmente se implementa como un vectorde vectors(una lista de vectores no puede proporcionar acceso aleatorio de tiempo constante). Si bien el tamaño de los vectores secundarios depende de la implementación, un algoritmo común es usar un tamaño constante en bytes.

(Esta es una respuesta que he dado en otro hilo . Esencialmente estoy argumentando que incluso las implementaciones bastante ingenuas, usando una sola vector, se ajustan a los requisitos de "empuje constante no amortizado_ {frente, atrás}". Puede que se sorprenda , y creo que esto es imposible, pero he encontrado otras citas relevantes en el estándar que definen el contexto de una manera sorprendente. Tenga paciencia conmigo; si he cometido un error en esta respuesta, sería muy útil identificar qué cosas He dicho correctamente y dónde se ha roto mi lógica.)

En esta respuesta, no estoy tratando de identificar una buena implementación, solo estoy tratando de ayudarnos a interpretar los requisitos de complejidad en el estándar C ++. Estoy citando de N3242 , que es, según Wikipedia , el último documento de estandarización de C ++ 11 disponible gratuitamente. (Parece estar organizado de manera diferente al estándar final, y por lo tanto no citaré los números de página exactos. Por supuesto, estas reglas podrían haber cambiado en el estándar final, pero no creo que eso haya sucedido).

UNA deque<T> podría implementarse correctamente utilizando a vector<T*>. Todos los elementos se copian en el montón y los punteros se almacenan en un vector. (Más sobre el vector más adelante).

Por qué T* lugar de T? Porque el estándar requiere que

"Una inserción en cualquier extremo del deque invalida todos los iteradores del deque, pero tiene no ningún efecto sobre la validez de las referencias a elementos de la deque " .

(mi énfasis) losT* ayudas para satisfacer eso. También nos ayuda a satisfacer esto:

"Insertar un solo elemento al principio o al final de una deque siempre ..... provoca una sola llamada a un constructor de T ".

Ahora para el bit (controvertido). ¿Por qué usar unvector para almacenar el T*? Nos da acceso aleatorio, que es un buen comienzo. Olvidemos la complejidad del vector por un momento y desarrollemos esto cuidadosamente:

El estándar habla sobre "el número de operaciones en los objetos contenidos". Para deque::push_frontesto es claramente 1 porque exactamente unoT objeto se construye y cero de las existentes Tobjetos se leen o escaneado de ninguna manera. Este número, 1, es claramente una constante y es independiente del número de objetos actualmente en la deque. Esto nos permite decir que:

'Para nuestro deque::push_front , el número de operaciones en los objetos contenidos (el Ts) es fijo y es independiente del número de objetos que ya están en la deque'.

Por supuesto, el número de operaciones en el T*no se comportará tan bien. Cuando vector<T*>crezca demasiado, se reasignará y se copiarán muchos correos electrónicos T*. Entonces, sí, el número de operaciones en el T*variará enormemente, pero el número de operaciones Tno se verá afectado.

¿Por qué nos importa esta distinción entre operaciones de Tconteo y operaciones de conteo T*? Es porque el estándar dice:

Todos los requisitos de complejidad en esta cláusula se establecen únicamente en términos del número de operaciones en los objetos contenidos.

Para el deque, los objetos contenidos son el T, no el T*, lo que significa que podemos ignorar cualquier operación que copia (o reasigna) a T*.

No he dicho mucho sobre cómo se comportaría un vector en una deque. Quizás lo interpretaríamos como un búfer circular (con el vector siempre ocupando su máximocapacity() , y luego reasignar todo en un búfer más grande cuando el vector esté lleno. Los detalles no importan.

En los últimos párrafos, hemos analizado deque::push_fronty la relación entre el número de objetos en la deque ya y el número de operaciones realizadas por push_front en Tobjetos contenidos . Y descubrimos que eran independientes entre sí. Como el estándar exige que la complejidad esté en términos de operaciones en curso T, entonces podemos decir que esto tiene una complejidad constante.

Sí, la Complejidad de Operaciones en T * se amortiza (debido a vector), pero solo nos interesa la Complejidad de Operaciones en T y esta es constante (no amortizada).

La complejidad de vector :: push_back o vector :: push_front es irrelevante en esta implementación; esas consideraciones involucran operaciones T*y, por lo tanto, son irrelevantes. Si el estándar se refería a la noción teórica "convencional" de complejidad, entonces no se habrían restringido explícitamente al "número de operaciones en los objetos contenidos". ¿Estoy sobreinterpretando esa oración?

Desde la perspectiva general, puede pensar dequecomo undouble-ended queue

Los datos en deque son almacenados por fragmentos de vector de tamaño fijo, que son

señalado por un map(que también es un fragmento de vector, pero su tamaño puede cambiar)

El código de la parte principal del deque iteratores el siguiente:

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

El código de la parte principal del dequees el siguiente:

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

A continuación le daré el código central de deque, principalmente sobre tres partes:

1. iterador

2. ¿Cómo construir un deque

1. iterador ( __deque_iterator)

El principal problema del iterador es, cuando ++, - iterator, puede saltar a otro fragmento (si apunta al borde del fragmento). Por ejemplo, hay tres fragmentos de datos: chunk 1, chunk 2, chunk 3.

Los pointer1punteros al comienzo de chunk 2, cuando el operador --pointerapunta al final de chunk 1, con el fin de pointer2.

A continuación daré la función principal de __deque_iterator:

En primer lugar, salta a cualquier fragmento:

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

Tenga en cuenta que, la chunk_size()función que calcula el tamaño del fragmento, puede pensar que devuelve 8 para simplificar aquí.

operator* obtener los datos en el fragmento

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

operator++, --

// formas de incremento de prefijo

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. Cómo construir un deque

función común de 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();
}

Supongamos que i_dequetiene 20 elementos int 0~19cuyo tamaño de fragmento es 8 y ahora push_back 3 elementos (0, 1, 2) para i_deque:

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

Es la estructura interna como a continuación:

Luego push_back nuevamente, invocará asignar nuevo fragmento:

push_back(3)

Si lo hacemos push_front, asignará un nuevo fragmento antes del anteriorstart

Tenga en cuenta que cuando el push_backelemento está en deque, si todos los mapas y fragmentos están llenos, se asignará un nuevo mapa y se ajustarán los fragmentos. Pero el código anterior puede ser suficiente para que usted lo entienda deque.

Estaba leyendo "Estructuras de datos y algoritmos en C ++" por Adam Drozdek, y encontré esto útil. HTH

Un aspecto muy interesante de STL deque es su implementación. Una eliminación de STL no se implementa como una lista vinculada sino como una matriz de punteros a bloques o matrices de datos. El número de bloques cambia dinámicamente según las necesidades de almacenamiento, y el tamaño de la matriz de punteros cambia en consecuencia.

Puede notar que en el medio está la matriz de punteros a los datos (fragmentos a la derecha), y también puede notar que la matriz en el medio está cambiando dinámicamente.

Una imagen vale más que mil palabras.

Si bien el estándar no exige ninguna implementación en particular (solo acceso aleatorio de tiempo constante), una deque generalmente se implementa como una colección de "páginas" de memoria contiguas. Las páginas nuevas se asignan según sea necesario, pero aún tiene acceso aleatorio. diferente astd::vector , no se le promete que los datos se almacenen de manera contigua, pero al igual que los vectores, las inserciones en el medio requieren mucha reubicación.