Consider the following innocent-looking code:

#include <deque>

#define MAX_VAL 500

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;
}

On Linux, you can compile this program with the command below (assuming you saved it on a file called deque.cpp):

g++ deque.cpp -std=c++0x -o deque

At first glance, one might think that adding elements to an std::deque via push_back() is a safe thing to do inside the second for loop. For those familiar with std::deque, 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; in other words, no reallocations are done". Well, this is unfortunately wrong: if you compile the program above, it will probably crash due to segmentation faults which seem to come from nowhere (if this does not happen, try increasing the value of MAX_VAL).

The problem comes from the fact that adding elements to an std::deque using push_back() invalidates all its iterators even though pointers and references to elements in the container remain valid (they still refer to the same elements as they did before push_back() was called). This happens because the iterator mapping of std::deque changes when new blocks are allocated. In fact, since std::deque::iterator is of random-acess type, std::deque must know that moving N elements forward might get us into another (possible the newly allocated) memory block, meaning the iterator mapping has to be updated to become aware of the newly created block. Sadly, as I said above, this change invalidates all iterators.

The lesson to be learned here is: before calling a function which manipulates the data stored in a container, it's important to understand how this function impacts its iterators!