Why is appending std::deque object to itself through std::copy successful if the deque is not large enough?

Question

The book is right, I just misread a line.

As the answer by @uneven_mark clearly points out, the following question hinges upon a misreading of mine.

While reading The C++ Standard Library (2nd edition) by Josuttis, I got somehow convinced that coll at page 457 is declared as a std::deque (on the contrary, it is declared as std::list!), hence I asked this question.

I hope it can serve as food for thought for the readers.

ORIGINAL QUESTION:

At page 456 of "The C++ Standard Library (2nd edition)", Josuttis remarks that before you call

copy(coll.begin(), coll.end(), back_inserter(coll));

on a coll of class std::vector, you must ensure that coll has enough space (in this case, that it has a capacity at least twice its size), otherwise

the algorithm invalidates the passed source iterators while running.

Contrariwise, at page 458, he doesn't say anything similar for the case of

copy(coll.begin(), coll.end(), front_inserter(coll));

as applied to a coll of class std::deque, even though, at page 286, the following is specified about the std::deque container:

[...] when elements are inserted at the front or the back. In this case, references and pointers to elements stay valid, but iterators don’t.

hence my doubt. (Yes, I know std::deque doesn't even offer a reserve-like member function.)

As long as I have understood this answer, my understanding is that the front_inserter(coll) iterator can cause a reallocation of the array of pointers (which is a legal way of implementing std::deque), and cannot cause reallocation of the arrays in which the actual elements of coll are stored, thus leaving references/pointers to the elements valid, while invalidating the iterators, whose correct behavior (I'm thinking of how operator++ could be implmented) relies on both the array of pointers and the pointed-to arrays.

If this is true, then I guess that the parameter corresponding to copy's argument coll.begin() gets invalidated at the moment the assignment to it causes a reallocation of the array of pointers.

Answer 1

Page 455/456 of the book introduces std::back_inserter, while page 457/458 introduces std::front_insert. There is a short explanation in each case, including a list of applicable container. Each section has a code snippet as example, with only one of the applicable containers chosen to exemplify the usage.

For std::back_inserter, as container std::vector is chosen and a comment in the code snippets mentions, why it is necessary to first reserve enough space in the vector.

For std::front_inserter the author chose std::list, not std::deque. std::list does not invalidate references or iterators on insert, therefore

copy(coll.begin(), coll.end(), front_inserter(coll));

is fine, see [list.modifiers]/1 of the current C++ draft.

There is therefore in both cases no error in the author's code. I suppose he did never intend to fully explain the dangers of copying into a container itself, but simply chose these cases, because it allowed him to write shorter complete usage examples.

I think for the case where coll is a std::deque this is clearly undefined behavior. std::front_inserter inserts elements by calls to push_front (see [front.insert.iter.ops]/2), which invalidates all iterators (see [deque.modifiers]/1):

At the same time std::copys behavior is [alg.copy]/4:

Effects: Copies elements in the range [first, last) into the range [result, result + N) starting from first and proceeding to last. For each non-negative integer n < N, performs *(result + n) = *(first + n).

After the first insert, first is invalidated and undefined behavior will be caused.