Qual è la complessità delle operazioni per i contenitori std::vector e std::list in C++?

std::vector

• Доступ по индексу: O(1)
• Добавление в конец (push_back): амортизированное O(1)
• Вставка или удаление в середине: O(n), так как требуется сдвиг элементов
• Итерация: O(n)

std::list (двусвязный список)

• Доступ по индексу: O(n), так как требуется последовательный проход
• Вставка и удаление в любом месте (если есть итератор): O(1)
• Итерация: O(n)

Таким образом, vector эффективен для быстрого доступа и добавления в конец, а list — для частых вставок и удалений в середине без необходимости сдвигать элементы.