una - ¿Qué estructura de datos, exactamente, son deques en C++?
lenguaje c++ ejemplos (7)
¿Hay una estructura de datos específica que se supone que debe implementar una deque en C ++ STL, o es una deque simplemente esta noción vaga de una matriz cultivable tanto desde el frente como desde la parte posterior, para ser implementada sin importar la implementación que elija?
Siempre solía suponer que un deque era un búfer circular , pero hace poco que estaba leyendo una referencia de C ++, y parece que un deque es una especie de matriz de matrices. No parece que sea un viejo buffer circular simple. ¿Es un búfer de brecha , entonces, o alguna otra variante de matriz cultivable , o solo depende de la implementación?
ACTUALIZACIÓN Y RESUMEN DE RESPUESTAS :
Parece que el consenso general es que un deque es una estructura de datos tal que:
- el tiempo para insertar o eliminar un elemento debe ser constante al comienzo o al final de la lista y, como mucho, lineal en cualquier otro lugar. Si interpretamos que esto significa verdadero tiempo constante y no tiempo constante amortizado, como alguien comenta, esto parece desafiante. Algunos han argumentado que no debemos interpretar que esto significa tiempo constante no amortizado.
- "Una deque requiere que cualquier inserción mantenga válida cualquier referencia a un elemento miembro. Está bien que los iteradores se invaliden, pero los miembros mismos deben permanecer en el mismo lugar en la memoria". Cuando alguien comenta: Esto es bastante fácil simplemente copiando a los miembros en algún lugar en el montón y almacenando T * en la estructura de datos debajo del capó.
- "Insertar un solo elemento al principio o al final de un deque siempre lleva tiempo constante y causa una sola llamada a un constructor de T." El único constructor de T también se logrará si la estructura de datos almacena T * bajo el capó.
- La estructura de datos debe tener acceso aleatorio.
Parece que nadie sabe cómo obtener una combinación de la 1ª y la 4ª condición si tomamos la primera condición como "tiempo constante no amortizado". Una lista enlazada logra 1) pero no 4), mientras que una memoria intermedia circular típica logra 4) pero no 1). Creo que tengo una implementación que cumple ambos a continuación. ¿Comentarios?
Comenzamos con una implementación sugerida por otra persona: asignamos una matriz y comenzamos a colocar elementos desde la mitad, dejando espacio tanto en la parte frontal como posterior. En esta implementación, hacemos un seguimiento de cuántos elementos hay desde el centro en las direcciones frontal y posterior, llamamos esos valores F y B. Luego, aumentemos esta estructura de datos con una matriz auxiliar que es dos veces el tamaño del original array (por lo que ahora estamos desperdiciando un montón de espacio, pero sin cambios en la complejidad asintótica). También llenaremos esta matriz auxiliar desde su centro y le daremos valores similares F ''y B''. La estrategia es esta: cada vez que agregamos un elemento a la matriz primaria en una dirección dada, si F> F ''o B> B'' (dependiendo de la dirección), se copian hasta dos valores de la matriz primaria a la auxiliar. array hasta que F ''alcance F (o B'' con B). Por lo tanto, una operación de inserción implica poner 1 elemento en el conjunto primario y copiar hasta 2 desde el primario al auxiliar, pero sigue siendo O (1). Cuando la matriz primaria se llena, liberamos la matriz primaria, hacemos la matriz auxiliar la matriz primaria y hacemos otra matriz auxiliar que es 2 veces más grande. Esta nueva matriz auxiliar comienza con F ''= B'' = 0 y no tiene nada copiado (por lo que la operación de cambio de tamaño es O (1) si la asignación de un montón es O (1) compleja). Como el auxiliar copia 2 elementos para cada elemento agregado al primario y el primario comienza como máximo a la mitad, es imposible que el auxiliar no se haya alcanzado con el primario en el momento en que el primario se queda sin espacio otra vez. Las eliminaciones también necesitan eliminar 1 elemento del primario y 0 o 1 del auxiliar. Entonces, suponiendo que las asignaciones de montón son O (1), esta implementación cumple la condición 1). Hacemos que la matriz sea de T * y utilice new siempre que se inserte para cumplir las condiciones 2) y 3). Finalmente, 4) se cumple porque estamos usando una estructura de matriz y podemos implementar fácilmente el acceso O (1).
(Haciendo que esta respuesta sea una wiki de la comunidad. Por favor atánete)
Lo primero es lo primero: una deque requiere que cualquier inserción al frente o atrás mantenga válida cualquier referencia a un elemento miembro. Está bien que los iteradores se invaliden, pero los miembros deben permanecer en el mismo lugar en la memoria. Esto es bastante fácil simplemente copiando los miembros en algún lugar del montón y almacenando T* en la estructura de datos debajo del capó. Vea esta otra pregunta de " Acerca de la indirección adicional de deque <T> "
(el vector no garantiza conservar iteradores o referencias, mientras que la list conserva ambos).
Así que solo demos por hecho este ''indirecto'' y veamos el resto del problema. El bit interesante es el momento de insertar o eliminar desde el principio o el final de la lista. Al principio, parece que un deque podría implementarse trivialmente con un vector , quizás interpretándolo como un buffer circular .
PERO un deque debe satisfacer "Insertar un solo elemento al principio o al final de un deque siempre lleva tiempo constante y causa una sola llamada a un constructor de T."
Gracias a la indirección que ya hemos mencionado, es fácil garantizar que solo haya una llamada de constructor, pero el desafío es garantizar un tiempo constante. Sería fácil si pudiéramos usar el tiempo constante amortizado , lo que permitiría la implementación del vector simple, pero debe ser un tiempo constante (no amortizado).
Es específico de la implementación. Todo lo que requiere un deque es la inserción / eliminación de tiempo constante al comienzo / final, y como mucho lineal en cualquier otro lugar. No se requiere que los elementos sean contiguos.
La mayoría de las implementaciones usan lo que se puede describir como una lista desenrollada. Las matrices de tamaño fijo se asignan en el montón y los punteros a estas matrices se almacenan en una matriz de tamaño dinámico que pertenece al deque.
Esta es una respuesta al desafío de la gravedad del usuario para comentar sobre la solución de 2 arreglos.
- Algunos detalles se discuten aquí
- Se da una sugerencia de mejora
Discusión de detalles: el usuario "gravedad" ya ha dado un resumen muy claro. La "gravedad" también nos desafió a comentar sobre la sugerencia de equilibrar la cantidad de elementos entre dos matrices para lograr O (1) el peor caso (en lugar del caso medio) de tiempo de ejecución. Bueno, la solución funciona eficientemente si ambas matrices son ringbuffers, y me parece que es suficiente dividir el deque en dos segmentos, equilibrado como se sugiere. También creo que, para fines prácticos, la implementación estándar de STL es, por lo menos, lo suficientemente buena, pero en condiciones de tiempo real y con una administración de memoria ajustada correctamente, se podría considerar el uso de esta técnica de equilibrio. También hay una implementación diferente dada por Eric Demaine en un artículo anterior de Dr.Dobbs, con un peor tiempo de ejecución similar.
Equilibrar la carga de ambos buffers requiere moverse entre 0 o 3 elementos, dependiendo de la situación. Por ejemplo, un pushFront (x) debe, si mantenemos el segmento frontal en el conjunto primario, mover los últimos 3 elementos del anillo primario al anillo auxiliar para mantener el equilibrio requerido. Un pushback (x) en la parte posterior debe hacerse cargo de la diferencia de carga y luego decidir cuándo es el momento de mover un elemento del primario al conjunto auxiliar.
Sugerencia para mejorar: hay menos trabajo y contabilidad que hacer si el frente y la parte trasera están almacenados en el anillo auxiliar. Esto se puede lograr cortando el deque en tres segmentos q1, q2, q3, dispuestos de la siguiente manera: La parte delantera q1 está en el anillo auxiliar (el de doble tamaño) y puede comenzar en cualquier desplazamiento desde el cual los elementos estén organizado en el sentido de las agujas del reloj en orden posterior. La cantidad de elementos en q1 es exactamente la mitad de todos los elementos almacenados en el anillo auxiliar. La parte trasera q3 también se encuentra en el anillo auxiliar, ubicado exactamente opuesto a la parte q1 en el anillo auxiliar, también en el sentido de las agujas del reloj en el orden posterior. Este invariante debe mantenerse entre todas las operaciones de deque. Solo la parte central q2 está ubicada (en el sentido de las agujas del reloj en orden posterior) en el anillo primario.
Ahora, cada operación moverá exactamente un elemento o asignará un nuevo buffer vacío cuando cualquiera de los dos se vacíe. Por ejemplo, un pushFront (x) almacena x antes de q1 en el anillo auxiliar. Para mantener el invariante, movemos el último elemento de q2 al frente de la parte posterior q3. Entonces, tanto q1 como q3 obtienen un elemento adicional en sus frentes y por lo tanto permanecen opuestos entre sí. PopFront () funciona al revés, y las operaciones posteriores funcionan de la misma manera. El anillo primario (igual que la parte central q2) va vacío exactamente cuando q1 y q3 se tocan entre sí y forman un círculo completo de elementos posteriores dentro del anillo auxiliar. Además, cuando la deque se reduce, q1, q3 se vaciará exactamente cuando q2 forme un círculo apropiado en el anillo primario.
Los datos en deque son almacenados por chuncks de vector de tamaño fijo, que son
pointered por un map (que también es un pedazo de vector, pero su tamaño puede cambiar)
El código de parte principal del deque iterator es 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 parte principal del deque es 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 dos partes:
iterador
Función simple sobre
deque
1. iterador ( __deque_iterator )
El principal problema del iterador es que cuando ++, - iterador, puede saltar a otro fragmento (si apunta hacia el borde del fragmento). Por ejemplo, hay tres fragmentos de datos: chunk 1 , chunk 2 , chunk 3 .
El apuntador1 pointer1 al inicio del chunk 2 , cuando el operador --pointer indicador --pointer al final del chunk 1 , de manera que pointer2 al pointer2 .
Debajo daré la función principal de __deque_iterator :
En primer lugar, salte a cualquier parte:
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
Tenga en cuenta que, la función chunk_size() 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;
}
2. Función simple sobre 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];
}
Si quieres entender más profundamente el deque , también puedes ver esta pregunta https://.com/a/50959796/6329006
Mi entendimiento de deque
Asigna ''n'' objetos contiguos vacíos del montón como la primera sub-matriz. Los objetos en él se agregan exactamente una vez por el puntero de la cabeza en la inserción.
Cuando el puntero de la cabeza llega al final de una matriz, asigna / vincula una nueva sub-matriz no contigua y agrega objetos allí.
Se eliminan exactamente una vez por el puntero de la cola en la extracción. Cuando el puntero de cola termina una suborganización de objetos, se mueve a la siguiente sub-matriz vinculada y desasigna la antigua.
Los objetos intermedios entre la cabeza y la cola nunca se mueven en la memoria por deque.
Un acceso aleatorio primero determina qué subarranque tiene el objeto, luego acceda a él desde su desplazamiento relativo con en el subcampo.
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í, la operación-en-T * -Complexity se amortiza (debido al vector ), pero solo estamos interesados en Operations-On- T -Complexity y esto es constante (no amortizado).
Epílogo: 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.
Un deque se implementa típicamente como una matriz dinámica de matrices de T
(a) (b) (c) (d)
+-+ +-+ +-+ +-+
| | | | | | | |
+-+ +-+ +-+ +-+
^ ^ ^ ^
| | | |
+---+---+---+---+
| 1 | 8 | 8 | 3 | (reference)
+---+---+---+---+
Las matrices (a), (b), (c) y (d) son generalmente de capacidad fija, y las matrices internas (b) y (c) están necesariamente llenas. (a) y (d) no están llenos, lo que da O (1) inserción en ambos extremos.
Imaginando que hacemos un montón de push_front , (a) se llenará, cuando esté lleno y se realice una inserción, primero tenemos que asignar una nueva matriz, luego hacer crecer el vector (de referencia) y empujar el puntero a la nueva matriz en el frente.
Esta implementación proporciona trivialmente:
- Acceso aleatorio
- Preservación de referencia en el empuje en ambos extremos
- Inserción en el medio que es proporcional a
min(distance(begin, it), distance(it, end))(el estándar es un poco más estricto que el requerido)
Sin embargo, falla el requisito del crecimiento O (1) amortizado. Debido a que las matrices tienen capacidad fija cada vez que el vector (referencia) necesita crecer, tenemos O (N / capacidad) copias de puntero. Debido a que los punteros se copian trivialmente, es posible realizar una única llamada memcpy , por lo que en la práctica esto es casi constante ... pero esto es insuficiente para pasarlo rápidamente.
Aún así, push_front y push_back son más eficientes que para un vector (a menos que esté utilizando la implementación de MSVC, que es notoriamente lenta debido a la capacidad muy pequeña para las matrices ...)
Honestamente, no conozco ninguna estructura de datos, o combinación de estructura de datos, que pueda satisfacer a ambos:
- Acceso aleatorio
y
- O (1) inserción en ambos extremos
Conozco algunas coincidencias "cercanas":
- La inserción de O (1) amortiguada se puede hacer con una matriz dinámica en la que se escribe en el medio, esto es incompatible con la semántica de "preservación de referencia" del
deque - Un árbol B + se puede adaptar para proporcionar un acceso por índice en lugar de por clave, los tiempos están cerca de las constantes, pero la complejidad es O (log N) para el acceso y la inserción (con una pequeña constante), requiere usar Fenwick Trees en los nodos de nivel intermedio.
- Finger Trees se puede adaptar de manera similar, una vez más es realmente O (log N).