The cppreference entry for std::deque gives the following complexity:
The complexity (efficiency) of common operations on deques is as follows:
- Random access - constant O(1)
- Insertion or removal of elements at the end or beginning - amortized constant O(1)
- Insertion or removal of elements - linear O(n)
which is consistent with the draft C++ standard section 23.3.3.1
Class template deque overview which says (emphasis mine):
A deque is a sequence container that, like a vector (23.3.6), supports random access iterators. In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. That is, a deque is especially optimized for pushing and popping elements at the beginning and end. As with vectors, storage management is handled automatically.
For std::vector cppreference says:
The complexity (efficiency) of common operations on vectors is as follows:
- Random access - constant O(1)
- Insertion or removal of elements at the end - amortized constant O(1)
- Insertion or removal of elements - linear in distance to the end of the vector O(n)
which is consistent with the draft standard section 23.3.6.1
Class template vector overview:
A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency.[...]