Przejdź do głównej zawartości
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class T, /* ... */ >
class deque;

Deque (double-ended queue) is a container that allows fast insertion and deletion from both the beggining and the end.

Unlike std::queue or std::priority_queue it's not a container adapter.

Technical definition of a 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, 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.

std::deque

Defined inqueue

Template parameters

pubT

The type of the elements.

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.

pubAllocator

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 if Allocator::value_type is not the same as T.

Type names

pubvalue_typeT
puballocator_typeAllocator
pubsize_typeUnsigned integer type (usuallly std::size_t)
pubdifference_typeSigned integer type (usuallly std::ptrdiff_t)
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer (do C++11)
std::allocator_traits<Allocator>::pointer (od C++11)
pubconst_pointerAllocator::const_pointer (do C++11)
std::allocator_traits<Allocator>::const_pointer (od C++11)
pubiteratorLegacyRandomAccessIterator
pubconst_iteratorLegacyRandomAccessIterator
pubreverse_iteratorstd::reverse_iterator<iterator>
pubconst_reverse_iteratorstd::reverse_iterator<const_iterator>

Member functions

pub(constructors)

Constructs a deque.

pub(destructor)

Destroys the deque, deallocating internal storage if used.

puboperator=

Assigns values to the container.

pubassign

Assigns values to the container.

pubget_allocatorReturns the associated allocator.

Element access

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses a specified element.

pubfront

Returns the first element.

pubback

Returns the last element.

Iterators

pubbegin
cbegin (od C++11)

Returns an iterator/const_iterator to the beginning.

pubend
cend (od C++11)

Returns an iterator/const_iterator to the end.

pubrbegin
crbegin (od C++11)

Returns a reverse iterator/const_iterator to the beginning.

pubrend
crend (od C++11)

Returns a reverse iterator/const_iterator to the end.

Capacity

pubempty

Returns true if the deque is empty, otherwise false.

pubsize

Returns the number of elements.

pubmax_size

Returns the maximum possible number of elements.

pubshrink_to_fit (od C++11)

Reduces memory usage by freeing unused memory.

Modifiers

pubclear

Clears the contents of a deque.

pubinsert

Inserts elements.

pubemplace (od C++11)

Constructs a new element in place.

puberase

Erases elements.

pubpush_back

Appends an element to the end.

pubemplace_back (od C++11)

Constructs new element in-place at the end.

pubpop_back

Removes the last element.

pubpush_front

Adds a new element to the beggining.

pubemplace_front (od C++11)

Constructs new element in-place at the beginning.

pubpop_front

Removes the first element.

pubresize

Changes the number of elements stored.

pubswap

Swaps two deques.

Non-member functions

puboperator==
operator!= (removed in C++20)
operator< (removed in C++20)
operator> (removed in C++20)
operator<= (removed in C++20)
operator>= (removed in C++20)
operator<=> (od C++20)

Lexicographically compares the values in the deque.

pubstd::swap (std::deque)

An overload for a std::swap algorithm.

puberase (std::deque)
erase_if (std::deque)

Overloads for std::erase/std::erase_if algorithms.

Helper classes

pubstd::uses_allocator (std::deque)

Specializes the std::uses_allocator type trait.

Deduction guides (since C++17)

Click to expand
// (1) (since C++17)
template< class InputIt,
class Alloc = std::allocator<
typename std::iterator_traits<InputIt>::value_type
>
>
deque( InputIt, InputIt, Alloc = Alloc() )
-> deque<typename std::iterator_traits<InputIt>::value_type, Alloc>;

(1) allows deduction from an iterator range.

Overload resolution

In order for (1) to participate in overload resolution, the folllowing requirements must be met:

zanotuj

The extent to which the library determines that a type does not satisfy LegacyInputIterator is unspecified, except that as a minimum:

  • Integral types do not qualify as input iterators.

Likewise, the extent to which it determines that a type does not satisfy Allocator is unspecified, except that as a minimum:

Examples

Basic manipulation

Initialize the queue, add values and print the contents
#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 << ' ';
}
}
Result
13 7 5 16 8 25
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class T, /* ... */ >
class deque;

