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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top