Why is the complexity of insertion or removal of elements at the end or beginning of std::deque constant O(1)?

Question

According to C++ standard std::deque is something like

std::vector<std::array<T, M> *>

If so, how is it possible that insertion or removal of elements at the end or beginning is constant O(1)? If the capacity of the vector exceeded and we insert something at the end or beginning there is no guarantee the the entire vector is not reallocated, so we have 0(N/M) that actually is 0(N), isn't it? (N is the size of the deque).

Answer 1

If the capacity of the vector exceeded and we insert something at the end or beginning there is no guarantee the the entire vector is not reallocated, so we have 0(N/M) that actually is 0(N), isn't it? (N is the size of the deque).

Yes, but no elements need to be copied/moved to reallocate that vector, only the pointers to the arrays need to be moved to the new storage.

The standard states:

[container.requirements.general]
-2- All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.

So the fact there are N/M copies of pointers isn't counted in the O(1) complexity requirement. And since those operations on pointers are very cheap, the performance of those operations is not a problem in practice. The deque needs to allocate a new page for every M elements inserted, but it never needs to reallocate the existing pages and move every existing element, so it avoids the most expensive operations on vector, so vector's exponential growth is not needed to make deques cheap.

Answer 2

Amortized constant complexity for insertion at the front is (typically) achieved by assigning from the middle of the vector of pointers outwards.

For example, if we have a deque with 3 nodes, each holding up to 4 elements, we might assign its vector of 8 pointers thus:

[ nil, nil, nil, N1*, N2*, N3*, nil, nil ]

Here N1 and N3 might themselves be partially filled:

N1: [ nil, nil, nil, 1 ]
N2: [ 2, 3, 4, 5 ]
N3: [ 6, 7, nil, nil ]

As we push_front onto the deque, first N1 is filled towards the front, then additional nodes are allocated and added to the vector of pointers. Once the vector of pointers is filled at the front, any additional push_front results in an exponential expansion with the additional space assigned at the front:

[ N1*, N2*, N3*, N4*, N5*, N6*, nil, nil ]
  |                         `---------------------------------------\
  `-----------------------------------v                             v
[ nil, nil, nil, nil, nil, nil, nil, N0*, N1*, N2*, N3*, N4*, N5*, N6*, nil, nil ]

This exponential growth policy achieves O(1) amortized complexity for both deque::push_front and deque::push_back for the same reason that vector::push_back has O(1) amortized complexity.