std::deque

std::deque

As opposed to std::vector

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

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

Template parameters

Iterator invalidation

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
• 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.

Member types

Member functions

Non-member functions

Notes

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 deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25

Defect reports

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

See also