std::deque - cppreference.com (original) (raw)

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, 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 a std::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 - constant O(1).
• Insertion or removal of elements at the end or beginning - constant O(1).
• Insertion or removal of elements - linear O(n).

std::deque meets the requirements of Container, AllocatorAwareContainer, SequenceContainer and ReversibleContainer.

Contents

• 1 Template parameters
• 2 Iterator invalidation
  • 2.1 Invalidation notes
• 3 Member types
• 4 Member functions
  • 4.1 Element access
  • 4.2 Iterators
  • 4.3 Capacity
  • 4.4 Modifiers
• 5 Non-member functions
• 6 Deduction guides
• 7 Notes
• 8 Example
• 9 Defect reports
• 10 See also

[edit] Template parameters

[edit] Iterator invalidation

[edit] Invalidation notes

• When inserting at either end of the deque, references are not invalidated by insert and emplace.
• push_front, push_back, emplace_front and emplace_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 by erase, pop_front and pop_back.
• A call to resize with a smaller size does not invalidate any references to non-erased elements.
• A call to resize 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 #include   int main() { // Create a deque containing integers std::deque 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 deque for (int n : d) std::cout << n << ' '; std::cout << '\n'; }

Output:

[edit] Defect reports

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

[edit] See also

| | adapts a container to provide queue (FIFO data structure) (class template) [edit] | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |