C++ Reference Material
The STL deque Container

The deque class implements a double-ended queue and, in its STL incarnation, has an interface which is very similar to that of the vector class. The major conceptual difference is that a deque provides fast insertion and deletion at both ends.

Constructors and destructor

Default Constructor

deque<T> d;
Construct an empty deque d which can hold values of type T.

Copy Constructor

There is, of course, only one copy constructor, but there are two syntactic forms that invoke it, and both are shown.

deque<T> d(otherDeque);
Construct d as a copy of otherDeque, whose component type must be T. The copy has the same size as the original.
deque<T> d = otherDeque;
Copy constructor (alternate usage syntax).

Other Constructors

deque<T> d(num);
Construct a deque d of size num containing num values, each equal to the default value of type T.
deque<T> d(num, val);
Construct a deque d of size num containing num values, each equal to val, which must be of type T, and which may be supplied by a variable, a literal or named constant, or a function call.
deque<T> d(inIterBegin, inIterEnd);
Construct d containing values from the range [inIterBegin,inIterEnd) in another (not necessarily deque) container, but whose component type is the same as the component type of d.

Destructor

d.~deque<T>()
Destroy all components of d and free the associated memory.

Overloaded operators

Assignment operator

d1 = d2
Assign d2 to d1, and return the common value. The deque on the left of an assignment receives the values and size of the one on the right.

Relational operators

Deques are compared in the "lexicographic ordering" sense. This essentially means that the two deques are compared by comparing their values pairwise, starting at the beginning, with each comparison looking at two values in corresponding positions, until a determination of the relationship between the two deques can be made. Only deques of the same component type can be compared of course, and the == and < operators must be defined for the component type.

d1 == d2
Return true if d1 and d2 have the same component type and the same size, and the components in each pair of corresponding locations have the same value; otherwise return false.
d1 != d2
Return true if d1==d2 returns false; otherwise return false.
d1 < d2
Return true if, in the pairwise comparison of values from d1 and d2, in the first pair in which the two values differ, the one from d1 is less than the one from d2; otherwise return false.
d1 <= d2
Return true if either d1<d2 or d1==d2 is true; otherwise return false.
d1 > d2
Return true if d2<d1 is true; otherwise return false.
d1 >= d2
Return true if either d1>d2 or d1==d2 is true, otherwise return false.

operator[ ]

d[i]
Return a reference (or const_reference) to the component of d with index i. (Index values start at 0, and there is no checking for an index out of bounds.)

Member functions for accessing values

Each of the member functions in this section has both a const and a non-const version.

d.at(i)
Return a reference (or const_reference) to the component of d with index i. (Throws an out_of_range exception if i is not a valid index for d.)
d.front()
Return a reference (or const_reference) to the first component of d.
d.back()
Return a reference (or const_reference) to the last component of d.
d.begin()
Return an iterator (or const_iterator) pointing to the first component of d.
d.end()
Return an iterator (or const_iterator) pointing to one-past-the-last component of d.
d.rbegin()
Return a reverse_iterator (or const_reverse_iterator) pointing to the last component of d.
d.rend()
Return a reverse_iterator (or const_reverse_iterator) pointing to one-before-the-first component of d.

Member functions for reporting status

d.max_size()
Return a value of type size_type giving the maximum possible size of d, which will depend on the size of the component type T of the deque object, and the amount of available memory.
d.size()
Return a value of type size_type giving the number of values currently in d.
d.empty()
Return true if d is empty (contains zero values); otherwise return false.

Member functions for inserting one or more values

d.assign(num, val)
Assign num copies of val to d, overwriting the entire previous contents of d.
d.assign(inIterBegin, inIterEnd)
Assign to d the values from the range [inIterBegin,inIterEnd) in another (not necessarily deque) container, but whose values are also of type T, overwriting the entire previous contents of d.
d.insert(iter, val)
Insert val into d immediately before the value pointed to by iter, and return an iterator pointing at the new component with value val.
d.insert(iter, num, val)
Insert num copies of val into d, immediately before the value pointed to by iter.
d.insert(iter, inIterBegin, inIterEnd)
Insert into d, immediately before the value pointed to by iter, values from the range [inIterBegin,inIterEnd) in another (not necessarily deque) container, but whose values must be of the same type as the values of d.
d.push_back(val)
Add val to the end of d, increasing the size of d by one.
d.push_front(val)
Add val to the front of d, increasing the size of d by one.

