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 interrompeu: primeiro pensei que era uma lista com dois links, o que permitiria a inserção e exclusão de ambas as extremidades em tempo constante, mas estou incomodado coma promessa feita pelo operador [] a ser feito em tempo constante. Em uma lista vinculada, o acesso arbitrário deve ser O (n), certo?

E se é uma matriz dinâmica, como podeadd elements em tempo constante? Deve-se mencionar que a realocação pode ocorrer e que O (1) é um custo amortizado, como um vetor.

ntã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 maio