15.5.3. deque Sequence Container

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 deques 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 vectors, arrays or built-in arrays.

2. This is an implementation-specific detail, not a requirement of the C++ standard.

Image Performance Tip 15.8

In general, deque has higher overhead than vector.

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

Click here to view code image

 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

Fig. 15.14. Standard Library deque class template.

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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.144.12.14