##### cppreference.com

##### Search

Create account

##### Namespaces

- Page
- Discussion

##### Variants

##### Views

- View
- Edit
- History

##### Actions

# std::deque

From cppreference.com
< cpp‎ | container

Defined in header `<deque>` |  |
template< class T, class Allocator = std::allocator<T> > class 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.

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 - amortized constant O(1)
- Insertion or removal of elements - linear O(n)

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

### [edit] 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 `MoveConstructible` and `MoveAssignable`, but many member functions impose stricter requirements. | (since C++11)
[edit]
Allocator | - | An allocator that is used to acquire memory to store the elements. The type must meet the requirements of `Allocator`. [edit]

### [edit] Iterator invalidation

| This section is incomplete

There are still a few inaccuracies in this section.

Operations | Invalidated
--- | ---
All read only operations, swap, std::swap | Never
shrink_to_fit, clear, insert, emplace, push_back, emplace_back | Always
erase | If erasing at beginning or end - only erased elements. Otherwise - all iterators are invalidated.
resize | Only if the new size is bigger than the old one.
pop_back, pop_front | Only to the element erased

#### [edit] Notes

- Under some circumstances, references are not invalidated by insert and emplace.
- push_back and emplace_back do not invalidate any references.

### [edit] Member types

Member type | Definition
`value_type` | `T` [edit]
`allocator_type` | `Allocator` [edit]
`size_type` | Unsigned integral type (usually std::size_t) [edit]
`difference_type` | Signed integer type (usually std::ptrdiff_t) [edit]
`reference` |
`Allocator::reference` | (until C++11)
`value_type&` | (since C++11)
[edit]
`const_reference` |
`Allocator::const_reference` | (until C++11)
`const value_type&` | (since C++11)
[edit]
`pointer` |
`Allocator::pointer` | (until C++11)
std::allocator_traits<Allocator>::pointer | (since C++11)
[edit]
`const_pointer` |
`Allocator::const_pointer` | (until C++11)
std::allocator_traits<Allocator>::const_pointer | (since C++11)
[edit]
`iterator` | `RandomAccessIterator` [edit]
`const_iterator` | Constant random access iterator [edit]
`reverse_iterator` | std::reverse_iterator<iterator> [edit]
`const_reverse_iterator` | std::reverse_iterator<const_iterator> [edit]

### [edit] Member functions

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

### [edit] Non-member functions

operator==operator!=operator<operator<=operator>operator>= | lexicographically compares the values in the deque (function template) [edit]
std::swap(std::deque) | specializes the std::swap algorithm (function template) [edit]

Retrieved from "http://en.cppreference.com/mwiki/index.php?title=cpp/container/deque&oldid=69357"
Category:

- Todo without reason