Why does push_back or push_front invalidate a deque's iterators?

The C++ standard doesn't specify how deque is implemented. It isn't required to allocate new space by allocating a new chunk and chaining it on to the previous ones, all that's required is that insertion at each end be amortized constant time So, while it's easy to see how to implement deque such that it gives the guarantee you want*, that's not the only way to do it * Iterators have a reference to an element, plus a reference to the block it's in so that they can continue forward/back off the ends of the block when they reach them. Plus I suppose a reference to the deque itself, so that operator can be constant-time as expected for random-access iterators -- following a chain of links from block to block isn't good enough.

The C++ standard doesn't specify how deque is implemented. It isn't required to allocate new space by allocating a new chunk and chaining it on to the previous ones, all that's required is that insertion at each end be amortized constant time. So, while it's easy to see how to implement deque such that it gives the guarantee you want*, that's not the only way to do it.

* Iterators have a reference to an element, plus a reference to the block it's in so that they can continue forward/back off the ends of the block when they reach them. Plus I suppose a reference to the deque itself, so that operator+ can be constant-time as expected for random-access iterators -- following a chain of links from block to block isn't good enough.

What's more interesting is that push_back and push_front will not invalidate any references to a deque's elements. Only iterators are to be assumed invalid. The standard, to my knowledge, doesn't state why.

However if an iterator were implemented that was aware of its immediate neighbors - as a list is - that iterator would become invalid if it pointed to an element that was both at the edge of the deque and the edge of a block.

3 Another reason I think is that the iterator could be implemented by keeping an index of an element. If something is inserted at the begin/end of the deque, that index is now not valid anymore (off-by-one), although any pointer/reference to that element it was pointing to is still valid, since no reallocation happened, of course). Same when we keep in index into an array of block-pointers (as I guessed in my comment on the question).

– Johannes Schaub - litb May 27 '09 at 8:34.

The key thing is not to make any assumptions just treat the iterator as if it will be invalidated. Even if it works fine now, a later version of the compiler or the compiler for a different platform might come along and break your code. Alternatively, a colleague might come along and decide to turn your deque into a vector or linked list.

My guess. Push_back/push_front can allocate a new memory block. A deque iterator must know when increment/decrement operator should jump into the next block.

The implementation may store that information in iterator itself. Incrementing/decrementing an old iterator after push_back/push_front may not work as intended. This code may or may not fail with run time error.

On my Visual Studio it failed in debug mode but run to the conclusion in release mode. On Linux it caused segmentation fault. #include #include int main() { std::deque x(1), y(1); std::deque::iterator iterx = x.begin(); std::deque::iterator itery = y.begin(); for (int i=1; iPush_back(i); y.

Push_back(i); ++iterx; ++itery; if(*iterx! = *itery) { std::cout.

Even when you are allocating in chunks, an insert will cause that particular chunk to be reallocated if there isn't enough space (as is the case with vectors).

Deque is typically implemented as a circular buffer. If it needs to allocate more space, it needs to copy items from the old buffer to the new one, invalidating any pointers to the old buffer.

1 I do not think that this is true, especially if references are to remain valid after a resize. – mmocny Oct 6 '10 at 18:52.

Because the standard says it can. It does not mandate that deque be implemented as a list of chunks. It mandates a particular interface with particular pre and post conditions and particular algorithmic complexity minimums.

Implementors are free to implement the thing in whatever way they choose, so long as it meets all of those requirements. A sensible implementation might use lists of chunks, or it might use some other technique with different trade-offs. It's probably impossible to say that one technique is strictly better than another for all users in all situations.

Which is why the standard gives implementors some freedom to choose.

I don't think you mean a list (eg, std::list) of chunks, as then random-access iterators could not be O(1). – Jared Grubb Apr 14 at 21:11 A cursory glance at one implementation suggests that a deque is more like a std::vector >, where the inner vector is fixed-reserved and never grows; however this isnt exactly right, since a pop_front from a vector would shift elements. However, a deque::iterator would really be a pair of iterators.

The inner iterator never invalidates (hence why dereferences are still valid), but the outer one can go bad if the outer container reallocates. So, after a few ++iter's, you may crawl off the end of the inner chunk and have to reset to the next chunk via the outer iterator, and boom. – Jared Grubb Apr 14 at 21:20.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.