Qual é a complexidade das operações para os contêineres std::vector e std::list em C++?

std::vector

• Acesso por índice: O(1)
• Adicionar ao final (push_back): amortizado O(1)
• Inserção ou remoção no meio: O(n), pois requer deslocamento de elementos
• Iteração: O(n)

std::list (lista duplamente ligada)

• Acesso por índice: O(n), pois requer passagem sequencial
• Inserção e remoção em qualquer lugar (se houver um iterador): O(1)
• Iteração: O(n)

Assim, vector é eficiente para acesso rápido e adição ao final, enquanto list é adequado para inserções e remoções frequentes no meio sem necessidade de deslocar elementos.