O que realmente é um deque no STL?

192

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.

Zonko
fonte
4
possível duplicação do deque STL acessando pelo índice é O (1)?
Fredoverflow
1
@Graham "dequeue" é outro nome comum para "deque". Eu ainda aprovo a edição, já que "deque" geralmente é o nome canônico.
Konrad Rudolph
@ Konrad Obrigado. A pergunta era especificamente sobre o deque C ++ STL, que usa a ortografia mais curta.
Graham Borland
2
dequemeios de fila de dupla extremidade , embora, obviamente, o requisito estrito de O (1) o acesso a elementos intermédios é determinada para C ++
Matthieu M.

Respostas:

181

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.

esquemático do layout de memória de um deque

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)).

Konrad Rudolph
fonte
27
Essa é a definição de um deque como eu aprendi, mas dessa forma, não pode garantir acesso a tempo constante, portanto deve haver algo faltando.
stefaanv
14
@stefaanv, @Konrad: implementações em C ++ que eu já usei uma matriz de ponteiros para matrizes de tamanho fixo. Isso efetivamente significa que push_front e push_back não são realmente constantes, mas com fatores de crescimento inteligentes, você ainda é amortizado com constantes, portanto, O (1) não é tão errado e, na prática, é mais rápido que o vetor porque você está trocando ponteiros únicos em vez de objetos inteiros (e menos ponteiros que objetos).
precisa
5
O acesso em tempo constante ainda é possível. Apenas, se você precisar alocar um novo bloco na frente, empurre um novo ponteiro no vetor principal e mude todos os ponteiros.
Xeo
4
Se o mapa (a própria fila) era uma lista dupla, não vejo como ele poderia permitir acesso aleatório O (1). Ele pode ser implementado como um buffer circular, o que permitiria que o redimensionamento do buffer circular fosse mais eficiente: copie apenas os ponteiros em vez de todos os elementos da fila. Ainda assim, esse é um pequeno benefício.
Wernight 17/02/2013
14
@JeremyWest Por que não? O acesso indexado vai para o elemento i% B-ésimo no bloco i / B-ésimo (B = tamanho do bloco), que é claramente O (1). Você pode adicionar um novo bloco no O (1) amortizado, portanto, adicionar elementos é O (1) amortizado no final. A adição de um novo elemento no início é O (1), a menos que um novo bloco precise ser adicionado. Adicionar um novo bloco no início não é O (1), é verdade, é O (N), mas, na realidade, possui um fator constante muito pequeno, pois você só precisa mover ponteiros N / B em vez de N elementos.
Konrad Rudolph
22

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.

Mark Ransom
fonte
1
Você pode descrever os vetores internos como tendo fixo capacidade
Caleth
18

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.

Alok Save
fonte
6
Não são exatamente vetores internamente. As estruturas internas podem ter capacidade alocada, mas não utilizada, no começo e no fim
Mooing Duck
@MooingDuck: É realmente uma implementação definida. Pode ser uma matriz de vetores ou vetores de vetores ou qualquer coisa que possa fornecer o comportamento e a complexidade exigidos pelo padrão.
precisa
1
@ Als: Eu não penso arrayem nada ou vectornada pode prometer O(1)push_front amortizado . O interior das duas estruturas, pelo menos, deve ser capaz de ter um O(1)push_front, que nem um arraynem um vectorpodem garantir.
Mooing Duck
4
@MooingDuck esse requisito é facilmente atendido se o primeiro pedaço crescer de cima para baixo em vez de de baixo para cima. Obviamente, um padrão vectornão faz isso, mas é uma modificação simples o suficiente para fazê-lo.
Mark Ransom
3
@ Mooing Duck, push_front e push_back podem ser facilmente executados em O (1) amortizado com uma única estrutura vetorial. É apenas um pouco mais de contabilidade de um buffer circular, nada mais. Suponha que você tenha um vetor regular de capacidade 1000 com 100 elementos nas posições 0 a 99. Agora, quando um push_Front acontece, basta pressionar no final, ou seja, na posição 999, depois em 998 etc. até que as duas extremidades se encontrem. Em seguida, você realoca (com crescimento exponencial para garantir tempos constantes de amortização) exatamente como faria com um vetor comum. Tão eficazmente, você só precisa de um ponteiro adicional para o primeiro el.
plamenko 4/09/16
14

