Как различается по скорости выполнение операции вставки элементов в контейнеры list и vector?

Вставка элементов в std::list и std::vector отличается по скорости из-за их внутренней структуры:

• std::list — это двусвязный список. Вставка элемента в любое место списка (если есть итератор на позицию) происходит за константное время O(1), так как нужно просто перенастроить указатели соседних элементов.

• std::vector — это динамический массив. Вставка в конец обычно амортизированно за O(1), но вставка в середину или начало требует сдвига всех последующих элементов, что занимает O(n) времени. Кроме того, при переполнении вектора происходит выделение новой памяти и копирование элементов, что тоже влияет на производительность.

Итог:

• Для частых вставок в середину или начало лучше использовать list.
• Для вставок в конец и быстрого доступа по индексу лучше vector.

Пример:

std::list<int> lst = {1, 2, 3};
auto it = std::next(lst.begin());
lst.insert(it, 10); // вставка за O(1)

std::vector<int> vec = {1, 2, 3};
vec.insert(vec.begin() + 1, 10); // вставка за O(n), сдвиг элементов