1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh. Apparently resource I was reading mistakenly stated it's amortised O(1)... Thank you for clarifying! $\endgroup$ – Tigran Saluev Jan 24 '18 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.