How deque has amortized constant time complexity

Question

I read here from the accepted answer that std :: deque has the following attribute

1- Random access - constant O(1) 2- Insertion or removal of elements at the end or beginning - amortized constant O(1) 3- Insertion or removal of elements - linear O(n) 

My question is about point 2. How can deque have a fixed constant insert at the end or the beginning?

I understand that a std::vector has amortized constant time complexity for insertions at the end. This is due to the fact that the vector is conditional and is a dynamic array. Therefore, when it ends up push_back , it allocates a whole new block of memory, copies the existing items from the old location to the new location, and then deletes the items from the old location. This operation, which I understand, is amortized over time. How does this relate to deque? As the inserts at the top and bottom of the deck are amortized constant. I got the impression that it should be constant O (1). I know that a deck consists of pieces of memory.

Answer 1

A typical deque implementation is basically a vector of pointers to nodes of a fixed size.

Allocating a fixed-size node clearly has constant complexity, so it’s easy to handle - you simply amortize the cost of allocating one node by the number of elements in that node to get constant complexity for each.

The vector of the pointer part is what is (slightly) more interesting. When we select enough nodes of a fixed size so that the pointer vector is full, we need to increase the size of the vector. Like std::vector , we need to copy its contents to the newly selected vector, so its growth should correspond to a geometric (and not arithmetic) progression. This means that we have more pointers to copy, we make copies less and less, so the total time spent copying pointers remains constant.

As a side note: the "vector" part is usually treated as a circular buffer, so if you use your deque as a queue, constantly adding to one end and deleting from the other does not redistribute the vector - it just means moving the head and tail pointers, which track which of the pointers is “active” at a given time.

Answer 2

The answer (of the profane) lies in the containers. requirements.general, 23.2.1 / 2:

All requirements for complexity in this section are indicated exclusively in terms of the number of operations on contained objects.

The redistribution of the array of pointers, therefore, is not covered by the guarantee of the complexity of the standard and can take arbitrarily long. As mentioned earlier, it probably adds amortized fixed overhead for every call to push_front() / push_back() (or the equivalent modifier) ​​in any “healthy” implementation. However, I would not recommend using deque in RT-critical code. Typically, in an RT script, you don’t want to have unlimited queues or stacks (which in C ++ by default use deque as the base container) in any case, nor memory allocations that might fail, so you will most likely use a pre-allocated ring buffer (e.g. Boost circular_buffer ).