I don't think std::deque's implementation is specified in standard. It only needs to meet certain running times, and the data structure in the article — the author's "devector" — would satisfy the requirements of std::deque; i.e., the "devector" is a valid implementation of std::deque, I think. However, in practice, std::deque is not implemented this way — your link hints at this:

> As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

The usual implementation, I think, looks something like the image here[1].

[1]: http://stackoverflow.com/a/6292437/101999

> the "devector" is a valid implementation of std::deque, I think

It is not. std::deque has strict requirements that say appends/prepends may not invalidate references/iterators. A devector can not guarantee this.

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...

Ah, I thought it was both, but was just working from the top of my memory. Good for looking it up :)