Iterator invalidation rules for std::deque

An iterator is considered invalidated if it no longer points to the same element it originally pointed to.

For std::deque, the iterator invalidation rules are as follows:

1. End iterators: The end iterator (the one returned by end()) is always invalidated when the deque is modified.
2. Insertion: Insertion in the middle of the deque invalidates all iterators. Insertion at either end (using push_front(), emplace_front(), push_back(), emplace_back()) only invalidates the end iterator.
3. Erasure: Erasing an element in the middle of the deque invalidates all iterators. Erasing an element at either end (using pop_front() or pop_back()) only invalidates the end iterator and the iterators to the erased elements.
4. Clear: Calling clear() invalidates all iterators.
5. Swap: Calling swap() invalidates all iterators.

Here's an example demonstrating iterator invalidation:

1#include <deque>
2#include <iostream>
3
4int main() {
5  std::deque<int> d{1, 2, 3, 4, 5};
6
7  auto it = d.begin();
8  auto end = d.end();
9
10  d.push_front(0);  
11
12  // This is fine, it still points to the element 1
13  std::cout << *it << "\n"; 
14  
15  // This is invalid, end iterator is invalidated
16  std::cout << *(end - 1) << "\n"; 
17
18  d.insert(it + 2, 10);  
19  // This is invalid, it no longer points to 1
20  std::cout << *it << "\n"; 
21}

The previous example results in undefined behaviour. With debug flags enabled, the compiler may detect the problem and throw a run time error:

1cannot deference out of range deque iterator

To avoid issues with iterator invalidation, it's often best to reacquire iterators after any operation that could potentially invalidate them.