caution

Note, this article is not finished! You can help by editing this doc page.

Overview

Simplified (since C++98)

template< class T, /* ... */ >
class deque;

Detailed

Regular (since C++98)

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

Polymorphic (since C++17)

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

Deque (double-ended queue) is a container that allows fast insertion and deletion from both the beggining and the end.

Unlike std::queue or std::priority_queue it's not a container adapter.

Technical definition of a deque

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.

std::deque

Defined in

queue

Template parameters

pub	T	The type of the elements. since C++11 The requirements that are imposed on the elements depend on the actual operations performed on the container. Generally, it is required that element type is a complete type and meets the requirements of Erasable, but many member functions impose stricter requirements. until C++11 T must meet the requirements of CopyAssignable and CopyConstructible.
pub	Allocator	An allocator that is used to acquire/release memory and to construct/destroy the elements in that memory. The type must meet the requirements of Allocator. since C++11 The behavior is undefined if Allocator::value_type is not the same as T. until C++11 The program is ill-formed if Allocator::value_type is not the same as T.

Type names

pub	value_type	T
pub	allocator_type	Allocator
pub	size_type	Unsigned integer type (usuallly std::size_t)
pub	difference_type	Signed integer type (usuallly std::ptrdiff_t)
pub	reference	value_type&
pub	const_reference	const value_type&
pub	pointer	Allocator::pointer (until C++11) std::allocator_traits<Allocator>::pointer (since C++11)
pub	const_pointer	Allocator::const_pointer (until C++11) std::allocator_traits<Allocator>::const_pointer (since C++11)
pub	iterator	LegacyRandomAccessIterator
pub	const_iterator	LegacyRandomAccessIterator
pub	reverse_iterator	std::reverse_iterator<iterator>
pub	const_reverse_iterator	std::reverse_iterator<const_iterator>

Member functions

pub	(constructors)	Constructs a deque.
pub	(destructor)	Destroys the deque, deallocating internal storage if used.
pub	operator=	Assigns values to the container.
pub	assign	Assigns values to the container.
pub	get_allocator	Returns the associated allocator.

Element access

pub	at	Accesses a specified element with bounds checking.
pub	operator[]	Accesses a specified element.
pub	front	Returns the first element.
pub	back	Returns the last element.

Iterators

pub	begin cbegin (since C++11)	Returns an iterator/const_iterator to the beginning.
pub	end cend (since C++11)	Returns an iterator/const_iterator to the end.
pub	rbegin crbegin (since C++11)	Returns a reverse iterator/const_iterator to the beginning.
pub	rend crend (since C++11)	Returns a reverse iterator/const_iterator to the end.

Capacity

pub	empty	Returns true if the deque is empty, otherwise false.
pub	size	Returns the number of elements.
pub	max_size	Returns the maximum possible number of elements.
pub	shrink_to_fit (since C++11)	Reduces memory usage by freeing unused memory.

Modifiers

pub	clear	Clears the contents of a deque.
pub	insert	Inserts elements.
pub	emplace (since C++11)	Constructs a new element in place.
pub	erase	Erases elements.
pub	push_back	Appends an element to the end.
pub	emplace_back (since C++11)	Constructs new element in-place at the end.
pub	pop_back	Removes the last element.
pub	push_front	Adds a new element to the beggining.
pub	emplace_front (since C++11)	Constructs new element in-place at the beginning.
pub	pop_front	Removes the first element.
pub	resize	Changes the number of elements stored.
pub	swap	Swaps two deques.

Non-member functions

pub	operator== operator!= (removed in C++20) operator< (removed in C++20) operator> (removed in C++20) operator<= (removed in C++20) operator>= (removed in C++20) operator<=> (since C++20)	Lexicographically compares the values in the deque.
pub	std::swap (std::deque)	An overload for a std::swap algorithm.
pub	erase (std::deque) erase_if (std::deque)	Overloads for std::erase/std::erase_if algorithms.

Helper classes

pub

std::uses_allocator (std::deque)

Specializes the std::uses_allocator type trait.

Deduction guides (since C++17)

Click to expand

// (1) (since C++17)
template< class InputIt,
          class Alloc = std::allocator<
            typename std::iterator_traits<InputIt>::value_type
          >
        >
deque( InputIt, InputIt, Alloc = Alloc() )
  -> deque<typename std::iterator_traits<InputIt>::value_type, Alloc>;

(1) allows deduction from an iterator range.

Overload resolution

In order for (1) to participate in overload resolution, the folllowing requirements must be met:

• InputIt satisfies LegacyInputIterator
• Alo satisfies Allocator

note

The extent to which the library determines that a type does not satisfy LegacyInputIterator is unspecified, except that as a minimum:

• Integral types do not qualify as input iterators.

Likewise, the extent to which it determines that a type does not satisfy Allocator is unspecified, except that as a minimum:

• The member type Alloc::value_type must exist.
• The expression std::declval<Alloc&>().allocate(std::size_t{}) must be well-formed when treated as an unevaluated operand.

Examples

Basic manipulation

Initialize the queue, add values and print the contents

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

Result

13 7 5 16 8 25