example - queue c++

El acceso a deque de STL por índice es O(1)?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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:

1. iterador

2. Cómo acceder aleatoriamente a un deque realizar

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