example - queue c++
El acceso a deque de STL por índice es O(1)? (4)
Encontré esta implementación deque de Wikipedia :
Almacenamiento de contenidos en múltiples arreglos más pequeños, asignando arreglos adicionales al principio o al final según sea necesario. La indexación se implementa manteniendo una matriz dinámica que contiene punteros a cada una de las matrices más pequeñas.
Supongo que responde a mi pregunta.
He leído que el acceso a los elementos por índice de posición se puede hacer en un tiempo constante en un deque STL. Por lo que sé, los elementos en un deque pueden almacenarse en varias ubicaciones no contiguas, eliminando el acceso seguro mediante aritmética de punteros. Por ejemplo:
abc-> defghi-> jkl-> mnop
Los elementos del deque anterior consisten en un solo carácter. El conjunto de caracteres en un grupo indica que está asignado en la memoria contigua (por ejemplo, abc está en un solo bloque de memoria, defhi está ubicado en otro bloque de memoria, etc.). ¿Alguien puede explicar cómo el acceso por índice de posición se puede hacer en tiempo constante, especialmente si el elemento al que se accede está en el segundo bloque? ¿O un deque tiene un puntero al grupo de bloques?
Actualización: ¿O hay alguna otra implementación común para un deque?
Si deque se implementa como un búfer de anillo en la parte superior de std::vector , que se reasigna a sí mismo cuando aumenta de tamaño, el acceso por índice es de hecho O (1).
El estándar proporciona evidencia de que dicha implementación fue realizada, al menos se ajusta al estándar en las estimaciones de complejidad. Las cláusulas 23.2.1.3/4 y 23.2.1.3/5 requieren que
la inserción al principio o al final de un deque requiere un tiempo constante, mientras que la inserción en el medio requiere un tiempo lineal del tamaño del deque
al borrar elementos del deque, puede llamar a tantos operadores de asignación, como la distancia desde los elementos que se borran hasta el final del deque.
Y, por supuesto, debe contar con requisitos estándar en lugar de su propia visión de cómo se podrían implementar los contenedores y los algoritmos.
Tenga en cuenta que la norma requiere más que estos dos puntos mencionados anteriormente. También plantea el requisito de que las referencias a los elementos deben permanecer válidas entre las inserciones en la parte posterior o frontal del deque. Esto puede satisfacerse si el búfer de anillo contiene punteros a los elementos reales en lugar de los propios elementos. De todos modos, mi respuesta solo demuestra la idea de que varias implementaciones pueden satisfacer ciertos requisitos.
Una de las posibles implementaciones puede ser una matriz dinámica de matrices de tamaño constante; esta matriz de tamaño constante se puede agregar a cualquiera de los extremos cuando se necesita más espacio. Todas las matrices están llenas, excepto, quizás, para la primera y la última, que pueden estar parcialmente vacías. Eso significa que, al conocer el tamaño de cada matriz y el número de elementos utilizados en la primera matriz, se puede encontrar fácilmente una posición de un elemento por índice.
http://cpp-tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html
Los datos en deque se almacenan por elementos de vector de tamaño fijo, que son
señalado por un map (que también es una parte del vector, pero su tamaño puede cambiar)
El código de la 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 principal de deque , principalmente sobre dos partes:
iterador
Cómo acceder aleatoriamente a un
dequerealizar
1. iterador ( __deque_iterator )
El principal problema del iterador es que, cuando ++, - iterador, puede saltar a otra parte (si apunta al borde de la parte). Por ejemplo, hay tres fragmentos de datos: chunk 1 , chunk 2 , chunk 3 .
Los punteros del pointer1 al comienzo del chunk 2 , cuando el operador --pointer , apuntará al final del chunk 1 , como también al pointer2 .
A continuación le daré la función principal de __deque_iterator :
En primer lugar, saltar a cualquier trozo:
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 trozo
reference operator*()const{
return *cur;
}
operator++, --
// prefijo formas de 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;
}
iterador saltar 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. Elementos de deque acceso aleatorio.
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];
}
También ves esta pregunta que da el código principal de deque
https://.com/a/50959796/6329006