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.
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 - constant O(1)
- Insertion or removal of elements - linear O(n)
std::deque
meets the requirements of Container
, AllocatorAwareContainer
, SequenceContainer
and ReversibleContainer
.
Contents |
[edit] Template parameters
T | - | The type of the elements.
|
||||
Allocator | - | An allocator that is used to acquire memory to store the elements. The type must meet the requirements of Allocator . The behavior is undefined if Allocator::value_type is not the same as T.
|
[edit] 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, 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
|
||||
allocator_type
|
Allocator
|
||||
size_type
|
Unsigned integral 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> |
[edit] 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) |
[edit] Non-member functions
lexicographically compares the values in the deque (function template) |
|
specializes the std::swap algorithm (function template) |
[edit] 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