Invalid random access iterator with deque

Question

I read effective STL by Scott Meyers. Here, in paragraph 1, the author mentions how to choose between different containers, and below is a piece of text with which it is difficult for me to understand.

Would it be beneficial to have a container of random access iterators where pointers and data references are not invalidated until nothing is erased and only inserts at the ends of the container occur? This is a very special case, but if this is your case, deque is the container of your dreams. (Interestingly, deques iterators can be invalidated when inserts are made only at the ends of the container. Deque is the only STL container standard whose iterators can be canceled without canceling pointers and references.)

My questions on the text above

• What does the author mean in pointers and links in the above context and how does it differ from iterators?

• How can iterators be invalidated when pasted only at the end, and yet do we have valid pointers and references?

The request is above two questions that need to be answered with a simple example.

Thanks for your time and help.

Answer 1

An iterator is often used to "loop through" to the elements of a standard library container, just as you would with an array index, for example. in a for loop.

Iterators can be invalidated for many reasons. One common case when this happens is when you use a for loop, for example:

 std::deque<int> c; for(std::deque<int>::iterator i = c.begin(); i != c.end(); ++i) { // do some stuff to the deque elements here } 

At the end of the above loop, the iterator i will point to the "element" one block after the last valid element in deque. If you tried to do something like

 *i = 88; 

immediately after the above for loop ends, which will be a problem because the container does not “own” the memory i “points” to.

But what Meyers is likely to say is that the Standard leaves much of the deque implementation open to the designer. Deques are usually implemented as linked lists of memory blocks containing several elements, so unlike vectors, there is no guarantee that elements will be next to each other in memory. In addition, iterators necessarily contain information about these “blocks” so that they can freely pass them (that is, iterators are not just pointers).

For example, if I push_back() new element, but there is no more space in the “last” memory fragment, then deque will need to allocate a new memory block for the new element (and add future elements to the end). Since the iterator I used earlier may not be aware of this new piece of memory, it may not be valid.

On the other hand, references and actual pointers will be used in this context to indicate / indicate individual objects in the container. If i write

 int& j = *c.begin(); 

then j is a reference to the first element of c . If I do then

 c.push_front(74); 

j still refers to the previous first element, even if it is no longer in front of the deck.

However , if you insert something into the middle of deque, then most likely you are effectively chopping one of these adjacent pieces of memory and trying to compress your new element there. To free up space, elements on one side or the other should be mixed in memory (and, perhaps, a new memory needs to be allocated). This, of necessity, will invalidate pointers / references to elements on this "side" of the insert. Since the developer understands how precisely the place for the inserted element is made, all bids are disabled relative to any pointer / link, regardless of where it is relative to the insert.

Answer 2

For the first part, this meant the following:

 deque<int> foo(10, 1); // a deque with ten elements with value of 1 int& bar = foo.front(); // reference int* baz = &foo.front(); // pointer deque<int>::iterator buz = foo.begin(); // iterator deque.push_front(0); // At this point bar and baz are still valid, but buz may have been invalidated 

For the second part, this has been described in detail here:

Why are push_back or push_front invalid deque iterators?