std::deque

std::deque (double-ended queue) is an indexed sequence container that supports fast insertion and removal at both ends.

Unlike std::vector, a deque does not store its elements in one single contiguous block. It still offers random-access indexing, but its segmented storage changes the iterator-invalidation and memory-locality tradeoffs.

# Declarations

template<
class T,
class Allocator = std::allocator<T>
> class deque;

namespace pmr {
template< class T >
using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}

(since C++17)

# 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';
}

deque is a good fit when the program needs cheap growth at both the front and the back while keeping indexed access.

# Template parameters

• T: element type. The exact requirements depend on the operations used. In general, elements must be erasable, and many operations impose stronger construction, assignment, or move requirements.
• Allocator: allocator used to obtain storage and manage element lifetimes. It must satisfy the Allocator requirements. Since C++20, the program is ill-formed if Allocator::value_type is not T.

# Member types

# Iterator invalidation

# Invalidation notes

• Insertions at either end do not invalidate references to existing elements.
• Erasing at either end does not invalidate references to non-erased elements.
• Resizing larger invalidates iterators but does not invalidate references to existing elements.
• Resizing smaller preserves references to non-erased elements.

# Reference map

# Notes

deque offers constant-time insertion and removal at both ends, but it does not provide the same contiguous-storage guarantee as vector.

That makes deque attractive for front/back growth patterns, but less suitable for APIs that require a pointer to one contiguous array buffer.

# Feature-test macros

# Defect reports

# See also

• vector
• list
• queue