Reference
C Library
IOstream Library
Strings library
STL Containers
STL Algorithms
Miscellaneous

STL Containers
bitset
deque
list
map
multimap
multiset
priority_queue
queue
set
stack
vector

deque
comparison operators
deque::deque
deque::~deque
member functions:
deque::assign
deque::at
deque::back
deque::begin
deque::clear
deque::empty
deque::end
deque::erase
deque::front
deque::get_allocator
deque::insert
deque::max_size
deque::operator=
deque::operator[]
deque::pop_back
deque::pop_front
deque::push_back
deque::push_front
deque::rbegin
deque::rend
deque::resize
deque::size
deque::swap

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

(constructor)

Construct deque container (public member function)

(destructor)

Deque destructor (public member function)

operator=

Copy container content (public member function)

Iterators:

begin

Return iterator to beginning (public member function)

end

Return iterator to end (public member function)

rbegin

Return reverse iterator to reverse beginning (public member function)

rend

Return reverse iterator to reverse end (public member function)

Capacity:

size

Return size (public member function)

max_size

Return maximum size (public member function)

resize

Change size (public member functions)

empty

Test whether container is empty (public member function)

Element access:

operator[]

Access element (public member function)

at	Access element (public member function)

front

Access first element (public member function)

back

Access last element (public member function)

Modifiers:

assign

Assign container content (public member function)

push_back

Add element at the end (public member function)

push_front

Insert element at beginning (public member function)

pop_back

Delete last element (public member function)

pop_front

Delete first element (public member function)

insert

Insert elements (public member function)

erase

Erase elements (public member function)

swap

Swap content (public member function)

clear

Clear content (public member function)

Allocator:

get_allocator

Get allocator (public member function)

Member types

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

member type	definition
`reference`	`Allocator::reference`
`const_reference`	`Allocator::const_reference`
`iterator`	Random access iterator
`const_iterator`	Constant random access iterator
`size_type`	Unsigned integral type (usually same as size_t)
`difference_type`	Signed integral type (usually same as ptrdiff_t)
`value_type`	`T`
`allocator_type`	`Allocator`
`pointer`	`Allocator::pointer`
`const_pointer`	`Allocator::const_pointer`
`reverse_iterator`	`reverse_iterator<iterator>`
`const_reverse_iterator`	`reverse_iterator<const_iterator>`