A deque[1] is very much like a vector: like vector, it is a
sequence that supports random access to elements, constant time
insertion and removal of elements at the end of the sequence, and
linear time insertion and removal of elements in the middle.
The main way in which deque differs from vector is
that deque also supports constant time insertion and removal
of elements at the beginning of the sequence [2].
Additionally, deque does not have any member functions
analogous to vector's capacity() and
reserve(), and does not provide any of the guarantees on
iterator validity that are associated with those member functions.
[3]
Example
deque<int> Q;
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0
Definition
Defined in the standard header deque, and in the nonstandard
backward-compatibility header deque.h.
Template parameters
Parameter
Description
Default
T
The deque's value type: the type of object that is stored
in the deque.
Alloc
The deque's allocator, used for all internal memory management.
[1]
The name deque is pronounced "deck", and stands for
"double-ended queue." Knuth (section 2.6) reports that the name was
coined by E. J. Schweppe. See section 2.2.1 of Knuth for more
information about deques. (D. E. Knuth, The Art of Computer
Programming. Volume 1: Fundamental Algorithms, second edition.
Addison-Wesley, 1973.)
[2]
Inserting an element at the beginning or end of a deque takes
amortized constant time. Inserting an element in the middle is linear
in n, where n is the smaller of the number of
elements from the insertion point to the beginning, and the number of
elements from the insertion point to the end.
[3]
The semantics of iterator invalidation for deque is as
follows. Insert (including push_front and
push_back) invalidates all iterators that refer to a
deque. Erase in the middle of a deque
invalidates all iterators that refer to the deque.
Erase at the beginning or end of a deque (including
pop_front and pop_back) invalidates an iterator only
if it points to the erased element.
[4]
This member function relies on member template functions, which
at present (early 1998) are not supported by all compilers. If your
compiler supports member templates, you can call this function with
any type of input iterator. If your
compiler does not yet support member templates, though, then the
arguments must either be of type const value_type* or of type
deque::const_iterator.