# std::deque

From cppreference.com
< cpp‎ | container

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, with additional bookkeeping, which means indexed access to std: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`.

### 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 if Allocator::value_type is not the same as T.

### Iterator invalidation

| This section is incomplete

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

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

### 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`

`Allocator::reference` | (until C++11)
`value_type&` | (since C++11)

`const_reference`

`Allocator::const_reference` | (until C++11)
`const value_type&` | (since C++11)

`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` | `RandomAccessIterator`
`const_iterator` | Constant random access iterator
`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

begin cbegin | returns an iterator to the beginning (public member function)
end cend | returns an iterator to the end (public member function)
rbegin crbegin | returns a reverse iterator to the beginning (public member function)
rend crend | 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 (C++11) | 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>= | lexicographically compares the values in the deque (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

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

- Todo without reason