Defined in header
std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.
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.
The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location.
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)