Does deque provide O (1) complexity when pasted from above

Question

I went over this post, and he claims that deque provides an efficient investment on top and bottom. However, this post here states that the temporal complexity of deque other than the inverse is O (n). I think that if deque had an effective upper and lower insert, then it would have O (1), and the vector should have O (1) only in the bottom position. I would appreciate it if anyone could clarify this.

Answer 1

Writing cppreference for std :: deque gives the following complexity:

The complexity (efficiency) of general operations on deques is as follows:

• Random Access - Permanent O (1)
• Insertion or removal of elements at the end or the beginning - amortized constant O (1)
• Insert or delete items - linear O (n)

which is consistent with the draft C ++ project 23.3.3.1 Overview of the class template template that says (highlighted by me):

Deque is a sequence container that, like vector (23.3.6), supports random access iterators. In addition, it supports inserting and deleting time at the beginning or at the end; insert and wash in the middle, take linear time. That is, deque is especially optimized for pushing and inputting elements at the beginning and end . As with vectors, storage management is handled automatically.

For std :: vector cppreference says:

The complexity (efficiency) of general operations on vectors is as follows:

• Random Access - Permanent O (1)
• Insert or delete elements at the end - amortized constant O (1)
• Insert or delete elements - linear in distance to the end of the vector O (n)

which is consistent with the draft standard section 23.3.6.1 Overview of vector template templates:

A vector is a sequence container that supports random access iterators. In addition, it maintains (depreciates) a constant insertion and erasure time of operations at the end; insert and wash in the middle, take linear time. Storage management is handled automatically, although hints can be given to increase efficiency. [...]

Answer 2

From the C ++ standard:

23.3.3.4 deque modi fiers [deque.modi fiers]

 [...] void push_front(const T& x); void push_front(T&& x); void push_back(const T& x); void push_back(T&& x); 

[...]

3 Difficulty: the complexity is linear in the number of inserted elements plus a smaller distance to the beginning and end of the deck. Inserting a single element at the beginning or at the end of deque always takes constant time and invokes a single call to T.

Emphasis on mine

Answer 3

C ++ 98, section 23.2.1 (template class class)

"Deque ... supports inserting and deleting the time constant at the beginning or at the end, pasting and erasing in the middle of dle takes linear time. That is, deque is especially optimized for pushing and popping elements to the beginning and end. As with vectors , storage management is processed automatically.

So yes: O (1) insert at both ends.