(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?

Aaron McDaid
fonte
8
Parece muito como me traindo! Quando você especifica a complexidade de uma operação, não a faz apenas em parte dos dados: deseja ter uma idéia do tempo de execução esperado da operação que está chamando, independentemente do que ela opera. Se eu seguir sua lógica sobre operações em T, isso significaria que você poderia verificar se o valor de cada T * é um número primo cada vez que uma operação é executada e ainda respeitar o padrão, já que você não toca em Ts. Você poderia especificar de onde vêm suas cotações?
Zonko
2
Penso que os escritores padrão sabem que não podem usar a teoria da complexidade convencional porque não temos um sistema totalmente especificado onde conhecemos, por exemplo, a complexidade da alocação de memória. Não é realista fingir que a memória pode ser alocada para um novo membro de um, listindependentemente do tamanho atual da lista; se a lista for muito grande, a alocação será lenta ou falhará. Portanto, até onde posso ver, o comitê tomou a decisão de especificar apenas as operações que podem ser objetivamente contadas e medidas. (PS: Eu tenho outra teoria sobre isso para outra resposta.)
Aaron McDaid
Tenho certeza de que O(n)o número de operações é assintoticamente proporcional ao número de elementos. IE, contagem de meta-operações. Caso contrário, não faria sentido limitar a pesquisa O(1). Portanto, as listas vinculadas não se qualificam.
Mooing Duck
8
Essa é uma interpretação muito interessante, mas por essa lógica também listpode ser implementada como vectorponteiro (as inserções no meio resultarão em uma chamada de construtor de cópia única , independentemente do tamanho da lista, e o O(N)embaralhamento dos ponteiros pode ser ignorado porque eles não são operações em T).
22412 Mankarse
1
Isso é legal para a linguagem legal (embora eu não vou tentar descobrir se está realmente correto ou se há algum ponto sutil no padrão que proíbe essa implementação). Mas não é uma informação útil na prática, porque (1) implementações comuns não são implementadas dequedessa maneira e (2) "trapaceando" dessa maneira (mesmo que permitidas pelo padrão) ao computar a complexidade algorítmica não é útil para escrever programas eficientes .
Kyle Strand
13

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

visão geral de deque

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)

estrutura interna deque

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.

insira a descrição da imagem aqui

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;
}
iterador pular n etapas / acesso aleatório
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:

insira a descrição da imagem aqui

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

push_back(3)

insira a descrição da imagem aqui

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

insira a descrição da imagem aqui

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.

Jayhello
fonte
Você mencionou: "Observe quando o elemento push_back entra no deque, se todos os mapas e partes estiverem preenchidos, isso fará com que aloque um novo mapa e ajuste as partes". Eu me pergunto por que o padrão C ++ diz "[26.3.8.4.3] A inserção de um único elemento no início ou no final de um deque sempre leva tempo constante" em N4713. Alocar uma porção de dados leva mais que um tempo constante. Não?
HCSF
7

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.

insira a descrição da imagem aqui

Keloo
fonte
1
Obrigado por indicar um livro. Eu li a dequeparte e é muito bom.
Rick
@ Rick feliz em ouvir isso. Lembro-me de cavar no deque em algum momento porque não conseguia entender como você pode ter acesso aleatório ([] operator) em O (1). Também provar que (push / pop) _ (verso / frente) amortizou O (1) complexidade é um interessante 'momento aha'.
9/19
6

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.

Kerrek SB
fonte
4
ou eliminações no meio requerem lotes de realocação
Mark Hendrickson
Se insertrequer muita deslocalização como é que experimento 4 aqui mostrar impressionante diferença entre vector::insert()e deque::insert()?
Bula
1
@ Bula: Talvez devido a falta de comunicação dos detalhes? A complexidade do deque insert é "linear no número de elementos inseridos mais a menor distância do início e do final do deque". Para sentir esse custo, você precisa inserir o meio atual; é isso que o seu benchmark está fazendo?
31517 Kerrek SB
@KerrekSB: o artigo com benchmark foi referenciado na resposta do Konrad acima. Na verdade, eu não notei a seção de comentários do artigo abaixo. No tópico 'Mas o deque tem tempo de inserção linear?' O autor mencionou que usou a inserção na posição 100 em todos os testes, o que torna os resultados um pouco mais compreensíveis.
Bula