Nitpick, the operation seems to be allowed to invalidate iterators, though not references. "An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque" [1] There might be some cases where it would be practical to simply not free the previously used memory, such that after N increases in size there are N copies of each element. This would only roughly double the space required.

[1] C++ working draft, 11 megabytes; http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...