Class deque provides many of the benefits of a vector
and a list
in one container. The term deque
is short for “double-ended queue.” Class deque
is implemented to provide efficient indexed access (using subscripting) for reading and modifying its elements, much like a vector
. Class deque
is also implemented for efficient insertion and deletion operations at its front and back, much like a list
(although a list
is also capable of efficient insertions and deletions in the middle of the list
). Class deque
provides support for random-access iterators, so deque
s can be used with all Standard Library algorithms. One of the most common uses of a deque
is to maintain a first-in, first-out queue of elements. In fact, a deque
is the default underlying implementation for the queue
adaptor (Section 15.7.2).
Additional storage for a deque
can be allocated at either end of the deque
in blocks of memory that are typically maintained as a built-in array of pointers to those blocks.2 Due to the noncontiguous memory layout of a deque
, a deque
iterator must be more “intelligent” than the pointers that are used to iterate through vector
s, array
s or built-in arrays.
2. This is an implementation-specific detail, not a requirement of the C++ standard.
Performance Tip 15.8
In general, deque has higher overhead than vector.
Performance Tip 15.9
Insertions and deletions in the middle of a deque are optimized to minimize the number of elements copied, so it’s more efficient than a vector but less efficient than a list for this kind of modification.
Class deque
provides the same basic operations as class vector
, but like list
adds member functions push_front and pop_front to allow insertion and deletion at the beginning of the deque
, respectively.
Figure 15.14 demonstrates features of class deque
. Remember that many of the functions presented in Fig. 15.10, Fig. 15.11 and Fig. 15.13 also can be used with class deque
. Header <deque> must be included to use class deque
.
1 // Fig. 15.14: fig15_14.cpp
2 // Standard Library deque class template.
3 #include <iostream>
4 #include <deque> // deque class-template definition
5 #include <algorithm> // copy algorithm
6 #include <iterator> // ostream_iterator
7 using namespace std;
8
9 int main()
10 {
11 deque< double > values; // create deque of doubles
12 ostream_iterator< double > output( cout, " " );
13
14 // insert elements in values
15 values.push_front( 2.2 );
16 values.push_front( 3.5 );
17 values.push_back( 1.1 );
18
19 cout << "values contains: ";
20
21 // use subscript operator to obtain elements of values
22 for ( size_t i = 0; i < values.size(); ++i )
23 cout << values[ i ] << ' ';
24
25 values.pop_front(); // remove first element
26 cout << "
After pop_front, values contains: ";
27 copy( values.cbegin(), values.cend(), output );
28
29 // use subscript operator to modify element at location 1
30 values[ 1 ] = 5.4;
31 cout << "
After values[ 1 ] = 5.4, values contains: ";
32 copy( values.cbegin(), values.cend(), output );
33 cout << endl;
34 } // end main
values contains: 3.5 2.2 1.1
After pop_front, values contains: 2.2 1.1
After values[ 1 ] = 5.4, values contains: 2.2 5.4
Line 11 instantiates a deque
that can store double
values. Lines 15–17 use functions push_front
and push_back
to insert elements at the beginning and end of the deque
.
The for
statement in lines 22–23 uses the subscript operator to retrieve the value in each element of the deque
for output. The condition uses function size
to ensure that we do not attempt to access an element outside the bounds of the deque
.
Line 25 uses function pop_front
to demonstrate removing the first element of the deque
. Line 30 uses the subscript operator to obtain an lvalue. This enables values to be assigned directly to any element of the deque
.