Member functions for deleting one or more values

d.clear()
Delete all values of d. The size of d is reduced to zero.
d.erase(iter)
Delete the value of d pointed to by iter and return an iterator pointing at the following value, or to one-past-the-last if the value deleted was the last one. The size of d is reduced by one.
d.erase(iterBegin, iterEnd)
Delete all values of d from the range [iterBegin,iterEnd) and return iterEnd. The size of d is reduced by iterEnd-iterBegin (a value of type difference_type).
d.pop_back()
Delete the last value of d. The size of d is reduced by one.
d.pop_front()
Delete the first value of d. The size of d is reduced by one.

Miscellaneous member functions

d.resize(num)
Change size of d to num. (If d must be lengthened, default values of its component type are added to the end of d. If d is shortened, values at the end are lost.)
d.resize(num, val)
Change size of d to num. (If d must be lengthened, copies of val are added to the end of d. If d is shortened, values at the end are lost, and the value of val is not used.)
d.swap(otherDeque)
Exchange values in d with those in otherDeque. The sizes are swapped as well.
d.getallocator()
Return the allocator of d. (This is possibly the most infrequently used of all member functions of the deque class.)

Miscellaneous notes

Differences in the use of d[i] and d.at(i)
The "safer" choice to access an element of d via an index i is d.at(i) rather than d[i]. This is because d.at(i) throws an out_of_range exception if i is not a valid index value for d, unlike d[i], which behaves just as if d were an ordinary array, and thus does not give you any warning if your index goes out of bounds. If it does go out of bounds, you may get a run-time error, or your program may simply use whatever is stored at the invalid location as though it were a piece of valid data.
Danger of invalidation of iterators, references and pointers
Although it may not be strictly true in all situations, it is probably safest to assume that any member function that inserts or removes values or changes the size of a deque will invalidate any iterators, references or pointers already associated with values of that deque.
Implementation
Standard C++ does not say how the STL containers and algorithms must be implemented. It does, however, state certain constraints, such as complexity constraints, to which each implementation must adhere. Thus it is much better to base your programs on the STL's performance guarantees, rather than upon any assumption about how a particular feature, like the deque class, may be implemented.
Some performance and usage issues
Deques tend to be useful in situations where order of components, compact storage, and fast insertions and deletions at the ends are important. They can be used to implement any FIFO (First In First Out) structure, though a queue should be used if there must be strict FIFO behavior with no direct access by numeric index permitted. If fast insertions near the middle need to be made, a list is the better choice.

The deque is one of the three "sequential" container classes in the STL (the vector and the list are the other two). Usually, if you're wondering about using a deque, the choice will be between using a deque or using a vector, since they have so much in common. Element access tends to be a bit faster in vectors, though both vectors and deques offer constant-time access to elements (from a big-Oh perspective). If there are to be many insertions and deletions at the ends, and particularly at the front, the deque would be a better choice. In general, though, when an array-like object which can grow and shrink dynamically is needed, the vector tends to be the container of choice.

Sample programs

There are two groups of sample programs. The first group involves only STL deques and generic C++, while the second group involves other STL features in addition to deques. The programs should be studied in the sequence given, since the description of each new sample program in the sequence mentions only the new features illustrated for the first time in that particular program, and features seen in earlier sample programs will continue to reappear in later programs.

All of the programs have been compiled and run successfully under Microsoft Visual Studio .NET 2005, unless otherwise noted.

Programs involving only deques (and generic C++)

