5

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).

Koban
  • 463
  • 1
  • 6
  • 12
  • 2
    Vector also says *Insertion or removal of elements at the end - amortized constant O(1)*. It just means that the reallocations are expected to be a tiny fraction of all operations. It's possible that they just omitted or forgot to write "amortized constant" in deque. – apokryfos Oct 03 '17 at 09:41
  • it is interesting what this 'tiny fraction' is? Is there some formula of 'tiny fraction'? – Koban Oct 03 '17 at 09:44
  • 1
    Well deque is not built on top of vector. It is its own data structure so it's written differently. The docs also state that: *As opposed to `std::vector`, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.* – apokryfos Oct 03 '17 at 09:46
  • I did not say it is built on std:;vector, but I said 'it is something like'... – Koban Oct 03 '17 at 09:48
  • Actually reading that again: If the internal arrays are fixed size then an allocation will be constant time O(1) albeit it will be a larger constant than an insertion without the need for allocation so amortized may not even be the case here. – apokryfos Oct 03 '17 at 09:49
  • figured out what is amortized constant : https://stackoverflow.com/questions/200384/constant-amortized-time/41739246#41739246 – Koban Oct 03 '17 at 10:06
  • Is there a reason this is tagged [tag:c++11] not simply [tag:c++]? There's nothing here that doesn't also apply to C++03, C++14 and C++17, is there? – Jonathan Wakely Oct 03 '17 at 14:07

2 Answers2

5

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.

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
4

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.

ecatmur
  • 152,476
  • 27
  • 293
  • 366
  • There's no need to keep null pointers at the front of the deque's page table (and I would be surprised if any real implementations do that). Reallocating the page table and shuffling the pointers in it is cheap and can be done as needed, when adding new pages to the front. It performs no copies/moves of the actual elements (although strictly speaking _does_ perform a number of operations proportional to the number of elements, with a constant factor k == N/M). – Jonathan Wakely Oct 03 '17 at 10:56
  • Or put another way, this answer would be a viable `std::deque` implementation strategy, but is not the answer to the question :-) The correct answer is that the standard explicitly says that the operations on those pointers are not counted in the complexity requirements. – Jonathan Wakely Oct 03 '17 at 13:54
  • 1
    @JonathanWakely according to the comment in bits/stl_deque.h, libstdc++ does employ this strategy: "*Not every pointer in the %map array will point to a node. If the initial number of elements in the deque is small, the /middle/ %map pointers will be valid, and the ones at the edges will be unused. This same situation will arise as the %map grows: available %map pointers, if any, will be on the ends.*" Interesting that it is not obligatory. – ecatmur Oct 03 '17 at 14:22
  • 1
    Doh! I should really know that ;) I was confusing myself with the fact that we can't keep hold of a page with no elements in it (for later reuse). But we certainly can keep a larger array with null pointers in. Thanks for the correction! – Jonathan Wakely Oct 06 '17 at 11:40