Search code examples
c++algorithmc++11time-complexitydeque

Why are std::deque subarray sizes fixed?

Background

std::deque uses subarrays to store its elements. It has an additional book keeping data structure to keep track of its subarrays. This way, compared to std::vector, std::deque can grow faster from the back (O(1) compared to amortized O(1)), and much faster in the front (O(1) compared to O(n)). This is due to the fact that std::deque can just add a subarray at either end and only have to modify its book keeping data structure.

Question

What I don't understand is why the subarrays have their sizes fixed as explained here:

typical implementations use a sequence of individually allocated fixed-size arrays

There are quite a few advantages of not having fix sized subarrays. For example, since the subarrays are fixed in size, any insertion in the middle will have to be O(n) complexity where n is the number of the elements to the closest end. However, if the subarrays are free to grow, insertion in the middle will be O(k) where k is the number of elements in the subarray which is much faster especially if the std::deque has a lot of subarrays. It's the same for deletion from the middle.

Is it because std::deque wants to keep its subarrays balanced? This can easily be mitigated by enabling subarrays to split or merge if they get too large/small. The complexity will just be O(k) where k is the size of the largest subarray. (Or the combined sizes of the smallest subarray and it's smaller neighbor)

Is it because fixed sized subarrays makes random iterating faster? For example if you want the nth element, you have to go through the book keeping data structure and add the sizes of all the previous subarrays making the complexity O(k) where k is the size of the book keeping data structure. But this is not a huge deal either since std::deque is advertised to be a doubly linked list with better caching anyways.

EDIT: std::deque is just a middle man between linked list implementation and array implementation. I guess my question has lost its original meaning and is just suggesting that it should behave more like a linked list than a vector

Solution

  • What I don't understand is why the subarrays have their sizes fixed

    Because that allows constant complexity random access which is required by the standard, as pointed out in the comments.

    But this is not a huge deal

    I disagree, and presumably so would the standard committee.

    since std::deque is advertised to be a doubly linked list ...

    It's not advertised as such.