Deque - C/C++

Duplo terminou fila
deque (geralmente pronunciado como "deck" ) é um acrônimo irregular de d -ouble e nded Que ue. Double-filas terminaram são uma espécie de recipiente seqüência. Como tal, os seus elementos estão ordenados na sequência de uma seqüência linear estrita.

Deques podem ser implementadas por bibliotecas específicas de diferentes maneiras, mas em todos os casos em que permitem a cada um dos elementos a ser acessado por meio de iteradores de acesso aleatório, com armazenamento sempre tratado automaticamente (expandindo e contraindo quando necessário).

seqüências deque têm as seguintes propriedades:
Os elementos individuais podem ser acessados ​​pelo seu índice de posição.
Iteração sobre os elementos podem ser realizados em qualquer ordem.
Os elementos podem ser adicionados e removidos de forma eficiente a partir de qualquer de suas extremidades (início ou o fim da seqüência).

Portanto, eles fornecem uma funcionalidade semelhante ao fornecido pelo vetor s, mas com inserção eficiente e exclusão de elementos também no início da seqüência e não apenas no seu final. Do lado da devolução, ao contrário do vetor s, deque s não são a garantia de ter todos os seus elementos em locais de armazenamento contíguos, eliminando assim a possibilidade de acesso seguro através da aritmética de ponteiro.

Ambos os vetores s e deque é proporcionar, assim, uma interface muito semelhante e pode ser usado para fins semelhantes, mas internamente o trabalho tanto de maneira bem diferente: enquanto os vetores são muito semelhantes a uma matriz comum, que cresce por realocar todos os seus elementos em um único bloco quando sua capacidade está esgotada, os elementos de um deque s pode ser dividido em vários pedaços de armazenamento, com a classe de manter todas essas informações e proporcionando um acesso uniforme aos elementos. Portanto, deque s são um pouco mais complexo internamente, mas isso geralmente lhes permite crescer de forma mais eficiente do que o vetor está com sua capacidade de forma automática, especialmente em grandes seqüências, porque realocações maciças são evitados.

Para operações que envolvem a inserção freqüente ou remoção de elementos em posições que não sejam o início ou o fim, deque é pior desempenho consistente e tem menos iteradores e referências de lista s.

Em sua implementação em C + + Standard Template Library, deques tomar dois parâmetros do modelo:

template < classe T, classe Allocator alocador => classe deque;

Onde os parâmetros de modelo têm os seguintes significados:
T : tipo de elementos.
Alocador : Tipo do alocador objeto usado para definir o modelo de alocação de armazenamento. Por padrão, o alocador de modelo de classe para o tipo T é usado, que define o modelo de alocação de memória mais simples e é independente de valor.
Na referência para as funções de membro do deque, esses mesmos nomes são assumidos para os parâmetros do modelo.

funções de Membro

(Construtor)

Construir container deque (função de membro público)

(Destruidor)

Deque destruidor (função de membro público)

operador =

Copie o conteúdo das embalagens (função de membro público)

Iteradores :

começar

Retornar iterador para o começo (função de membro público)

final

Retornar iterador para terminar (função de membro público)

rbegin

Retornar iterador reverso para reverter início (função de membro público)

rasgar

Retornar iterador reverso para reverter final (função de membro público)

Capacidade :

tamanho

Retornar tamanho (função de membro público)

max_size

tamanho máximo de Retorno (função de membro público)

redimensionar

Altere o tamanho (funções de membro público)

vazio

Teste se o recipiente estiver vazio (função de membro público)

Elemento de acesso :

operador []

Acesse o elemento (função de membro público)

em	Acesse o elemento (função de membro público)

frente

Acesso primeiro elemento (função de membro público)

volta

Acesso último elemento (função de membro público)

Modificadores :

atribuir

Atribuir o conteúdo das embalagens (função de membro público)

push_back

Adicionar elemento no final (função de membro público)

push_front

Inserir elemento no início (função de membro público)

pop_back

Eliminar o último elemento (função de membro público)

pop_front

Excluir primeiro elemento (função de membro público)

inserir

Inserir elementos (função de membro público)

apagar

Apagar elementos (função de membro público)

swap	Swap de conteúdo (função de membro público)

claro

Limpar o conteúdo (função de membro público)

Alocador :

get_allocator

Obter alocador (função de membro público)

tipos Estados

do modelo <T, classe Allocator alocador <T> => deque de classe; 

tipo de membro	definição
referência	Alocador de Referência:
const_reference	Alocador: const_reference
iterador	Random iterador acesso
const_iterator	iterador de acesso aleatório Constant
size_type	Unsigned tipo integral (normalmente mesmo size_t )
difference_type	Assinado tipo integral (normalmente mesmo ptrdiff_t )
value_type	T
allocator_type	Alocador
ponteiro	Alocador: ponteiro
const_pointer	Alocador: const_pointer
reverse_iterator	<iterator> reverse_iterator
const_reverse_iterator	<const_iterator> reverse_iterator