std::deque
<deque>
class T,
class Allocator = std::allocator <T>
template< class T >
using deque = std::deque<T, std::pmr::polymorphic_allocator <T>>;
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 are constexpr: it is possible to create and use std::deque objects in the evaluation of a constant expression.However, std::deque objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression.
Contents
[edit] Template parameters
Allocator::value_type is not the same as T.[edit]
[edit] Iterator invalidation
Reason: 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. It is unspecified when the past-the-end iterator is invalidated. (until C++11)The past-the-end iterator is also invalidated unless the erased |
| 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. |
| pop_front , pop_back | To the element erased.
The past-the-end iterator may be invalidated (implementation defined). (until C++11)The past-the-end iterator is also invalidated. (since C++11) |
[edit] 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.
[edit] Member types
pointer
Allocator::pointer
std::allocator_traits <Allocator>::pointer
(since C++11)const_pointer
Allocator::const_pointer
std::allocator_traits <Allocator>::const_pointer
(since C++11)iterator
value_type[edit]
const_iterator
reverse_iterator
const_reverse_iterator
[edit] Member functions
Element access
Iterators
Capacity
Modifiers
[edit] Non-member functions
deques (function template) [edit]
Deduction guides
(since C++17)[edit] Notes
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_containers_ranges |
202202L |
(C++23) | Ranges construction and insertion for containers |
__cpp_lib_constexpr_deque |
202502L |
(C++26) | constexpr std::deque
|
[edit] Example
#include <deque> #include <iostream> 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 << ' '; std::cout << '\n'; }
Output:
13 7 5 16 8 25
[edit] Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 230 | C++98 | T was not required to be CopyConstructible (an element of type T might not be able to be constructed)
|
T is also required tobe CopyConstructible |