¿Qué es realmente un deque en STL?

192

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.

Zonko
fuente
44
posible duplicado de STL deque acceder por índice es O (1)?
fredoverflow
1
@Graham "dequeue" es otro nombre común para "deque". Todavía he aprobado la edición ya que "deque" suele ser el nombre canónico.
Konrad Rudolph
@ Konrad Gracias. La pregunta era específicamente sobre el deque C ++ STL, que usa la ortografía más corta.
Graham Borland
2
dequesignifica cola doblemente terminada , aunque obviamente el requisito estricto de acceso O (1) a elementos intermedios es particular de C ++
Matthieu M.

Respuestas:

181

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.

esquema del diseño de memoria de una deque

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

Konrad Rudolph
fuente
27
Esa es la definición de una deque tal como la aprendí, pero de esta manera, no puede garantizar el acceso constante al tiempo, por lo que debe faltar algo.
stefaanv
14
@stefaanv, @Konrad: las implementaciones de C ++ que he visto utilizan una matriz de punteros a matrices de tamaño fijo. Esto significa efectivamente que push_front y push_back no son realmente tiempos constantes, pero con factores de crecimiento inteligentes, aún se amortizan tiempos constantes, por lo que O (1) no es tan erróneo, y en la práctica es más rápido que el vector porque está intercambiando punteros individuales en lugar de objetos completos (y menos punteros que objetos).
Matthieu M.
55
El acceso en tiempo constante todavía es posible. Simplemente, si necesita asignar un nuevo bloque en el frente, empuje hacia atrás un nuevo puntero en el vector principal y cambie todos los punteros.
Xeo
44
Si el mapa (la cola en sí) era una lista de doble extremo, no veo cómo podría permitir el acceso aleatorio O (1). Podría implementarse como un búfer circular, lo que permitiría que el cambio de tamaño del búfer circular sea más eficiente: solo copie los punteros en lugar de todos los elementos en la cola. Aún así, parece ser un pequeño beneficio.
Wernight
14
@JeremyWest ¿Por qué no? El acceso indexado va al elemento i% B-th en el bloque i / B-th (B = tamaño de bloque), eso es claramente O (1). Puede agregar un nuevo bloque en O (1) amortizado, por lo tanto, agregar elementos es O (1) amortizado al final. Agregar un nuevo elemento al principio es O (1) a menos que sea necesario agregar un nuevo bloque. Agregar un nuevo bloque al principio no es O (1), es cierto, es O (N), pero en realidad tiene un factor constante muy pequeño ya que solo necesita mover punteros N / B en lugar de N elementos.
Konrad Rudolph
22

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.

Mark Ransom
fuente
1
Puede describir los vectores internos como de capacidad
Caleth
18

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.

Alok Save
fuente
66
No son del todo vectores internos. Las estructuras internas pueden tener capacidad asignada pero no utilizada al principio y al final
Mooing Duck
@MooingDuck: es una implementación definida realmente. Puede ser una matriz de matrices o vectores de vectores o cualquier cosa que pueda proporcionar el comportamiento y la complejidad exigidos por el estándar.
Alok Save
1
@Als: No pienso arrayen nada ni vectoren nada que pueda prometer O(1)push_front amortizado . El interior de las dos estructuras, al menos, debe poder tener un O(1)push_front, que ni un arrayni un vectorpueden garantizar.
Mooing Duck
44
@MooingDuck ese requisito se cumple fácilmente si el primer fragmento crece de arriba hacia abajo en lugar de de abajo hacia arriba. Obviamente, un estándar vectorno hace eso, pero es una modificación lo suficientemente simple como para que sea así.
Mark Ransom
3
@ Mooing Duck, tanto push_front como push_back se pueden hacer fácilmente en O (1) amortizado con una sola estructura vectorial. Es solo un poco más de contabilidad de un búfer circular, nada más. Suponga que tiene un vector regular de capacidad 1000 con 100 elementos en las posiciones 0 a 99. Ahora, cuando ocurre un push_Front, simplemente empuja al final, es decir, en la posición 999, luego 998, etc., hasta que los dos extremos se encuentran. Luego se reasigna (con un crecimiento exponencial para garantizar la amortización de tiempos constantes) tal como lo haría con un vector ordinario. Así que efectivamente solo necesitas un puntero adicional para el primer EL.
plamenko
14

