Menu
As a result of this question from a few days ago there are a few things that have been bugging me about the complexity requirements for std::deque::push_back/push_front vs the actual std::deque implementations out in the wild.
The upshot of the previous question was that these operations are required to have O(1) worst case complexity. I verified that this was indeed the case in c++11:
from 23.3.3.4 deque modifiers, refering to insert, push/emplace front/back
Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.
This is combined with the O(1) complexity requirement for indexing, via operator[] etc.
The issue is that implementations don't strictly satisfy these requirements.
In terms of both msvc and gcc the std::deque implementation is a blocked data structure, consisting of a dynamic array of pointers to (fixed size) blocks, where each block stores a number of data elements.
In the worst case, push_back/front etc could require an extra block to be allocated (which is fine - fixed size allocation is O(1)), but it could also require that the dynamic array of block pointers be resized - this is not fine, since this is O(m) where m is the number of blocks, which at the end of the day is O(n).
Obviously this is still amortised O(1) complexity and since generally m << n it's going to be pretty fast in practice. But it seems there's an issue with conformance?
As a further point, I don't see how you can design a data structure that strictly satisfies both the O(1) complexity for both push_back/front etc and operator[]. You could have a linked-list of block pointers, but this doesn't give you the desired operator[] behaviour. Can it actually be done?
613
push_back(): Inserts a new element at the end of the vector. Its time complexity is O(1).
Complexity. In a doubly-linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1).
The interesting point is that deque is now faster than vector.
deque::push_front() is used to push/insert an element at the front or at the beginning of the deque container making the pushed/inserted element as the first element of the deque. This function accepts one argument, that is, the element which is to be pushed/inserted at the beginning.
In the C++11 FDIS, we can read:
23.2.3 Sequence containers [sequence.reqmts]
16/ Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.
Where Table 101 is named Optional sequence container operations and lists deque for the push_back and push_front operations.
Therefore, it seems more like a slight omission in the paragraph you cited. Perhaps worth a Defect Report ?
Note that the single call to a constructor still holds.
83
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
