deque


class template
<deque>

Double ended queue

deque (usually pronounced like "deck") is an irregular acronym of double-ended queue. Double-ended queues are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.

Deques may be implemented by specific libraries in different ways, but in all cases they allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).

Deque sequences have the following properties:
  • Individual elements can be accessed by their position index.
  • Iteration over the elements can be performed in any order.
  • Elements can be efficiently added and removed from any of its ends (either the beginning or the end of the sequence).


Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.

For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists.

In their implementation in the C++ Standard Template Library, deques take two template parameters:
 
template < class T, class Allocator = allocator<T> > class deque;

Where the template parameters have the following meanings:
  • T: Type of the elements.
  • Allocator: Type of the allocator object used to define the storage allocation model. By default, the allocator class template for type T is used, which defines the simplest memory allocation model and is value-independent.

In the reference for the deque member functions, these same names are assumed for the template parameters.

Member functions



Iterators:


Capacity:


Element access:


Modifiers:


Allocator:


Member types

of template <class T, class Allocator=allocator<T> > class deque;

member typedefinition
referenceAllocator::reference
const_referenceAllocator::const_reference
iteratorRandom access iterator
const_iteratorConstant random access iterator
size_typeUnsigned integral type (usually same as size_t)
difference_typeSigned integral type (usually same as ptrdiff_t)
value_typeT
allocator_typeAllocator
pointerAllocator::pointer
const_pointerAllocator::const_pointer
reverse_iteratorreverse_iterator<iterator>
const_reverse_iteratorreverse_iterator<const_iterator>