Por que eu preferiria usar vetor para deque

Desde a

1. ambos são recipientes de memória contíguos;
2. Em termos de recursos, o deque tem quase tudo que o vetor tem, mas muito mais, já que é mais eficiente para inserir na frente.

Por Whould ninguém preferem std::vectora std::deque?

Os elementos em a nãodeque são contíguos na memória; elementos têm a garantia de ser. Portanto, se você precisa interagir com uma biblioteca C simples que precisa de matrizes contíguas, ou se você se preocupa (muito) com a localidade espacial, talvez prefira . Além disso, como há alguma contabilidade extra, outras operações são provavelmente (ligeiramente) mais caras do que suas operações equivalentes . Por outro lado, o uso de muitas / grandes instâncias de pode levar à fragmentação desnecessária do heap (desacelerando as chamadas para ).vectorvectorvectorvectornew

Além disso, conforme apontado em outro lugar no StackOverflow , há mais boas discussões aqui: http://www.gotw.ca/gotw/054.htm .

Para saber a diferença, é preciso saber como dequegeralmente é implementado. A memória é alocada em blocos de tamanhos iguais e eles são encadeados (como uma matriz ou possivelmente um vetor).

Portanto, para encontrar o enésimo elemento, você encontra o bloco apropriado e acessa o elemento dentro dele. Este é um tempo constante, porque é sempre exatamente 2 pesquisas, mas ainda é mais do que o vetor.

vectortambém funciona bem com APIs que desejam um buffer contíguo porque são APIs C ou são mais versáteis ao serem capazes de pegar um ponteiro e um comprimento. (Assim, você pode ter um vetor embaixo ou um array regular e chamar a API do seu bloco de memória).

Onde dequetem suas maiores vantagens são:

1. Ao aumentar ou diminuir a coleção de qualquer extremidade
2. Quando você está lidando com tamanhos de coleção muito grandes.
3. Ao lidar com bools e você realmente quer bools em vez de um bitset.

O segundo deles é menos conhecido, mas para tamanhos de coleção muito grandes:

1. O custo de realocação é grande
2. A sobrecarga de ter que encontrar um bloco de memória contíguo é restritiva, então você pode ficar sem memória mais rápido.

Quando eu estava lidando com grandes coleções no passado e mudei de um modelo contíguo para um modelo de bloco, fomos capazes de armazenar uma coleção cerca de 5 vezes maior antes de ficar sem memória em um sistema de 32 bits. Isso ocorre em parte porque, ao realocar, ele realmente precisava armazenar o bloco antigo e também o novo antes de copiar os elementos.

Tendo dito tudo isso, você pode ter problemas com std::dequesistemas que usam alocação de memória "otimista". Embora suas tentativas de solicitar um tamanho de buffer grande para uma realocação de a vectorprovavelmente sejam rejeitadas em algum ponto com a bad_alloc, a natureza otimista do alocador provavelmente sempre concederá a solicitação de um buffer menor solicitado por a dequee isso provavelmente causará o sistema operacional para matar um processo para tentar adquirir alguma memória. Qualquer que seja escolhido pode não ser muito agradável.

As soluções alternativas nesse caso são definir sinalizadores no nível do sistema para substituir a alocação otimista (nem sempre viável) ou gerenciar a memória um pouco mais manualmente, por exemplo, usando seu próprio alocador que verifica o uso de memória ou similar. Obviamente não é o ideal. (O que pode responder à sua pergunta quanto à preferência pelo vetor ...)

Eu implementei vetor e deque várias vezes. deque é muito mais complicado do ponto de vista da implementação. Essa complicação se traduz em mais código e código mais complexo. Portanto, você normalmente verá um tamanho de código ao escolher deque em vez de vetor. Você também pode experimentar um pequeno golpe de velocidade se seu código usar apenas as coisas em que o vetor se destaca (ou seja, push_back).

Se você precisa de uma fila dupla, deque é o vencedor. Mas se você estiver fazendo a maioria das inserções e apagamentos no verso, o vetor será o vencedor claro. Quando você não tiver certeza, declare seu contêiner com um typedef (para que seja fácil alternar para frente e para trás) e meça.

std::dequenão tem memória contínua garantida - e geralmente é um pouco mais lento para acesso indexado. Um deque é tipicamente implementado como uma "lista de vetores".

De acordo com http://www.cplusplus.com/reference/stl/deque/ , "ao contrário dos vetores, não é garantido que os deques tenham todos os seus elementos em locais de armazenamento contíguos, eliminando assim a possibilidade de acesso seguro através da aritmética de ponteiros."

Deques são um pouco mais complicados, em parte porque eles não têm necessariamente um layout de memória contíguo. Se você precisar desse recurso, não deve usar um deque.

(Anteriormente, minha resposta levantou uma falta de padronização (da mesma fonte acima, "deques pode ser implementado por bibliotecas específicas de maneiras diferentes"), mas isso na verdade se aplica a praticamente qualquer tipo de dados de biblioteca padrão.)

Um deque é um contêiner de sequência que permite acesso aleatório aos seus elementos, mas não é garantido que tenha armazenamento contíguo.

Acho boa ideia fazer teste de desempenho de cada case. E tome a decisão confiando nestes testes.

Eu prefiro do std::dequeque std::vectorna maioria dos casos.

Você não preferiria que o vetor deque de acordo com os resultados do teste (com a fonte).

Claro, você deve testar em seu aplicativo / ambiente, mas em resumo:

• push_back é basicamente o mesmo para todos
• insert, erase in deque são muito mais rápidos que list e marginalmente mais rápidos que vector

Mais algumas reflexões e uma nota a considerar circular_buffer.

Por um lado, o vetor é freqüentemente muito mais rápido do que o deque. Se você realmente não precisa de todos os recursos do deque, use um vetor.

Por outro lado, às vezes você fazer características necessidades que vector não lhe dá, caso em que você deve usar um deque. Por exemplo, eu desafio qualquer um a tentar reescrever esse código , sem usar um deque e sem alterar enormemente o algoritmo.

Observe que a memória vetorial é realocada à medida que o array cresce. Se você tiver ponteiros para elementos do vetor, eles se tornarão inválidos.

Além disso, se você apagar um elemento, os iteradores se tornam inválidos (mas não "para (auto ...)").

Editar: mudou 'deque' para 'vetor'