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 tostd::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.

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of astd::vector because it does not involve copying of the existing elements to a new memory location. On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++).

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

• Random access - constantO(1).
• Insertion or removal of elements at the end or beginning - constantO(1).
• Insertion or removal of elements - linearO(n).

std::deque meets the requirements ofContainer,AllocatorAwareContainer,SequenceContainer andReversibleContainer.

[edit]Template parameters

[edit]Iterator invalidation

[edit]Invalidation notes

• When inserting at either end of the deque, references are not invalidated byinsert andemplace.
• push_front,push_back,emplace_front andemplace_back do not invalidate any references to elements of the deque.
• When erasing at either end of the deque, references to non-erased elements are not invalidated byerase,pop_front andpop_back.
• A call toresize with a smaller size does not invalidate any references to non-erased elements.
• A call toresize with a bigger size does not invalidate any references to elements of the deque.

[edit]Member types

[edit]Member functions

[edit]Non-member functions

[edit]Notes

[edit]Example

#include <deque>#include <iostream> int main(){// Create a deque containing integers    std::deque<int> d={7,5,16,8}; // Add an integer to the beginning and end of the deque    d.push_front(13);    d.push_back(25); // Iterate and print values of dequefor(int n: d)std::cout<< n<<' ';std::cout<<'\n';}

13 7 5 16 8 25

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Polski
• Português
• Русский
• 中文