O que realmente é um deque no STL?

Eu estava olhando para contêineres STL e tentando descobrir o que eles realmente são (ou seja, a estrutura de dados usada), e o deque me parou: primeiro pensei que era uma lista com dois links, que permitiria a inserção e exclusão de ambas as extremidades em tempo constante, mas estou preocupado com a promessa feita pelo operador [] de ser feita em tempo constante. Em uma lista vinculada, o acesso arbitrário deve ser O (n), certo?

E se é um array dinâmico, como ele pode adicionar elementos em tempo constante? Deve-se mencionar que a realocação pode ocorrer e que O (1) é um custo amortizado, como para um vetor .

Então, eu me pergunto o que é essa estrutura que permite acesso arbitrário em tempo constante e, ao mesmo tempo, nunca precisa ser movida para um novo local maior.

Um deque é definido recursivamente: internamente, ele mantém uma fila dupla de pedaços de tamanho fixo. Cada pedaço é um vetor, e a fila (“mapa” no gráfico abaixo) dos próprios pedaços também é um vetor.

Há uma ótima análise das características de desempenho e como ela se compara com a vectordo CodeProject .

A implementação da biblioteca padrão do GCC usa internamente a T**para representar o mapa. Cada bloco de dados é um T*que é alocado com algum tamanho fixo __deque_buf_size(que depende sizeof(T)).

Imagine isso como um vetor de vetores. Só que eles não são padrão std::vector.

O vetor externo contém ponteiros para os vetores internos. Quando sua capacidade é alterada por meio de realocação, em vez de alocar todo o espaço vazio até o fim std::vector, ele divide o espaço vazio em partes iguais no início e no final do vetor. Isto permite push_fronte push_backneste vector para ambos ocorrem em O (1) tempo amortizado.

O comportamento do vetor interno precisa mudar, dependendo da parte frontal ou traseira do deque. Na parte de trás, pode se comportar como um padrão, std::vectoronde cresce no final e push_backocorre no tempo O (1). Na frente, ele precisa fazer o oposto, crescendo no início de cada um push_front. Na prática, isso é facilmente alcançado adicionando um ponteiro ao elemento frontal e a direção do crescimento, juntamente com o tamanho. Com esta modificação simples, push_fronttambém pode ser o tempo O (1).

O acesso a qualquer elemento requer deslocamento e divisão no índice de vetor externo adequado que ocorre em O (1) e indexação no vetor interno que também é O (1). Isso pressupõe que todos os vetores internos tenham tamanho fixo, exceto aqueles no início ou no final do deque.

deque = fila dupla

Um recipiente que pode crescer em qualquer direção.

Deque é normalmente implementado como um vectorde vectors(uma lista de vetores não pode fornecer acesso aleatório em tempo constante). Enquanto o tamanho dos vetores secundários depende da implementação, um algoritmo comum é usar um tamanho constante em bytes.

(Esta é uma resposta que eu dei em outro tópico . Essencialmente, estou argumentando que mesmo implementações bastante ingênuas, usando uma única vector, estão em conformidade com os requisitos de "push constante não amortizado_ {frente, trás}". Você pode se surpreender , e acho que isso é impossível, mas eu encontrei outras citações relevantes no padrão que definem o contexto de uma maneira surpreendente.Por favor, tenha paciência comigo: se eu cometer um erro nesta resposta, seria muito útil identificar quais coisas Eu disse corretamente e onde minha lógica foi quebrada.)

Nesta resposta, não estou tentando identificar uma boa implementação, estou apenas tentando nos ajudar a interpretar os requisitos de complexidade no padrão C ++. Estou citando o N3242 , que é, segundo a Wikipedia , o mais recente documento de padronização C ++ 11 disponível gratuitamente. (Parece estar organizado de maneira diferente do padrão final e, portanto, não citarei os números exatos das páginas. É claro que essas regras podem ter sido alteradas no padrão final, mas acho que isso não aconteceu.)

A deque<T>pode ser implementado corretamente usando a vector<T*>. Todos os elementos são copiados para a pilha e os ponteiros armazenados em um vetor. (Mais sobre o vetor posteriormente).

Por que ao T*invés de T? Porque o padrão exige que

"Uma inserção em cada extremidade do deque invalida todos os iteradores do deque, mas não afeta a validade das referências a elementos do deque. "

(minha ênfase). As T*ajudas para satisfazer isso. Também nos ajuda a satisfazer isso:

"Inserir um único elemento no início ou no final de um deque sempre ..... causa uma única chamada para um construtor de T. "

Agora, o pouco (controverso). Por que usar a vectorpara armazenar o T*? Isso nos dá acesso aleatório, o que é um bom começo. Vamos esquecer a complexidade do vetor por um momento e desenvolver isso com cuidado:

