How does the speed of inserting elements into list and vector containers differ?

Inserting elements into std::list and std::vector differs in speed due to their internal structure:

• std::list — this is a doubly linked list. Inserting an element anywhere in the list (if an iterator to the position exists) takes constant time O(1), as it only requires reassigning neighboring pointers.

• std::vector — this is a dynamic array. Inserting at the end is usually amortized O(1), but inserting in the middle or at the beginning requires shifting all subsequent elements, which takes O(n) time. Additionally, when the vector overflows, it allocates new memory and copies elements, which also affects performance.

Summary:

• For frequent insertions in the middle or at the beginning, it is better to use list.
• For insertions at the end and quick access by index, vector is preferable.

Example:

std::list<int> lst = {1, 2, 3};
auto it = std::next(lst.begin());
lst.insert(it, 10); // insertion in O(1)

std::vector<int> vec = {1, 2, 3};
vec.insert(vec.begin() + 1, 10); // insertion in O(n), shifting elements