Qual é a diferença entre os contêineres vector e list em C++?

O std::vector representa um array dinâmico. Os dados são armazenados em um bloco de memória contíguo.

Vantagens do vector:

• Acesso rápido por índice (O(1)).
• Boa localidade de dados, útil para o cache do processador.
• Inserção/remoção rápida no final (em média O(1)).

Desvantagens do vector:

• Complexidade na inserção/remocão em locais arbitrários (O(n)).
• Reatribuição de memória ao crescer, que requer copiar elementos.

std::list é uma lista duplamente ligada. Cada elemento armazena ponteiros para o elemento anterior e seguinte.

Vantagens do list:

• Complexidade na inserção/remocão em qualquer lugar (O(1)) após encontrar a posição (que pode ser O(n)).
• Não requer um bloco de memória contíguo.

Desvantagens do list:

• Acesso lento por índice (O(n)).
• Ocupa mais memória por elemento (devido aos ponteiros).
• Má localidade de dados.

Diferença principal:

Característica	std::vector	std::list
Estrutura de dados	Array dinâmico	Lista duplamente ligada
Armazenamento de dados	Memória contígua	Nodos com ponteiros
Acesso por índice	O(1)	O(n)
Inserção/remocão	O(n) (exceto no final)	O(1) (após o iterador)
Localidade	Boa	Má
Uso de memória	Elementos	Elementos + ponteiros

A escolha entre vector e list depende das operações típicas com o contêiner. Se acessos aleatórios e inserções/removções no final são frequentes, vector é preferido. Se inserções/removções frequentes no meio da lista são importantes, list é preferido.