Difference between revisions of "cpp/container/deque"
| Line 17: | Line 17: | ||
* Random access - constant {{math|O(1)}} | * Random access - constant {{math|O(1)}} | ||
| − | * Insertion or removal of elements at the end or beginning - | + | * Insertion or removal of elements at the end or beginning - constant {{math|O(1)}} |
* Insertion or removal of elements - linear {{math|O(n)}} | * Insertion or removal of elements - linear {{math|O(n)}} | ||
Revision as of 12:56, 4 August 2015
| Defined in header <deque>
|
||
| template< class 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.
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 Template:concept, Template:concept, Template:concept and Template:concept.
Contents |
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(until C++20)The program is ill-formed(since C++20) 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, 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 |
Notes
- Under some circumstances, references are not invalidated by insert and emplace.
- push_back and emplace_back do not invalidate any references.
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
|
value_type& | ||||
const_reference
|
const value_type& | ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
LegacyRandomAccessIterator to value_type
| ||||
const_iterator
|
LegacyRandomAccessIterator to const value_type | ||||
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 | |
| (C++11) |
returns an iterator to the beginning (public member function) |
| (C++11) |
returns an iterator to the end (public member function) |
| (C++11) |
returns a reverse iterator to the beginning (public member function) |
| (C++11) |
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) | |
| (DR*) |
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
| (removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(C++20) |
lexicographically compares the values of two deques (function template) |
| specializes the std::swap algorithm (function template) |
