Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/deque"

From cppreference.com
< cpp‎ | container
m (Update links.)
(Iterator invalidation semantics)
Line 27: Line 27:
 
{{par inc | cpp/container/param list Allocator | deque}}
 
{{par inc | cpp/container/param list Allocator | deque}}
 
{{par end}}
 
{{par end}}
 +
 +
===Iterator invalidation===
 +
 +
{| class="dsctable" style="font-size:0.8em"
 +
! Operations
 +
! Invalidated
 +
|-
 +
| All read only operations, {{lc|swap}}, {{lc|std::swap}}
 +
| Never
 +
|-
 +
| {{lc|shrink_to_fit}}, {{lc|clear}}, {{lc|insert}}, {{lc|emplace}}, {{lc|push_back}}, {{lc|emplace_back}}
 +
| Always
 +
|-
 +
| {{lc|erase}}
 +
| If erasing at beginning or end - only erased elements.<br>
 +
Otherwise - all iterators are invalidated.
 +
|-
 +
| {{lc|resize}}
 +
| Only if the new size is bigger than the old one.
 +
|-
 +
| {{lc|pop_back}}, {{lc|pop_front}}
 +
| Only to the element erased
 +
|}
 +
 +
====Notes====
 +
* Under some circumstances, references are not invalidated by {{lc|insert}} and {{lc|emplace}}.
 +
* {{lc|push_back}} and {{lc|emplace_back}} do not invalidate any references.
  
 
===Member types===
 
===Member types===

Revision as of 11:29, 3 April 2014

 
C++
 
Containers library
 
std::deque
Member types
Member functions
Non-member functions
(until C++20)(until C++20)(until C++20)(until C++20)(until C++20)
Deduction guides(C++17)
 
Defined in header <deque>
template<

    class T,
    class Allocator = std::allocator<T>

> class 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.

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 - amortized 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.
T must meet the requirements of CopyAssignable and CopyConstructible. (until C++11)
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 Erasable, but many member functions impose stricter requirements. (since C++11)

[edit]

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.[edit]

Iterator invalidation

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

Member types

Member type Definition
value_type T[edit]
allocator_type Allocator[edit]
size_type Unsigned integer type (usually std::size_t)[edit]
difference_type Signed integer type (usually std::ptrdiff_t)[edit]
reference value_type&[edit]
const_reference const value_type&[edit]
pointer

Allocator::pointer

(until C++11)

std::allocator_traits<Allocator>::pointer

(since C++11)
[edit]
const_pointer

Allocator::const_pointer

(until C++11)

std::allocator_traits<Allocator>::const_pointer

(since C++11)
[edit]
iterator LegacyRandomAccessIterator to value_type[edit]
const_iterator LegacyRandomAccessIterator to const value_type[edit]
reverse_iterator std::reverse_iterator<iterator>[edit]
const_reverse_iterator std::reverse_iterator<const_iterator>[edit]

Member functions

 constructs the deque
(public member function) [edit]
destructs the deque
(public member function) [edit]
assigns values to the container
(public member function) [edit]
assigns values to the container
(public member function) [edit]
returns the associated allocator
(public member function) [edit]
Element access
access specified element with bounds checking
(public member function) [edit]
access specified element
(public member function) [edit]
access the first element
(public member function) [edit]
access the last element
(public member function) [edit]
Iterators
(C++11)
 returns an iterator to the beginning
(public member function) [edit]
(C++11)
 returns an iterator to the end
(public member function) [edit]
(C++11)
 returns a reverse iterator to the beginning
(public member function) [edit]
(C++11)
 returns a reverse iterator to the end
(public member function) [edit]
Capacity
checks whether the container is empty
(public member function) [edit]
returns the number of elements
(public member function) [edit]
returns the maximum possible number of elements
(public member function) [edit]
(DR*)
 reduces memory usage by freeing unused memory
(public member function) [edit]
Modifiers
clears the contents
(public member function) [edit]
inserts elements
(public member function) [edit]
(C++11)
 constructs element in-place
(public member function) [edit]
erases elements
(public member function) [edit]
adds an element to the end
(public member function) [edit]
(C++11)
 constructs an element in-place at the end
(public member function) [edit]
removes the last element
(public member function) [edit]
inserts an element to the beginning
(public member function) [edit]
(C++11)
 constructs an element in-place at the beginning
(public member function) [edit]
removes the first element
(public member function) [edit]
changes the number of elements stored
(public member function) [edit]
swaps the contents
(public member function) [edit]

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) [edit]
specializes the std::swap algorithm
(function template) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/deque&oldid=69349"