vector vs list vs deque, and iterator invalidation

Choose `vector` by default. Contiguous memory makes it fast in practice, even for some middle insertions on small sizes, because CPUs are good at sequential memory. Use deque when you need fast pushes at both ends, as in a queue or sliding window. Use list only when you splice or erase at known positions a lot and need iterators to stay valid. Note that finding a position in a list is still O(n).

Iterator invalidation. Some operations make existing iterators, pointers and references to elements unusable. Using them afterwards is undefined behaviour.

• vector: push_back invalidates everything if it reallocates (when size exceeds capacity). Otherwise only end() changes. insert/erase invalidate everything from that position onwards.
• deque: inserting at either end invalidates all iterators, but references to existing elements stay valid. Erasing in the middle invalidates everything.
• list: only iterators to the erased elements are invalidated.

Classic bug

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it % 2 == 0) v.erase(it);        // 'it' is invalid after erase

Fix: it = v.erase(it); and increment only in the else branch. Better still, use the erase–remove idiom, or std::erase_if(v, pred) in C++20. Another common one: keeping int &first = v[0]; and then calling push_back.