Adding elements to std::deque: a nasty surprise

Consider the following innocent-looking code:

#include <deque>

#define MAX_VAL 1000000

int main () {
  std::deque<int> Q;

  // Insert the even numbers 0, 2, 4, ..., (2 * MAX_VAL) into Q.
  for (int i = 0; i <= MAX_VAL; ++i) {
    Q.push_back(2 * i);
  }

  // For each even element of Q, insert an odd element at its back.
  for (auto it = Q.begin(); it != Q.end(); ++it) {
    if (*it % 2 == 0) {
      Q.push_back(*it + 1);
    }
  }

  return 0;
}

You can compile this program with the command below (assuming you saved it as a file named deque.cpp):

g++ deque.cpp -std=c++11 -o deque

At first glance, one might think that adding elements to an std::deque using push_back() is safe to do inside the second for loop. For those familiar with how std::deque is implemented, the rationale might be the following: std::deque stores its elements in possibly separate blocks of memory, so inserting elements at its end should not be a problem for any iterator pointing to one of its existing elements, as new blocks of memory are automatically allocated to make room for the new elements whenever necessary, without any reallocations taking place. However, this assumption is unfortunately incorrect: if you compile the program above, it will likely crash due to a segmentation fault (if this does not happen, try increasing the value of MAX_VAL).

The problem arises from the fact that adding elements to an std::deque using push_back() invalidates all of its iterators, even though pointers and references to elements in the container remain valid (they still point to the same elements as they did before). This happens because the iterator mapping of std::deque changes when new blocks are allocated. In fact, since std::deque::iterator is of random-access type, std::deque must be aware that moving N elements forward might lead to another memory block, which means the iterator mapping has to be updated whenever a new block is created, invalidating all iterators in the process.

The lesson to be learned here is: before calling a function that manipulates the data stored in a container, make sure you understand how this function affects its iterators!