(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?

Aaron McDaid
fuente
8
¡Me parece mucho hacer trampa! Cuando especifica la complejidad de una operación, no lo hace solo en alguna parte de los datos: desea tener una idea del tiempo de ejecución esperado de la operación que está llamando, independientemente de en qué opere. Si sigo su lógica sobre las operaciones en T, significaría que podría verificar si el valor de cada T * es un número primo cada vez que se realiza una operación y aún así respetar el estándar ya que no toca Ts. ¿Podría especificar de dónde provienen sus citas?
Zonko
2
Creo que los escritores estándar saben que no pueden usar la teoría de la complejidad convencional porque no tenemos un sistema completamente especificado en el que sepamos, por ejemplo, la complejidad de la asignación de memoria. No es realista pretender que se puede asignar memoria para un nuevo miembro de un, listindependientemente del tamaño actual de la lista; Si la lista es demasiado grande, la asignación será lenta o fallará. Por lo tanto, hasta donde puedo ver, el comité tomó la decisión de especificar solo las operaciones que pueden contarse y medirse objetivamente. (PD: Tengo otra teoría sobre esto para otra respuesta.)
Aaron McDaid
Estoy bastante seguro de que O(n)el número de operaciones es asintóticamente proporcional al número de elementos. IE, las metaoperaciones cuentan. De lo contrario, no tendría sentido limitar la búsqueda O(1). Ergo, las listas enlazadas no califican.
Mooing Duck
8
Esta es una interpretación muy interesante, pero según esta lógica también listpodría implementarse como un vectorpuntero (las inserciones en el medio darán como resultado una invocación de constructor de copia única , independientemente del tamaño de la lista, y la O(N)combinación aleatoria de los punteros puede ignorarse porque no son operaciones en T).
Mankarse
1
Este es un buen lenguaje de abogacía (aunque no voy a tratar de averiguar si es realmente correcto o si hay algún punto sutil en el estándar que prohíbe esta implementación). Pero no es información útil en la práctica, porque (1) las implementaciones comunes no se implementan de dequeesta manera y (2) "engañan" de esta manera (incluso si lo permite el estándar) cuando calcular la complejidad algorítmica no es útil para escribir programas eficientes .
Kyle Strand
13

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

resumen deque

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)

estructura interna deque

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.

ingrese la descripción de la imagen aquí

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;
}
Saltar iterador n pasos / acceso aleatorio
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:

ingrese la descripción de la imagen aquí

Luego push_back nuevamente, invocará asignar nuevo fragmento:

push_back(3)

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

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.

Jayhello
fuente
Usted mencionó: "Tenga en cuenta que cuando el elemento push_back esté en deque, si se rellenan todos los mapas y fragmentos, se asignará un nuevo mapa y se ajustarán los fragmentos". Me pregunto por qué el estándar C ++ dice "[26.3.8.4.3] Insertar un solo elemento al principio o al final de una deque siempre lleva tiempo constante" en N4713. Asignar una tirada de datos lleva más de un tiempo constante. ¿No?
HCSF
7

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.

ingrese la descripción de la imagen aquí

Keloo
fuente
1
Gracias por recomendar un libro. Leí la dequeparte y está bastante bien.
Rick
@ Rick feliz de escuchar eso. Recuerdo excavar en la deque en algún momento porque no podía entender cómo se puede tener acceso aleatorio (operador []) en O (1). También probar que (push / pop) _ (back / front) ha amortizado la complejidad de O (1) es un interesante 'aha moment'.
Keloo
6

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.

Kerrek SB
fuente
44
o las eliminaciones en el medio requieren mucha reubicación
Mark Hendrickson
Si insertrequiere mucha reubicación, ¿cómo muestra aquí el experimento 4 una asombrosa diferencia entre vector::insert()y deque::insert()?
Bula
1
@Bula: ¿Quizás debido a la falta de comunicación de los detalles? La complejidad de la inserción de deque es "lineal en el número de elementos insertados más la menor de las distancias al comienzo y al final de la deque". Para sentir este costo, debe insertar en el medio actual; ¿Es eso lo que está haciendo su punto de referencia?
Kerrek SB
@KerrekSB: se hizo referencia al artículo con referencia en la respuesta de Konrad anterior. En realidad no noté la sección de comentarios del artículo a continuación. En el hilo '¿Pero deque tiene tiempo de inserción lineal?' El autor mencionó que utilizó la inserción en la posición 100 a través de todas las pruebas, lo que hace que los resultados sean un poco más comprensibles.
Bula