O padrão fala sobre "o número de operações nos objetos contidos". Pois deque::push_frontisso é claramente 1, porque exatamente um Tobjeto é construído e zero dos Tobjetos existentes é lido ou verificado de qualquer maneira. Esse número, 1, é claramente uma constante e é independente do número de objetos atualmente no deque. Isso nos permite dizer que:

'Para nós deque::push_front, o número de operações nos objetos contidos (os Ts) é fixo e é independente do número de objetos já existentes no deque.'

Obviamente, o número de operações no T*não será tão bem-comportado. Quando o vector<T*>tamanho for muito grande, ele será realocado e muitos T*s serão copiados. Portanto, sim, o número de operações no T*variará muito, mas o número de operações no Tnão será afetado.

Por que nos preocupamos com essa distinção entre contar operações Te contar operações T*? É porque o padrão diz:

Todos os requisitos de complexidade nesta cláusula são declarados apenas em termos do número de operações nos objetos contidos.

Para o deque, os objetos contidos são T, e não o T*, o que significa que podemos ignorar qualquer operação que copie (ou realoque) a T*.

Não falei muito sobre como um vetor se comportaria em um deque. Talvez o interpretássemos como um buffer circular (com o vetor sempre ocupando seu máximo capacity()e realocando tudo em um buffer maior quando o vetor estiver cheio. Os detalhes não importam.

Nos últimos parágrafos, analisamos deque::push_fronte a relação entre o número de objetos no deque e o número de operações executadas por push_front em objetos-contidos T. E descobrimos que eles eram independentes um do outro. Como o padrão exige que a complexidade seja em termos de operações T, podemos dizer que isso tem complexidade constante.

Sim, a complexidade Operações-em-T * é amortizada (devido a vector), mas estamos interessados ​​apenas na complexidade em Operações-em-T e isso é constante (não-amortizado).

A complexidade do vetor :: push_back ou vector :: push_front é irrelevante nesta implementação; essas considerações envolvem operações T*e, portanto, são irrelevantes. Se o padrão estivesse se referindo à noção teórica "convencional" de complexidade, eles não teriam explicitamente se restringido ao "número de operações nos objetos contidos". Estou interpretando demais essa frase?

Na visão geral, você pode pensar dequecomo umdouble-ended queue

Os dados dequesão armazenados por chuncks de vetor de tamanho fixo, que são

apontado por um map(que também é um pedaço do vetor, mas seu tamanho pode mudar)

O código principal da peça deque iteratoré o seguinte:

/*
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
}

O código principal da peça dequeé o seguinte:

/*
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;
}

Abaixo, apresentarei o código dequeprincipal, principalmente sobre três partes:

1. iterador

2. Como construir um deque

1. iterador ( __deque_iterator)

O principal problema do iterador é que, quando ++, - iterator, ele pode pular para outro pedaço (se apontar para a borda do pedaço). Por exemplo, há três blocos de dados: chunk 1, chunk 2, chunk 3.

Os pointer1ponteiros para o início de chunk 2, quando o operador --pointerapontará para o final de chunk 1, para o pointer2.

Abaixo darei a função principal de __deque_iterator:

Primeiro, pule para qualquer parte:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

Observe que, a chunk_size()função que calcula o tamanho do pedaço, você pode pensar em retornar 8 para simplificar aqui.

operator* obter os dados no pedaço

reference operator*()const{
    return *cur;
}

operator++, --

// prefixo 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;
}

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. Como construir um deque

função comum 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();
}

Vamos supor que i_dequetenha 20 elementos int 0~19cujo tamanho do bloco seja 8 e, agora, 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);

É estrutura interna como abaixo:

Então push_back novamente, ele chamará alocar novo pedaço:

push_back(3)

Se nós push_front, ele alocará novo pedaço antes do anteriorstart

Observe quando o push_backelemento dentro do deque, se todos os mapas e partes forem preenchidos, isso fará com que aloque um novo mapa e ajuste partes. Mas o código acima pode ser suficiente para você entender deque.

Eu estava lendo "Estruturas de dados e algoritmos em C ++" por Adam Drozdek, e achei isso útil. HTH.

Um aspecto muito interessante do STL deque é sua implementação. Um deque STL não é implementado como uma lista vinculada, mas como uma matriz de ponteiros para blocos ou matrizes de dados. O número de blocos muda dinamicamente, dependendo das necessidades de armazenamento, e o tamanho da matriz de ponteiros muda de acordo.

Você pode notar no meio a matriz de ponteiros para os dados (pedaços à direita) e também pode notar que a matriz no meio está mudando dinamicamente.

Uma imagem vale mais que mil palavras.

Embora o padrão não exija nenhuma implementação específica (apenas acesso aleatório em tempo constante), um deque é geralmente implementado como uma coleção de "páginas" de memória contígua. Novas páginas são alocadas conforme necessário, mas você ainda tem acesso aleatório. Ao contrário std::vector, não é prometido que os dados sejam armazenados de forma contígua, mas, como os vetores, as inserções no meio exigem muita realocação.