deque01.cpp | Windows_executable | program_output (text)
Illustrates deque constructors, accessing deque values with d[i], the typedef deque<T>::size_type, and the member functions size() and empty(). Also illustrates how ordinary array pointers can be used, in certain situations, in the same way that STL iterators are used.
deque02.cpp | Windows_executable | program_output (text)
Illustrates the similarities and differences between d[i] and d.at(i).
deque03.cpp | Windows_executable | program_output (text)
Illustrates member function max_size(), and how the maximum size for a deque object depends on the size of its component type.
deque04.cpp | Windows_executable | program_output (text)
Illustrates push_back() and push_front().
deque05.cpp | Windows_executable | program_output (text)
Illustrates typical uses of the default (random-access) iterator for the deque class, shows additional uses of member functions begin() and end(), and also shows the use of operators =, +, -, ++, --, != and * with deque class iterators.
deque06.cpp | Windows_executable | program_output (text)
Illustrates the default (random-access) deque class iterator in additional situations, and shows the use of operators ->, [ ], <, >, <=, >=, +=, -= and == with deque class iterators.
deque07.cpp | Windows_executable | program_output (text)
Illustrates reverse iterators for the deque class, as well as member functions rbegin() and rend().
deque08.cpp | Windows_executable | program_output (text)
Illustrates a typical use of a const iterator.
deque09.cpp | Windows_executable | program_output (text)
Illustrates member functions front() and back().
deque10.cpp | Windows_executable | program_output (text)
Illustrates the overloaded assignment operator = and the assign() member function.
deque11.cpp | Windows_executable | program_output (text)
Illustrates the insert() member function.
deque12.cpp | Windows_executable | program_output (text)
Illustrates clear(), erase(), pop_back() and pop_front() member functions.
deque13.cpp | Windows_executable | program_output (text)
Illustrates the resize() member function.
deque14.cpp | Windows_executable | program_output (text)
Illustrates the swap() member function.

Programs involving additional deque features and deques in combination with other STL features

deque_a.cpp | Windows_executable | program_output (text)
Illustrates the use of stream iterators and the copy algorithm for I/O of deque values.
deque_b.cpp | Windows_executable | program_output (text)
Illustrates how to display the name of the underlying type represented by each typedef defined by a deque class.
deque_c.cpp | Windows_executable | program_output (text)
Illustrates initialization of a deque with values from non-deque containers (in this case, a vector and a list).

Member function prototypes

For enhanced readability in each of the prototypes given below, each parameter in each parameter list appears on a separate line. Also, some formatting liberties are taken, in the interest of greater readability. For example, rather than aligning all prototypes at the left margin, const and non-const versions of a member function are aligned in such a way as to allow the reader to more easily compare the two visually.

Template specification for the deque class

template<class T,
         class Allocator = allocator<T> >
class deque { ... }

Constructors

explicit deque(const Allocator& a = Allocator());

explicit deque(size_type num,
               const T& val = T(),
               const Allocator& a = Allocator());
                

template<class InIterator>
deque(InIterator inIterBegin,
      InIterator inIterEnd,
      const Allocator& a = Allocator());

Copy Constructor

deque(const deque<T, Allocator>& otherDeque);

Destructor

~deque();

assign

void assign(size_type num,
            const T& val);

template<class InIterator>
void assign(InIterator inIterBegin,
            InIterator inIterEnd);

at

      reference at(size_type i);
const_reference at(size_type i) const;

back

      reference back();
const_reference back() const;

begin

      iterator begin();
const_iterator begin() const;

clear

void clear();

empty

bool empty() const;

end

      iterator end();
const_iterator end() const;

erase

iterator erase(iterator iter);
iterator erase(iterator iterBegin,
               iterator iterEnd);

front

      reference front();
const_reference front() const;

get_allocator

allocator_type get_allocator() const;

insert

iterator insert(iterator iter,
                const T& val);

void insert(iterator iter,
            size_type num,
            const T& val);

template<class InIterator>
void insert(iterator iter,
            InIterator inIterBegin,
            InIterator inIterEnd);

max_size

size_type max_size() const;

operator[ ]

      reference operator[](size_type i);
const_reference operator[](size_type i) const;

pop_back

void pop_back();

pop_front

void pop_front();

push_back

void push_back(const T& val);

push_front

void push_front(const T& val);

rbegin

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

rend

      reverse_iterator rend();
const_reverse_iterator rend() const;

resize

void resize(size_type num,
            T val = T());

size

size_type size() const;

swap

void swap(deque<T, Allocator>& otherDeque);