std::deque
Defined in header <deque>
|
||
template< class T, |
(1) | |
namespace pmr { template <class 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.
| ||||
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 |
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 | 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
|
| ||||
const_reference
|
| ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
RandomAccessIterator | ||||
const_iterator
|
Constant random access iterator | ||||
reverse_iterator
|
std::reverse_iterator<iterator> | ||||
const_reverse_iterator
|
std::reverse_iterator<const_iterator> |
Member functions
constructs the deque (public member function) | |
destructs the deque (public member function) | |
assigns values to the container (public member function) | |
assigns values to the container (public member function) | |
returns the associated allocator (public member function) | |
Element access | |
access specified element with bounds checking (public member function) | |
access specified element (public member function) | |
access the first element (public member function) | |
access the last element (public member function) | |
Iterators | |
returns an iterator to the beginning (public member function) | |
returns an iterator to the end (public member function) | |
returns a reverse iterator to the beginning (public member function) | |
returns a reverse iterator to the end (public member function) | |
Capacity | |
checks whether the container is empty (public member function) | |
returns the number of elements (public member function) | |
returns the maximum possible number of elements (public member function) | |
(C++11) |
reduces memory usage by freeing unused memory (public member function) |
Modifiers | |
clears the contents (public member function) | |
inserts elements (public member function) | |
(C++11) |
constructs element in-place (public member function) |
erases elements (public member function) | |
adds an element to the end (public member function) | |
(C++11) |
constructs an element in-place at the end (public member function) |
removes the last element (public member function) | |
inserts an element to the beginning (public member function) | |
(C++11) |
constructs an element in-place at the beginning (public member function) |
removes the first element (public member function) | |
changes the number of elements stored (public member function) | |
swaps the contents (public member function) |
Non-member functions
lexicographically compares the values in the deque (function template) | |
specializes the std::swap algorithm (function template) |
Example
#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