Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/deque"

From cppreference.com
< cpp‎ | container
(Iterator invalidation semantics)
m (→‎Deduction guides: ~)
 
(48 intermediate revisions by 23 users not shown)
Line 1: Line 1:
 
{{cpp/title|deque}}
 
{{cpp/title|deque}}
 
{{cpp/container/deque/navbar}}
 
{{cpp/container/deque/navbar}}
−
{{ddcl | header=deque |
+
{{dcl begin}}
 +
{{dcl header|deque}}
 +
{{dcl|num=1|1=
 
template<
 
template<
 
     class T,
 
     class T,
−
     class Allocator {{=}} std::allocator<T>
+
     class Allocator = std::allocator<T>
 
> class deque;
 
> class deque;
−
}}  
+
}}
 +
{{dcl|num=2|since=c++17|1=
 +
namespace pmr {
 +
    template< class T >
 +
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
 +
}
 +
}}
 +
{{dcl end}}
  
 
{{tt|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.
 
{{tt|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 {{lc|std::vector}}, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.
+
As opposed to {{lc|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 {{lc|std::vector}} because it does not involve copying of the existing elements to a new memory location.
+
The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a {{lc|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:
 
The complexity (efficiency) of common operations on deques is as follows:
  
−
* Random access - constant {{math|O(1)}}
+
* Random access - constant {{math|O(1)}}.
−
* Insertion or removal of elements at the end or beginning - amortized constant {{math|O(1)}}
+
* 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)}}.
  
−
{{tt|std::deque}} meets the requirements of {{concept|Container}}, {{concept|AllocatorAwareContainer}}, {{concept|SequenceContainer}} and {{concept|ReversibleContainer}}.
+
{{tt|std::deque}} meets the requirements of {{named req|Container}}, {{named req|AllocatorAwareContainer}}, {{named req|SequenceContainer}} and {{named req|ReversibleContainer}}.
  
 
===Template parameters===
 
===Template parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par inc | cpp/container/param list T | deque}}
+
{{par inc|cpp/container/param list T|deque}}
−
{{par inc | cpp/container/param list Allocator | deque}}
+
{{par inc|cpp/container/param list Allocator|deque}}
 
{{par end}}
 
{{par end}}
  
 
===Iterator invalidation===
 
===Iterator invalidation===
 +
{{todo|There are still a few inaccuracies in this section, refer to individual member function pages for more detail}}
  
−
{| class="dsctable" style="font-size:0.8em"
+
{|class="dsctable" style="font-size:0.9em"
−
! Operations
+
!Operations
−
! Invalidated
+
!Invalidated
 
|-
 
|-
−
| All read only operations, {{lc|swap}}, {{lc|std::swap}}
+
|All read only operations.
−
| Never
+
|Never.
 
|-
 
|-
−
| {{lc|shrink_to_fit}}, {{lc|clear}}, {{lc|insert}}, {{lc|emplace}}, {{lc|push_back}}, {{lc|emplace_back}}
+
|{{lc|swap}}, {{lc|std::swap}}
−
| Always
+
|The past-the-end iterator may be invalidated (implementation defined).
 
|-
 
|-
−
| {{lc|erase}}
+
|{{lc|shrink_to_fit}}, {{lc|clear}}, {{lc|insert}}, {{lc|emplace}}, {{lc|push_front}},<br>{{lc|push_back}}, {{lc|emplace_front}}, {{lc|emplace_back}}
−
| If erasing at beginning or end - only erased elements.<br>
+
|Always.
−
Otherwise - all iterators are invalidated.
+
 
|-
 
|-
−
| {{lc|resize}}
+
|{{lc|erase}}
−
| Only if the new size is bigger than the old one.
+
|If erasing at begin - only erased elements.<br>
 +
If erasing at end - only erased elements and the past-the-end iterator.<br>
 +
Otherwise - all iterators are invalidated.<br><br>
 +
{{rev inl|until=c++11|It is unspecified when the past-the-end iterator is invalidated.}}<br><br>
 +
{{rev inl|since=c++11|The past-the-end iterator is also invalidated unless the erased<br>
 +
elements are at the beginning of the container and the last element is not erased.}}
 
|-
 
|-
−
| {{lc|pop_back}}, {{lc|pop_front}}
+
|{{lc|resize}}
−
| Only to the element erased
+
|If the new size is smaller than the old one - only erased elements and the<br> past-the-end iterator.<br>
 +
If the new size is bigger than the old one - all iterators are invalidated.<br>
 +
Otherwise - none iterators are invalidated.
 +
|-
 +
|{{lc|pop_front}}, {{lc|pop_back}}
 +
|To the element erased.<br>
 +
The past-the-end iterator<br>
 +
{{rev inl|until=c++11|may be invalidated (implementation defined)}}<br>
 +
{{rev inl|since=c++11|is also invalidated.}}
 
|}
 
|}
  
−
====Notes====
+
====Invalidation notes====
−
* Under some circumstances, references are not invalidated by {{lc|insert}} and {{lc|emplace}}.
+
* When inserting at either end of the deque, references are not invalidated by {{lc|insert}} and {{lc|emplace}}.
−
* {{lc|push_back}} and {{lc|emplace_back}} do not invalidate any references.
+
* {{lc|push_front}}, {{lc|push_back}}, {{lc|emplace_front}} and {{lc|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 {{lc|erase}}, {{lc|pop_front}} and {{lc|pop_back}}.
 +
* A call to {{lc|resize}} with a smaller size does not invalidate any references to non-erased elements.
 +
* A call to {{lc|resize}} with a bigger size does not invalidate any references to elements of the deque.
  
 
===Member types===
 
===Member types===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc hitem | Member type | Definition}}
+
{{dsc hitem|Member type|Definition}}
−
{{dsc inc | cpp/container/dsc value_type | deque}}
+
{{dsc inc|cpp/container/dsc value_type|deque}}
−
{{dsc inc | cpp/container/dsc allocator_type | deque}}
+
{{dsc inc|cpp/container/dsc allocator_type|deque}}
−
{{dsc inc | cpp/container/dsc size_type | deque}}
+
{{dsc inc|cpp/container/dsc size_type|deque}}
−
{{dsc inc | cpp/container/dsc difference_type | deque}}
+
{{dsc inc|cpp/container/dsc difference_type|deque}}
−
{{dsc inc | cpp/container/dsc reference | deque}}
+
{{dsc inc|cpp/container/dsc reference|deque}}
−
{{dsc inc | cpp/container/dsc const_reference | deque}}
+
{{dsc inc|cpp/container/dsc const_reference|deque}}
−
{{dsc inc | cpp/container/dsc pointer | deque}}
+
{{dsc inc|cpp/container/dsc pointer|deque}}
−
{{dsc inc | cpp/container/dsc const_pointer | deque}}
+
{{dsc inc|cpp/container/dsc const_pointer|deque}}
−
{{dsc inc | cpp/container/dsc iterator | deque}}
+
{{dsc inc|cpp/container/dsc iterator|deque}}
−
{{dsc inc | cpp/container/dsc const_iterator | deque}}
+
{{dsc inc|cpp/container/dsc const_iterator|deque}}
−
{{dsc inc | cpp/container/dsc reverse_iterator | deque}}
+
{{dsc inc|cpp/container/dsc reverse_iterator|deque}}
−
{{dsc inc | cpp/container/dsc const_reverse_iterator | deque}}
+
{{dsc inc|cpp/container/dsc const_reverse_iterator|deque}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Member functions===
 
===Member functions===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/container/dsc constructor | deque}}
+
{{dsc inc|cpp/container/dsc constructor|deque}}
−
{{dsc inc | cpp/container/dsc destructor | deque}}
+
{{dsc inc|cpp/container/dsc destructor|deque}}
−
{{dsc inc | cpp/container/dsc operator{{=}} | deque}}
+
{{dsc inc|cpp/container/dsc operator{{=}}|deque}}
−
{{dsc inc | cpp/container/dsc assign | deque}}
+
{{dsc inc|cpp/container/dsc assign|deque}}
−
{{dsc inc | cpp/container/dsc get_allocator | deque}}
+
{{dsc inc|cpp/container/dsc assign_range|deque}}
 +
{{dsc inc|cpp/container/dsc get_allocator|deque}}
  
−
{{dsc h2 | Element access}}
+
{{dsc h2|Element access}}
−
{{dsc inc | cpp/container/dsc at | deque}}
+
{{dsc inc|cpp/container/dsc at|deque}}
−
{{dsc inc | cpp/container/dsc operator_at | deque}}
+
{{dsc inc|cpp/container/dsc operator_at|deque}}
−
{{dsc inc | cpp/container/dsc front | deque}}
+
{{dsc inc|cpp/container/dsc front|deque}}
−
{{dsc inc | cpp/container/dsc back | deque}}
+
{{dsc inc|cpp/container/dsc back|deque}}
  
−
{{dsc h2 | Iterators}}
+
{{dsc h2|Iterators}}
−
{{dsc inc | cpp/container/dsc begin | deque}}
+
{{dsc inc|cpp/container/dsc begin|deque}}
−
{{dsc inc | cpp/container/dsc end | deque}}
+
{{dsc inc|cpp/container/dsc end|deque}}
−
{{dsc inc | cpp/container/dsc rbegin | deque}}
+
{{dsc inc|cpp/container/dsc rbegin|deque}}
−
{{dsc inc | cpp/container/dsc rend | deque}}
+
{{dsc inc|cpp/container/dsc rend|deque}}
  
−
{{dsc h2 | Capacity}}
+
{{dsc h2|Capacity}}
−
{{dsc inc | cpp/container/dsc empty | deque}}
+
{{dsc inc|cpp/container/dsc empty|deque}}
−
{{dsc inc | cpp/container/dsc size | deque}}
+
{{dsc inc|cpp/container/dsc size|deque}}
−
{{dsc inc | cpp/container/dsc max_size | deque}}
+
{{dsc inc|cpp/container/dsc max_size|deque}}
−
{{dsc inc | cpp/container/dsc shrink_to_fit | deque}}
+
{{dsc inc|cpp/container/dsc shrink_to_fit|deque}}
  
−
{{dsc h2 | Modifiers}}
+
{{dsc h2|Modifiers}}
−
{{dsc inc | cpp/container/dsc clear | deque}}
+
{{dsc inc|cpp/container/dsc clear|deque}}
−
{{dsc inc | cpp/container/dsc insert | deque}}
+
{{dsc inc|cpp/container/dsc insert|deque}}
−
{{dsc inc | cpp/container/dsc emplace | deque}}
+
{{dsc inc|cpp/container/dsc insert_range|deque}}
−
{{dsc inc | cpp/container/dsc erase | deque}}
+
{{dsc inc|cpp/container/dsc emplace|deque}}
−
{{dsc inc | cpp/container/dsc push_back | deque}}
+
{{dsc inc|cpp/container/dsc erase|deque}}
−
{{dsc inc | cpp/container/dsc emplace_back | deque}}
+
{{dsc inc|cpp/container/dsc push_back|deque}}
−
{{dsc inc | cpp/container/dsc pop_back | deque}}
+
{{dsc inc|cpp/container/dsc emplace_back|deque}}
−
{{dsc inc | cpp/container/dsc push_front | deque}}
+
{{dsc inc|cpp/container/dsc append_range|deque}}
−
{{dsc inc | cpp/container/dsc emplace_front | deque}}
+
{{dsc inc|cpp/container/dsc pop_back|deque}}
−
{{dsc inc | cpp/container/dsc pop_front | deque}}
+
{{dsc inc|cpp/container/dsc push_front|deque}}
−
{{dsc inc | cpp/container/dsc resize | deque}}
+
{{dsc inc|cpp/container/dsc emplace_front|deque}}
−
{{dsc inc | cpp/container/dsc swap | deque}}
+
{{dsc inc|cpp/container/dsc prepend_range|deque}}
 +
{{dsc inc|cpp/container/dsc pop_front|deque}}
 +
{{dsc inc|cpp/container/dsc resize|deque}}
 +
{{dsc inc|cpp/container/dsc swap|deque}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Non-member functions===
 
===Non-member functions===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/container/dsc operator_cmp | deque}}
+
{{dsc inc|cpp/container/dsc operator_cmp|deque}}
−
{{dsc inc | cpp/container/dsc swap2 | deque}}
+
{{dsc inc|cpp/container/dsc swap2|deque}}
 +
{{dsc inc|cpp/container/dsc erase seq|deque}}
 +
{{dsc end}}
 +
 
 +
{{rrev|since=c++17|
 +
==={{rl|deduction guides|Deduction guides}}===
 +
}}
 +
 
 +
===Notes===
 +
{{ftm begin|std=1|comment=1}}
 +
{{ftm|__cpp_lib_containers_ranges|value=202202L|std=C++23|Ranges construction and insertion for containers}}
 +
{{ftm end}}
 +
 
 +
===Example===
 +
{{example
 +
|code=
 +
#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
 +
}}
 +
 
 +
===Defect reports===
 +
{{dr list begin}}
 +
{{dr list item|wg=lwg|dr=230|std=C++98|before={{tt|T}} was not required to be {{named req|CopyConstructible}}<br>(an element of type {{tt|T}} might not be able to be constructed)|after={{tt|T}} is also required to<br>be {{named req|CopyConstructible}}}}
 +
{{dr list end}}
 +
 
 +
===See also===
 +
{{dsc begin}}
 +
{{dsc inc|cpp/container/dsc queue}}
 
{{dsc end}}
 
{{dsc end}}
  
−
[[de:cpp/container/deque]]
+
{{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}}
−
[[es:cpp/container/deque]]
+
−
[[fr:cpp/container/deque]]
+
−
[[it:cpp/container/deque]]
+
−
[[ja:cpp/container/deque]]
+
−
[[pt:cpp/container/deque]]
+
−
[[ru:cpp/container/deque]]
+
−
[[zh:cpp/container/deque]]
+

Latest revision as of 22:51, 13 November 2023

 
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;
 (1)
namespace pmr {

    template< class T >
    using deque = std::deque<T, std::pmr::polymorphic_allocator<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 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.

Contents

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

[edit] Iterator invalidation

This section is incomplete
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.
Otherwise - all iterators are invalidated.

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
elements are at the beginning of the container and the last element is not erased.(since C++11)

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.
Otherwise - none iterators are invalidated.

pop_front, pop_back To the element erased.

The past-the-end iterator
may be invalidated (implementation defined)(until C++11)
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

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]

[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]
(C++23)
 assigns a range of 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++23)
 inserts a range of 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]
(C++23)
 adds a range of elements to 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]
(C++23)
 adds a range of elements to 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]

[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]
(C++20)
 erases all elements satisfying specific criteria
(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

[edit] Example

Run this code
#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 to
be CopyConstructible

[edit] See also

 adapts a container to provide queue (FIFO data structure)
(class template) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/deque&oldid=162739"