Deque (double-ended queue) is a container that allows fast insertion and deletion from both the beggining and the end.

Unlike std::queue or std::priority_queue it's not a container adapter.

Technical definition of a 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, 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.

std::deque

Defined inqueue

Template parameters

pubT

The type of the elements.

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.

pubAllocator

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 if Allocator::value_type is not the same as T.

Type names

pubvalue_typeT
puballocator_typeAllocator
pubsize_typeUnsigned integer type (usuallly std::size_t)
pubdifference_typeSigned integer type (usuallly std::ptrdiff_t)
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer (do C++11)
std::allocator_traits<Allocator>::pointer (od C++11)
pubconst_pointerAllocator::const_pointer (do C++11)
std::allocator_traits<Allocator>::const_pointer (od C++11)
pubiteratorLegacyRandomAccessIterator
pubconst_iteratorLegacyRandomAccessIterator
pubreverse_iteratorstd::reverse_iterator<iterator>
pubconst_reverse_iteratorstd::reverse_iterator<const_iterator>

Member functions

pub(constructors)

Constructs a deque.

pub(destructor)

Destroys the deque, deallocating internal storage if used.

puboperator=

Assigns values to the container.

pubassign

Assigns values to the container.

pubget_allocatorReturns the associated allocator.

Element access

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses a specified element.

pubfront

Returns the first element.

pubback

Returns the last element.

Iterators

pubbegin
cbegin (od C++11)

Returns an iterator/const_iterator to the beginning.

pubend
cend (od C++11)

Returns an iterator/const_iterator to the end.

pubrbegin
crbegin (od C++11)

Returns a reverse iterator/const_iterator to the beginning.

pubrend
crend (od C++11)

Returns a reverse iterator/const_iterator to the end.

Capacity

pubempty

Returns true if the deque is empty, otherwise false.

pubsize

Returns the number of elements.

pubmax_size

Returns the maximum possible number of elements.

pubshrink_to_fit (od C++11)

Reduces memory usage by freeing unused memory.

Modifiers

pubclear

Clears the contents of a deque.

pubinsert

Inserts elements.

pubemplace (od C++11)

Constructs a new element in place.

puberase

Erases elements.

pubpush_back

Appends an element to the end.

pubemplace_back (od C++11)

Constructs new element in-place at the end.

pubpop_back

Removes the last element.

pubpush_front

Adds a new element to the beggining.

pubemplace_front (od C++11)

Constructs new element in-place at the beginning.

pubpop_front

Removes the first element.

pubresize

Changes the number of elements stored.

pubswap

Swaps two deques.

Non-member functions

puboperator==
operator!= (removed in C++20)
operator< (removed in C++20)
operator> (removed in C++20)
operator<= (removed in C++20)
operator>= (removed in C++20)
operator<=> (od C++20)

Lexicographically compares the values in the deque.

pubstd::swap (std::deque)

An overload for a std::swap algorithm.

puberase (std::deque)
erase_if (std::deque)

Overloads for std::erase/std::erase_if algorithms.

Helper classes

pubstd::uses_allocator (std::deque)

Specializes the std::uses_allocator type trait.

Deduction guides (since C++17)

Click to expand
// (1) (since C++17)
template< class InputIt,
class Alloc = std::allocator<
typename std::iterator_traits<InputIt>::value_type
>
>
deque( InputIt, InputIt, Alloc = Alloc() )
-> deque<typename std::iterator_traits<InputIt>::value_type, Alloc>;

(1) allows deduction from an iterator range.

Overload resolution

In order for (1) to participate in overload resolution, the folllowing requirements must be met:

zanotuj

The extent to which the library determines that a type does not satisfy LegacyInputIterator is unspecified, except that as a minimum:

  • Integral types do not qualify as input iterators.

Likewise, the extent to which it determines that a type does not satisfy Allocator is unspecified, except that as a minimum:

Examples

Basic manipulation

Initialize the queue, add values and print the contents
#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 << ' ';
}
}
Result
13 7 5 16 8 25
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.