Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++98)
- Detailed
template< class T, /* ... */ >
class deque;
- Regular (since C++98)
- Polymorphic (since C++17)
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>>;
}
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.
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
|
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
The behavior is undefined if Allocator::value_type is not the same as T .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 (do C++11)std::allocator_traits<Allocator>::pointer (od C++11) |
pub | const_pointer | Allocator::const_pointer (do C++11)std::allocator_traits<Allocator>::const_pointer (od 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 (od C++11) | Returns an |
pub | end cend (od C++11) | Returns an |
pub | rbegin crbegin (od C++11) | Returns a reverse |
pub | rend crend (od C++11) | Returns a reverse |
Capacity
pub | empty | Returns |
pub | size | Returns the number of elements. |
pub | max_size | Returns the maximum possible number of elements. |
pub | shrink_to_fit (od C++11) | Reduces memory usage by freeing unused memory. |
Modifiers
pub | clear | Clears the contents of a deque. |
pub | insert | Inserts elements. |
pub | emplace (od C++11) | Constructs a new element in place. |
pub | erase | Erases elements. |
pub | push_back | Appends an element to the end. |
pub | emplace_back (od 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 (od 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<=> (od 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 |
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
satisfiesLegacyInputIterator
Alo
satisfiesAllocator
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
#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 << ' ';
}
}
13 7 5 16 8 25
Hover to see the original license.