Why isn't deque implemented as a dynamic array?

Question

We know that std::vector in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to reach O(1) amortized push_back time. But changing capacity of a vector is essentially allocation of new memory block and copying old data into it. That means we can as well implement a vector which can grow in both directions with amorized O(1) push_back and push_front time.

But std::deque is implemented in different, rather complicated way, not storing data in a contiguous manner and suffering from related issues (e.g. more frequent page faults when iterating). Why so? Are there any obstacles disallowing to implement deque as a dynamic array?

Answer 1

The reason why std::deque is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to std::vector.

You already partially said it: changing the capacity of an std::vector requires reallocating the memory and copying the entire content to the new memory. While it is true that the std::vectorreallocation scheme achieves a O(1) amortised complexity, the implementation of std::deque guarantees a true O(1) complexity bound for appending.