library - queue c++
¿Qué es realmente un deque en STL? (6)
deque = cola doble final
Un contenedor que puede crecer en cualquier dirección.
Deque se implementa típicamente como un vector de vectors (una lista de vectores no puede dar 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.
Estaba mirando contenedores STL y tratando de entender qué 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 estoy preocupado por la promesa hecha por el operador [] para que se haga en tiempo constante. En una lista vinculada, el acceso arbitrario debe ser O (n), ¿verdad?
Y si se trata de una matriz dinámica, ¿cómo puede agregar elementos en tiempo constante? Debe mencionarse que la reasignación puede ocurrir y que O (1) es un costo amortizado, como para un vector .
Entonces me pregunto qué es esta estructura que permite el acceso arbitrario en tiempo constante y, al mismo tiempo, nunca necesita ser trasladado a un lugar nuevo y más grande.
(Esta es una respuesta que he dado en otro hilo . Básicamente estoy argumentando que incluso las implementaciones bastante ingenuas, usando un solo vector , se ajustan a los requisitos de "push_ {front, back} no amortizado constante". sorprendido, y creo que esto es imposible, pero he encontrado otras citas relevantes en la norma que definen el contexto de una manera sorprendente. Tengan paciencia, si me he equivocado en esta respuesta, sería muy útil identificar cuál cosas que he dicho correctamente y donde mi lógica se ha roto).
En esta respuesta, no estoy tratando de identificar una buena implementación, simplemente estoy tratando de ayudarnos a interpretar los requisitos de complejidad en el estándar C ++. N3242 de N3242 , que es, según Wikipedia , el último documento de estandarización de C ++ 11 disponible gratuitamente. (Parece estar organizado de forma diferente al estándar final, y por lo tanto no citaré los números exactos de las páginas. Por supuesto, estas reglas podrían haber cambiado en el estándar final, pero no creo que eso haya sucedido).
Un deque<T> podría implementarse correctamente utilizando un 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 al deque, pero no tiene ningún efecto sobre la validez de las referencias a elementos del deque " .
(mi énfasis). La T* ayuda a satisfacer eso. También nos ayuda a satisfacer esto:
"Insertar un solo elemento ya sea al principio o al final de un deque siempre ... causa una sola llamada a un constructor de T ".
Ahora para el bit (polémico). ¿Por qué usar un vector para almacenar la T* ? Nos da acceso aleatorio, que es un buen comienzo. Olvidémonos de la complejidad del vector por un momento y construyamos esto cuidadosamente:
El estándar habla sobre "el número de operaciones en los objetos contenidos". Para deque::push_front esto es claramente 1 porque se construye exactamente un objeto T y cero de los objetos T existentes se leen o escanean de cualquier manera. Este número, 1, es claramente una constante y es independiente del número de objetos actualmente en el deque. Esto nos permite decir que:
''Para nuestro deque::push_front , el número de operaciones en los objetos contenidos (los Ts) es fijo y es independiente del número de objetos que ya están en deque.''
Por supuesto, la cantidad de operaciones en la T* no será tan buena. Cuando el vector<T*> crece demasiado, se colocará de nuevo y se copiarán muchas T* s. Entonces sí, el número de operaciones en la T* variará enormemente, pero la cantidad de operaciones en T no se verá afectada.
¿Por qué nos importa esta distinción entre las operaciones de conteo en T y las operaciones de conteo en 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 la deque , los objetos contenidos son la T , no la T* , lo que significa que podemos ignorar cualquier operación que copie (o reasigne) una T* .
No he dicho mucho acerca de cómo se comportaría un vector en una deque. Tal vez lo interpretaríamos como un búfer circular (con el vector siempre ocupando su capacity() máxima capacity() , y luego reasigne todo a un búfer más grande cuando el vector esté lleno. Los detalles no importan.
En los últimos párrafos, hemos analizado deque::push_front y la relación entre el número de objetos en el deque ya y el número de operaciones realizadas por push_front en T objetos- T contenidos. Y descubrimos que eran independientes el uno del otro. Como el estándar exige que la complejidad sea en términos de operaciones en T , podemos decir que tiene una complejidad constante.
Sí, el complejo Operations-On-T * se amortiza (debido al vector ), pero solo nos interesa la complejidad de Operations-On-T y esto es constante (no amortizado).
La complejidad de vector :: push_back o vector :: push_front es irrelevante en esta implementación; esas consideraciones implican operaciones en T* y, por lo tanto, son irrelevantes. Si el estándar se refería a la noción teórica "convencional" de la complejidad, entonces no se habrían limitado explícitamente al "número de operaciones en los objetos contenidos". ¿Estoy sobreinterpretando esa oración?
Estaba leyendo "Estructuras de datos y algoritmos en C ++" de Adam Drozdek, y encontré esto útil. HTH.
Un aspecto muy interesante de STL deque es su implementación. Un deque de STL no se implementa como una lista vinculada sino como una matriz de punteros a bloques o matrices de datos. La cantidad de bloques cambia dinámicamente según las necesidades de almacenamiento, y el tamaño de la matriz de indicadores cambia en consecuencia.
Puede observar en el centro la matriz de punteros a los datos (trozos a la derecha), y también puede observar que la matriz en el medio está cambiando dinámicamente.
Una imagen vale más que mil palabras.
Imagínatelo como un vector de vectores. Solo que no son estándar std::vector s.
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 hace std::vector , divide el espacio vacío en partes iguales al principio y al final del vector. Esto permite que tanto push_front como push_back en este vector ocurran en tiempo O (1) amortizado.
El comportamiento del vector interno debe cambiar dependiendo de si está en la parte frontal o posterior del deque . En la parte posterior puede comportarse como un estándar std::vector donde crece al final, y push_back ocurre en O (1) tiempo. En el frente, tiene que hacer lo contrario, creciendo al principio con cada push_front . En la práctica, esto se logra fácilmente al agregar un puntero al elemento frontal y la dirección de crecimiento junto con el tamaño. Con esta simple modificación push_front también puede ser O (1) vez.
El acceso a cualquier elemento requiere la compensación y la división en el índice vectorial externo adecuado que se produce en O (1), y la 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 del deque .
Si bien el estándar no exige ninguna implementación en particular (solo acceso aleatorio de tiempo constante), un deque generalmente se implementa como una colección de "páginas" de memoria contigua. Las páginas nuevas se asignan según sea necesario, pero aún tiene acceso aleatorio. A diferencia de std::vector , no se promete que los datos se almacenan contiguamente, pero al igual que el vector, las inserciones en el medio requieren mucha reubicación.
Un deque se define de manera recursiva: internamente mantiene una cola de dos extremos de " trozos " ("bloques" en el gráfico a continuación) de tamaño fijo. Cada trozo es un vector, y la cola ("mapa" en el gráfico a continuación) de trozos 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 vector en CodeProject .
La implementación de la biblioteca estándar de GCC usa internamente una T** para representar el mapa. Cada bloque de datos es una T* que se asigna con un tamaño fijo __deque_buf_size (que depende del tamaño de sizeof(T) ).