O std :: deque realmente tem inserção de tempo constante no início?

O Padrão diz:

Um deque é um contêiner de sequência que suporta iteradores de acesso aleatório (27.2.7). Além disso, ele suporta operações de inserção e exclusão de tempo constante no início ou no final; inserir e apagar no meio leva tempo linear.

No entanto, também diz na mesma cláusula:

Todos os requisitos de complexidade desta Cláusula são declarados apenas em termos do número de operações nos objetos contidos. [Exemplo: o construtor de cópia do tipo vector<vector<int>>tem complexidade linear, mesmo que a complexidade de copiar cada um deles vector<int>seja linear. - exemplo final]

Isso não significa que a inserção no início de, digamos, deque<int>pode levar tempo linear , desde que não execute mais do que um número constante de operações nas ints que já estão no deque e o novo intobjeto sendo inserido ?

Por exemplo, suponha que implementemos um deque usando um "vetor de vetores tamanho-K". Parece que uma vez a cada K vez que inserimos no início, um novo vetor tamanho-K deve ser adicionado no início, para que todos os outros vetores tamanho-K sejam movidos. Isso significaria que a complexidade temporal da inserção no início é amortizada O (N / K), onde N é o número total de elementos, mas K é constante, portanto, esse é apenas O (N). Mas parece que isso é permitido pelo Padrão, porque mover um vetor tamanho K não move nenhum de seus elementos e os "requisitos de complexidade" são "declarados apenas em termos do número de operações" nos intobjetos contidos .

O Padrão realmente permite isso? Ou devemos interpretá-lo como tendo um requisito mais rigoroso, ou seja , número constante de operações nos objetos contidos mais tempo adicional constante?

Por exemplo, suponha que implementemos um deque usando um "vetor de vetores tamanho-K".

Isso não seria uma implementação válida. A inserção na frente de um vectorinvalida todos os ponteiros / referências no contêiner. dequeé necessário para não invalidar nenhum ponteiro / referência na inserção frontal.

Mas vamos ignorar isso por enquanto.

Mas parece que isso é permitido pelo Padrão, porque mover um vetor tamanho-K não move nenhum de seus elementos e os "requisitos de complexidade" são "declarados apenas em termos do número de operações" nos objetos int contidos .

Sim, isso seria permitido. De fato, implementações reais de dequenão são tão diferentes disso (embora não se usem std::vectorpor razões óbvias). O resumo geral de uma dequeimplementação é uma matriz de ponteiros para blocos (com espaço para crescimento na parte frontal e traseira), com cada bloco contendo até X itens, bem como ponteiros para os blocos seguintes / anteriores (para criar iteração rápida do elemento).

Se você inserir elementos suficientes na frente ou atrás, a matriz de ponteiros de bloco precisará aumentar. Isso exigirá uma operação que seja de tempo linear em relação ao número de itens no deque, mas na verdade não opere nos itens, portanto, não conta. A especificação não tem nada a dizer sobre a complexidade dessa operação.

Sem essa disposição, não tenho certeza se o conjunto exclusivo de recursos deque(inserção frontal / traseira rápida e acesso aleatório) seria implementável.

Eu acho que você está alcançando um pouco, na maneira como interpreta o significado dos domínios de complexidade. Você está tentando fazer uma distinção entre "tempo linear" e "complexidade linear", que não estou convencida de que faz muito sentido.

O padrão está claro que a inserção na frente é de tempo constante, e acho que todos concordamos com isso. A última passagem apenas nos diz que o que cada um que quantidade "constante" de operações envolve por baixo é simplesmente não especificados nem constrangido pela norma.

E isso não é incomum. Qualquer algoritmo funciona com alguma base de abstração. Mesmo se escrevêssemos um algoritmo que se resumisse às instruções individuais da máquina e disséssemos que havia apenas N instruções de máquina geradas por nosso algoritmo, não investigaríamos que tipo de complexidade cada complexidade individual possui dentro do processador e adicione isso aos nossos resultados. Nós não diria que algumas operações acabam fazendo mais no nível molecular quântica e, portanto, a nossa O (n) algoritmo é realmente O (N × M ³ ) ou algo assim. Optamos por não considerar esse nível de abstração. E, a menos que essa complexidade dependa das entradas do algoritmo, tudo bem.

No seu caso, o tamanho dos vetores internos movidos / copiados não é realmente relevante, porque eles não mudam inerentemente à medida que o deque cresce. O número de vetores internos sim, mas o tamanho de cada um é uma propriedade independente. Portanto, é irrelevante ao descrever a complexidade de inserir um novo elemento no vetor externo.

O tempo real de execução (que poderia ser descrito em alguns termos algorítmicos, se você escolher) varia dependendo do conteúdo dos vetores internos copiados? Sim, claro. Mas isso não tem nada a ver com o modo como a tarefa de expandir o vetor externo cresce em carga de trabalho à medida que o próprio vetor externo cresce.

Então, aqui, o padrão está dizendo que ele não copiará N ou N ² nem registrará N vetores internos quando você colocar outro na frente; está dizendo que o número dessas operações não mudará de escala à medida que seu deque cresce. Também está dizendo que, para os fins dessa regra, não se importa com o que copiar / mover os vetores internos realmente envolve ou com que tamanho eles são.

A análise de complexidade não é sobre desempenho. A análise de complexidade é sobre como o desempenho é escalado.