std::deque

 

C++

Compiler support

Freestanding and hosted

Language

Standard library

Standard library headers

Named requirements

Feature test macros (C++20)

Language support library

Concepts library (C++20)

Metaprogramming library (C++11)

Diagnostics library

General utilities library

Strings library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Numerics library

Localizations library

Input/output library

Filesystem library (C++17)

Regular expressions library (C++11)

Concurrency support library (C++11)

Execution support library (C++26)

Technical specifications

Symbols index

External libraries

 

Containers library

Sequence

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

deque

forward_list (C++11)

list

Associative

set

multiset

map

multimap

Unordered associative

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

Adaptors

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

Views

span (C++20)

mdspan (C++23)

Tables

Iterator invalidation

Member function table

Non-member function table

 

std::deque

Member types
Member functions
deque::deque deque::~deque deque::operator= deque::assign deque::assign_range (C++23)   deque::get_allocator Element access deque::at deque::operator[] deque::front deque::back Iterators deque::begindeque::cbegin (C++11) deque::enddeque::cend (C++11) deque::rbegindeque::crbegin (C++11) deque::renddeque::crend (C++11)	Capacity deque::empty deque::size deque::max_size deque::shrink_to_fit (DR*) Modifiers deque::clear deque::insert deque::insert_range (C++23) deque::emplace deque::erase deque::push_front deque::emplace_front (C++11) deque::prepend_range (C++23) deque::pop_front deque::push_back deque::emplace_back (C++11) deque::append_range (C++23) deque::pop_back deque::resize deque::swap
Non-member functions
operator==operator<=> (C++20) swap(std::deque) erase(std::deque)erase_if(std::deque) (C++20)(C++20)	operator!=operator<operator>operator<=operator>= (until C++20)(until C++20)(until C++20)(until C++20)(until C++20)
Deduction guides(C++17)

 

Defined in header <deque>
template<     class T,     class Allocator = std::allocator<T> > class deque;	(1)
namespace pmr {     template <class T>     using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>; }	(2)	(since C++17)

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.

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.

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 Template:concept, Template:concept, Template:concept and Template:concept.

Template parameters

T	-	The type of the elements. T must meet the requirements of CopyAssignable and CopyConstructible. (until 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. (since C++11)
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. The behavior is undefined(until C++20)The program is ill-formed(since C++20) if Allocator::value_type is not the same as T.

Iterator invalidation

There are still a few inaccuracies in this section, refer to individual member function pages for more detail

Operations	Invalidated
All read only operations	Never
swap, std::swap	The past-the-end iterator may be invalidated (implementation defined)
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back	Always
erase	If erasing at begin - only erased elements If erasing at end - only erased elements and the past-the-end iterator Otherwise - all iterators are invalidated (including the past-the-end iterator).
resize	If the new size is smaller than the old one : only erased elements and the past-the-end iterator If the new size is bigger than the old one : all iterators are invalidated Otherwise - none iterators are invalidated.
pop_front	Only to the element erased
pop_back	Only to the element erased and the past-the-end iterator

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.
• If a method is common to both deque and std::vector then the run-time complexity of deque's method is no worse than the complexity of std::vector's method (and in the case of inserting to the front, deque's complexity is better).
• Despite the run-time complexity advantage of deque over std::vector described above, the std::vector container does have some advantages over the deque container:
  • Implementations of deque typically have a large overhead memory cost. For instance, the 64-bit GNU (resp. Apache, Microsoft) standard library implementation of deque uses a minimum of 656 (resp. 832, 128) bytes to store 1 object in a deque. This variability may also negatively affect portability.
  • deque typically doesn't store its elements contiguously in memory, which may make interacting with older C or C++ code more difficult. This also means that std::vectors typically have better locality in memory. This lack of locality in space, however, may give deque an advantage when dealing with a large collection of objects.
  • The better run-time complexity of some of deque's operations comes at the expense of additional book-keeping. In particular, many popular implementations of deque often store objects via an array of pointers-to-array so that accessing an element by passing an index to operator[], for instance, requires first finding the pointer that points to the array holding this element and then secondly finding the location of this element within this array.

Member types

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

Member functions

(constructor)	constructs the deque (public member function)
(destructor)	destructs the deque (public member function)
operator=	assigns values to the container (public member function)
assign	assigns values to the container (public member function)
get_allocator	returns the associated allocator (public member function)
Element access
at	access specified element with bounds checking (public member function)
operator[]	access specified element (public member function)
front	access the first element (public member function)
back	access the last element (public member function)
Iterators
begincbegin (C++11)	returns an iterator to the beginning (public member function)
endcend (C++11)	returns an iterator to the end (public member function)
rbegincrbegin (C++11)	returns a reverse iterator to the beginning (public member function)
rendcrend (C++11)	returns a reverse iterator to the end (public member function)
Capacity
empty	checks whether the container is empty (public member function)
size	returns the number of elements (public member function)
max_size	returns the maximum possible number of elements (public member function)
shrink_to_fit (DR*)	reduces memory usage by freeing unused memory (public member function)
Modifiers
clear	clears the contents (public member function)
insert	inserts elements (public member function)
emplace (C++11)	constructs element in-place (public member function)
erase	erases elements (public member function)
push_back	adds an element to the end (public member function)
emplace_back (C++11)	constructs an element in-place at the end (public member function)
pop_back	removes the last element (public member function)
push_front	inserts an element to the beginning (public member function)
emplace_front (C++11)	constructs an element in-place at the beginning (public member function)
pop_front	removes the first element (public member function)
resize	changes the number of elements stored (public member function)
swap	swaps the contents (public member function)

Non-member functions

operator==operator!=operator<operator<=operator>operator>=operator<=> (removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(C++20)	lexicographically compares the values of two deques (function template)
std::swap(std::deque)	specializes the std::swap algorithm (function template)

Example

Run this code

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

Output:

13
7
5
16
8
25