Difference between revisions of "cpp/container/deque"

Revision as of 04:55, 24 February 2017

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 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. 656 bytes on 64-bit libstdc++).

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.

`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

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 (including 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 Otherwise - none 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[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

(constructor)	constructs the `deque` (public member function) [edit]
(destructor)	destructs the `deque` (public member function) [edit]
operator=	assigns values to the container (public member function) [edit]
assign	assigns values to the container (public member function) [edit]
get_allocator	returns the associated allocator (public member function) [edit]
Element access
at	access specified element with bounds checking (public member function) [edit]
operator[]	access specified element (public member function) [edit]
front	access the first element (public member function) [edit]
back	access the last element (public member function) [edit]
Iterators
begincbegin (C++11)	returns an iterator to the beginning (public member function) [edit]
endcend (C++11)	returns an iterator to the end (public member function) [edit]
rbegincrbegin (C++11)	returns a reverse iterator to the beginning (public member function) [edit]
rendcrend (C++11)	returns a reverse iterator to the end (public member function) [edit]
Capacity
empty	checks whether the container is empty (public member function) [edit]
size	returns the number of elements (public member function) [edit]
max_size	returns the maximum possible number of elements (public member function) [edit]
shrink_to_fit (DR*)	reduces memory usage by freeing unused memory (public member function) [edit]
Modifiers
clear	clears the contents (public member function) [edit]
insert	inserts elements (public member function) [edit]
emplace (C++11)	constructs element in-place (public member function) [edit]
erase	erases elements (public member function) [edit]
push_back	adds an element to the end (public member function) [edit]
emplace_back (C++11)	constructs an element in-place at the end (public member function) [edit]
pop_back	removes the last element (public member function) [edit]
push_front	inserts an element to the beginning (public member function) [edit]
emplace_front (C++11)	constructs an element in-place at the beginning (public member function) [edit]
pop_front	removes the first element (public member function) [edit]
resize	changes the number of elements stored (public member function) [edit]
swap	swaps the contents (public member function) [edit]

Non-member functions

operator==operator!=operator<operator<=operator>operator>=operator<=> (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 `deque`s (function template) [edit]
std::swap(std::deque)	specializes the std::swap algorithm (function template) [edit]

Example

Run this code

#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:

@@ Line 19: / Line 19: @@
 {{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 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 {{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. 656 bytes on 64-bit libstdc++).
 The complexity (efficiency) of common operations on deques is as follows:
@@ Line 71: / Line 71: @@
 |}
-====Notes====
+====Invalidation notes====
 * When inserting at either end of the deque, references are not invalidated by {{lc|insert}} and {{lc|emplace}}.
 * {{lc|push_front}}, {{lc|push_back}}, {{lc|emplace_front}} and {{lc|emplace_back}} do not invalidate any references to elements of the deque.
@@ Line 77: / Line 77: @@
 * 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.
-* If a method is common to both deque and {{lc|std::vector}} then the run-time complexity of deque's method is no worse than the complexity of {{lc|std::vector}}'s method (and in the case of inserting to the front, deque's complexity is better).
-* Despite the run-time complexity advantage of deque over {{lc|std::vector}} described above, the {{lc|std::vector}} container does have some advantages over the deque container:
-** Implementations of deque typically have a large overhead memory cost. For instance, the 64-bit GNU (resp. Apache, Microsoft) standard library implementation of deque uses a minimum of 656 (resp. 832, 128) bytes to store 1 object in a deque. This variability may also negatively affect portability.
-** deque typically doesn't store its elements contiguously in memory, which may make interacting with older C or C++ code more difficult. This also means that {{lc|std::vector}}s typically have better locality in memory. This lack of locality in space, however, may give deque an advantage when dealing with a large collection of objects.
-** The better run-time complexity of some of deque's operations comes at the expense of additional book-keeping. In particular, many popular implementations of deque often store objects via an array of pointers-to-array so that accessing an element by passing an index to {{lc|operator[]}}, for instance, requires first finding the pointer that points to the array holding this element and then secondly finding the location of this element within this array.
 ===Member types===

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

Sequence
array (C++11)
vector
vector<bool>
inplace_vector (C++26)
deque
forward_list (C++11)
list
Associative
set
multiset
map
multimap
Unordered associative
unordered_set (C++11)
unordered_multiset (C++11)
unordered_map (C++11)
unordered_multimap (C++11)
Adaptors
stack
queue
priority_queue
flat_set (C++23)
flat_multiset (C++23)
flat_map (C++23)
flat_multimap (C++23)
Views
span (C++20)
mdspan (C++23)
Tables
Iterator invalidation
Member function table
Non-member function table

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/container/deque"

Revision as of 04:55, 24 February 2017

Contents

Template parameters

Iterator invalidation

Invalidation notes

Member types

Member functions

Element access

Iterators

Capacity

Modifiers

Non-member functions

Example

Navigation

Toolbox