Sequence Containers

The C++ Standard Template Library provides three sequence containersvector, list and deque. Class template vector and class template deque both are based on arrays. Class template list implements a linked-list data structure similar to our List class presented in Chapter 21, but more robust.

One of the most popular containers in the STL is vector. Recall that we introduced class template vector in Chapter 7 as a more robust type of array. A vector changes size dynamically. Unlike C and C++ "raw" arrays (see Chapter 7), vectors can be assigned to one another. This is not possible with pointer-based, C-like arrays, because those array names are constant pointers and cannot be the targets of assignments. Just as with C arrays, vector subscripting does not perform automatic range checking, but class template vector does provide this capability via member function at (also discussed in Chapter 7).

---

Performance Tip 23.4

Insertion at the back of a vector is efficient. The vector simply grows, if necessary, to accommodate the new item. It is expensive to insert (or delete) an element in the middle of a vector the entire portion of the vector after the insertion (or deletion) point must be moved, because vector elements occupy contiguous cells in memory just as C or C++ "raw" arrays do.

Figure 23.2 presented the operations common to all the STL containers. Beyond these operations, each container typically provides a variety of other capabilities. Many of these capabilities are common to several containers, but they are not always equally efficient for each container. The programmer must choose the container most appropriate for the application.

Performance Tip 23.5

Applications that require frequent insertions and deletions at both ends of a container normally use a deque rather than a vector. Although we can insert and delete elements at the front and back of both a vector and a deque, class deque is more efficient than vector for doing insertions and deletions at the front.

Performance Tip 23.6

Applications with frequent insertions and deletions in the middle and/or at the extremes of a container normally use a list, due to its efficient implementation of insertion and deletion anywhere in the data structure.

In addition to the common operations described in Fig. 23.2, the sequence containers have several other common operationsfront to return a reference to the first element in the container, back to return a reference to the last element in the container, push_back to insert a new element at the end of the container and pop_back to remove the last element of the container.

23.2.1. vector Sequence Container

Class template vector provides a data structure with contiguous memory locations. This enables efficient, direct access to any element of a vector via the subscript operator [], exactly as with a C or C++ "raw" array. Class template vector is most commonly used when the data in the container must be sorted and easily accessible via a subscript. When a vector's memory is exhausted, the vector allocates a larger contiguous area of memory, copies the original elements into the new memory and deallocates the old memory.

Performance Tip 23.7

Choose the vector container for the best random-access performance.

Performance Tip 23.8

Objects of class template vector provide rapid indexed access with the overloaded subscript operator [] because they are stored in contiguous memory like a C or C++ raw array.

Performance Tip 23.9

It is faster to insert many elements at once than one at a time.

---

An important part of every container is the type of iterator it supports. This determines which algorithms can be applied to the container. A vector supports random-access iteratorsi.e., all iterator operations shown in Fig. 23.10 can be applied to a vector iterator. All STL algorithms can operate on a vector. The iterators for a vector are normally implemented as pointers to elements of the vector. Each STL algorithm that takes iterator arguments requires those iterators to provide a minimum level of functionality. If an algorithm requires a forward iterator, for example, that algorithm can operate on any container that provides forward iterators, bidirectional iterators or random-access iterators. As long as the container supports the algorithm's minimum iterator functionality, the algorithm can operate on the container.

Using Vector and Iterators

Figure 23.14 illustrates several functions of the vector class template. Many of these functions are available in every first-class container. You must include header file to use class template vector.

Figure 23.14. Standard Library vector class template.

(This item is displayed on pages 1126 - 1127 in the print version)

 1 // Fig. 23.14: Fig23_14.cpp
 2 // Demonstrating Standard Library vector class template.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include  // vector class-template definition
 8 using std::vector; 
 9
10 // prototype for function template printVector
11 template < typename T > void printVector( const vector< T > &integers2 );
12
13 int main()
14 {
15 const int SIZE = 6; // define array size
16 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 }; // initialize array
17 vector< int > integers; // create vector of ints
18
19 cout << "The initial size of integers is: " << integers.size()
20 << "
The initial capacity of integers is: " << integers.capacity();
21
22 // function push_back is in every sequence collection
23 integers.push_back( 2 ); 
24 integers.push_back( 3 ); 
25 integers.push_back( 4 ); 
26
27 cout << "
The size of integers is: " << integers.size()
28 << "
The capacity of integers is: " << integers.capacity();
29 cout << "

Output array using pointer notation: ";
30
31 // display array using pointer notation
32 for ( int *ptr = array; ptr != array + SIZE; ptr++ )
33 cout << *ptr << ' ';
34
35 cout << "
Output vector using iterator notation: ";
36 printVector( integers );
37 cout << "
Reversed contents of vector integers: ";
38
39 // two const reverse iterators
40 vector< int >::const_reverse_iterator reverseIterator;
41 vector< int >::const_reverse_iterator tempIterator = integers.rend();
42
43 // display vector in reverse order using reverse_iterator
44 for ( reverseIterator = integers.rbegin(); 
45  reverseIterator!= tempIterator; ++reverseIterator ) 
46  cout << *reverseIterator << ' '; 
47
48 cout << endl;
49 return 0;
50 } // end main
51
52 // function template for outputting vector elements
53 template < typename T > void printVector( const vector< T > &integers2 )
54 {
55 typename vector< T >::const_iterator constIterator; // const_iterator
56
57 // display vector elements using const_iterator 
58 for ( constIterator = integers2.begin(); 
59  constIterator != integers2.end(); ++constIterator )
60  cout << *constIterator << ' '; 
61 } // end function printVector

 

 The initial size of integers is: 0
 The initial capacity of integers is: 0
 The size of integers is: 3
 The capacity of integers is: 4

 Output array using pointer notation: 1 2 3 4 5 6
 Output vector using iterator notation: 2 3 4
 Reversed contents of vector integers: 4 3 2

 

---

Line 17 defines an instance called integers of class template vector that stores int values. When this object is instantiated, an empty vector is created with size 0 (i.e., the number of elements stored in the vector) and capacity 0 (i.e., the number of elements that can be stored without allocating more memory to the vector).

Lines 19 and 20 demonstrate the size and capacity functions; each initially returns 0 for vector v in this example. Function sizeavailable in every containerreturns the number of elements currently stored in the container. Function capacity returns the number of elements that can be stored in the vector before the vector needs to dynamically resize itself to accommodate more elements.

Lines 2325 use function push_backavailable in all sequence containersto add an element to the end of the vector. If an element is added to a full vector, the vector increases its sizesome STL implementations have the vector double its capacity.

---

Performance Tip 23.10

It can be wasteful to double a vector's size when more space is needed. For example, a full vector of 1,000,000 elements resizes to accommodate 2,000,000 elements when a new element is added. This leaves 999,999 unused elements. Programmers can use resize to control space usage better.

Lines 27 and 28 use size and capacity to illustrate the new size and capacity of the vector after the three push_back operations. Function size returns 3the number of elements added to the vector. Function capacity returns 4, indicating that we can add one more element before the vector needs to add more memory. When we added the first element, the vector allocated space for one element, and the size became 1 to indicate that the vector contained only one element. When we added the second element, the capacity doubled to 2 and the size became 2 as well. When we added the third element, the capacity doubled again to 4. So we can actually add another element before the vector needs to allocation more space. When the vector eventually fills its allocated capacity and the program attempts to add one more element to the vector, the vector will double its capacity to 8 elements.

The manner in which a vector grows to accommodate more elementsa time consuming operationis not specified by the C++ Standard Document. C++ library implementors use various clever schemes to minimize the overhead of resizing a vector. Hence, the output of this program may vary, depending on the version of vector that comes with your compiler. Some library implementors allocate a large initial capacity. If a vector stores a small number of elements, such capacity may be a waste of space. However, it can greatly improve performance if a program adds many elements to a vector and does not have to reallocate memory to accommodate those elements. This is a classic space-time trade-off. Library implementors must balance the amount of memory used against the amount of time required to perform various vector operations.

Lines 3233 demonstrate how to output the contents of an array using pointers and pointer arithmetic. Line 36 calls function printVector (defined at lines 5361) to output the contents of a vector using iterators. Function template printVector receives a const reference to a vector (integers2) as its argument. Line 55 defines a const_iterator called constIterator that iterates through the vector and outputs its contents. Notice that the declaration in line 55 is prefixed with the keyword typename. Because printVector is a function template and vector< T > will be specialized differently for each function-template specialization, the compiler cannot tell at compile time whether or not vector< T >::const_iterator is a type. In particular specialization, const_iterator could be a static variable. The compiler needs this information to compile the program correctly. Therefore, you must tell the compiler that a qualified name, whether the qualifier is a dependent type, is expected to be a type in every specialization.

A const_iterator enables the program to read the elements of the vector, but does not allow the program to modify the elements. The for statement at lines 5860 initializes constIterator using vector member function begin, which returns a const_iterator to the first element in the vectorthere is another version of begin that returns an iterator that can be used for non-const containers. Note that a const_iterator is returned because the identifier integers2 was declared const in the parameter list of function printVector. The loop continues as long as constIterator has not reached the end of the vector. This is determined by comparing constIterator to the result of integers2.end(), which returns an iterator indicating the location past the last element of the vector. If constIterator is equal to this value, the end of the vector has been reached. Functions begin and end are available for all first-class containers. The body of the loop dereferences iterator constIterator to get the value in the current element of the vector. Remember that the iterator acts like a pointer to the element and that operator * is overloaded to return a reference to the element. The expression ++constIterator (line 59) positions the iterator to the next element of the vector.

---

Performance Tip 23.11

Use prefix increment when applied to STL iterators because the prefix increment operator does not return a value that must be stored in a temporary object.

Error-Prevention Tip 23.4

Only random-access iterators support <. It is better to use != and end to test for the end of a container.

Line 40 declares a const_reverse_iterator that can be used to iterate through a vector backward. Line 41 declares a const_reverse_iterator variable tempIterator and initializes it to the iterator returned by function rend (i.e., the iterator for the ending point when iterating through the container in reverse). All first-class containers support this type of iterator. Lines 4446 use a for statement similar to that in function printVector to iterate through the vector. In this loop, function rbegin (i.e., the iterator for the starting point when iterating through the container in reverse) and tempIterator delineate the range of elements to output. As with functions begin and end, rbegin and rend can return a const_reverse_iterator or a reverse_iterator, based on whether or not the container is constant.

Performance Tip 23.12

For performance reasons, capture the loop ending value before the loop and compare against that, rather than having a (potentially expensive) function call for each iteration.

 

Vector Element-Manipulation Functions

Figure 23.15 illustrates functions that enable retrieval and manipulation of the elements of a vector. Line 17 uses an overloaded vector constructor that takes two iterators as arguments to initialize integers. Remember that pointers into an array can be used as iterators. Line 17 initializes integers with the contents of array from location array up tobut not includinglocation array + SIZE.

Figure 23.15. vector class template element-manipulation functions.

(This item is displayed on pages 1129 - 1131 in the print version)

 1 // Fig. 23.15: Fig23_15.cpp
 2 // Testing Standard Library vector class template
 3 // element-manipulation functions.
 4 #include 
 5 using std::cout;
 6 using std::endl;
 7
 8 #include  // vector class-template definition
 9 #include  // copy algorithm
10 #include  // ostream_iterator iterator
11 #include  // out_of_range exception
12
13 int main()
14 {
15 const int SIZE = 6;
16 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 };
17 std::vector< int > integers( array, array + SIZE );
18 std::ostream_iterator< int > output( cout, " " );
19
20 cout << "Vector integers contains: ";
21 std::copy( integers.begin(), integers.end(), output );
22
23 cout << "
First element of integers: " << integers.front()
24 << "
Last element of integers: " << integers.back();
25
26 integers[ 0 ] = 7; // set first element to 7 
27 integers.at( 2 ) = 10; // set element at position 2 to 10
28
29 // insert 22 as 2nd element 
30 integers.insert( integers.begin() + 1, 22 );
31
32 cout << "

Contents of vector integers after changes: ";
33 std::copy( integers.begin(), integers.end(), output );
34
35 // access out-of-range element
36 try
37 {
38 integers.at( 100 ) = 777;
39 } // end try
40 catch ( std::out_of_range outOfRange ) // out_of_range exception
41 {
42 cout << "

Exception: " << outOfRange.what();
43 } // end catch
44
45 // erase first element 
46 integers.erase( integers.begin() );
47 cout << "

Vector integers after erasing first element: ";
48 std::copy( integers.begin(), integers.end(), output );
49
50 // erase remaining elements  
51 integers.erase( integers.begin(), integers.end() );
52 cout << "
After erasing all elements, vector integers ";
53 << ( integers.empty() ? "is" : "is not" ) << " empty";
54
55 // insert elements from array
56 integers.insert( integers.begin(), array, array + SIZE );
57 cout << "

Contents of vector integers before clear: ";
58 std::copy( integers.begin(), integers.end(), output );
59
60 // empty integers; clear calls erase to empty a collection
61 integers.clear();
62 cout << "
After clear, vector integers "
63 << ( integers.empty() ? "is" : "is not" ) << " empty" << endl;
64 return 0;
65 } // end main

 

 Vector integers contains: 1 2 3 4 5 6
 First element of integers: 1
 Last element of integers: 6

 Contents of vector integers after changes: 7 22 2 10 4 5 6

 Exception: invalid vector subscript

 Vector integers after erasing first element: 22 2 10 4 5 6
 After erasing all elements, vector integers is empty

 Contents of vector integers before clear: 1 2 3 4 5 6
 After clear, vector integers is empty

 

---

Line 18 defines an ostream_iterator called output that can be used to output integers separated by single spaces via cout. An ostream_iterator< int > is a type-safe output mechanism that outputs only values of type int or a compatible type. The first argument to the constructor specifies the output stream, and the second argument is a string specifying the separator for the values outputin this case, the string contains a space character. We use the ostream_iterator (defined in header ) to output the contents of the vector in this example.

Line 21 uses algorithm copy from the Standard Library to output the entire contents of vector integers to the standard output. Algorithm copy copies each element in the container starting with the location specified by the iterator in its first argument and continuing up tobut not includingthe location specified by the iterator in its second argument. The first and second arguments must satisfy input iterator requirementsthey must be iterators through which values can be read from a container. Also, applying ++ to the first iterator must eventually cause it to reach the second iterator argument in the container. The elements are copied to the location specified by the output iterator (i.e., an iterator through which a value can be stored or output) specified as the last argument. In this case, the output iterator is an ostream_iterator (output) that is attached to cout, so the elements are copied to the standard output. To use the algorithms of the Standard Library, you must include the header file .

Lines 2324 use functions front and back (available for all sequence containers) to determine the first and last element of the vector, respectively. Notice the difference between functions front and begin. Function front returns a reference to the first element in the vector, while function begin returns a random access iterator pointing to the first element in the vector. Also notice the difference between functions back and end. Function back returns a reference to the last element in the vector, while function end returns a random access iterator pointing to the end of the vector (the location after the last element).

---

Common Programming Error 23.3

The vector must not be empty; otherwise, results of the front and back functions are undefined.

Lines 2627 illustrate two ways to subscript through a vector (which also can be used with the deque containers). Line 26 uses the subscript operator that is overloaded to return either a reference to the value at the specified location or a constant reference to that value, depending on whether the container is constant. Function at (line 27) performs the same operation, but with bounds checking. Function at first checks the value supplied as an argument and determines whether it is in the bounds of the vector. If not, function at tHRows an out_of_bounds exception defined in header (as demonstrated in lines 3643). Figure 23.16 shows some of the STL exception types. (The Standard Library exception types are discussed in Chapter 16, Exception Handling.)

Figure 23.16. Some STL exception types.

STL exception types	Description
out_of_range	Indicates when subscript is out of rangee.g., when an invalid subscript is specified to vector member function at.
invalid_argument	Indicates an invalid argument was passed to a function.
length_error	Indicates an attempt to create too long a container, string, etc.
bad_alloc	Indicates that an attempt to allocate memory with s (or with an allocator) failed because not enough memory was available.

Line 30 uses one of the three overloaded insert functions provided by each sequence container. Line 30 inserts the value 22 before the element at the location specified by the iterator in the first argument. In this example, the iterator is pointing to the second element of the vector, so 22 is inserted as the second element and the original second element becomes the third element of the vector. Other versions of insert allow inserting multiple copies of the same value starting at a particular position in the container, or inserting a range of values from another container (or array), starting at a particular position in the original container.

Lines 46 and 51 use the two erase functions that are available in all first-class containers. Line 46 indicates that the element at the location specified by the iterator argument should be removed from the container (in this example, the element at the beginning of the vector). Line 51 specifies that all elements in the range starting with the location of the first argument up tobut not includingthe location of the second argument should be erased from the container. In this example, all the elements are erased from the vector. Line 53 uses function empty (available for all containers and adapters) to confirm that the vector is empty.

Common Programming Error 23.4

Erasing an element that contains a pointer to a dynamically allocated object does not delete that object; this can lead to a memory leak.

Line 56 demonstrates the version of function insert that uses the second and third arguments to specify the starting location and ending location in a sequence of values (possibly from another container; in this case, from array of integers array) that should be inserted into the vector. Remember that the ending location specifies the position in the sequence after the last element to be inserted; copying is performed up tobut not includingthis location.

---

Finally, line 61 uses function clear (found in all first-class containers) to empty the vector. This function calls the version of erase used in line 51 to empty the vector.

[Note: Other functions that are common to all containers and common to all sequence containers have not yet been covered. We will cover most of these in the next few sections. We will also cover many functions that are specific to each container.]

23.2.2. list Sequence Container

The list sequence container provides an efficient implementation for insertion and deletion operations at any location in the container. If most of the insertions and deletions occur at the ends of the container, the deque data structure (Section 23.2.3) provides a more efficient implementation. Class template list is implemented as a doubly linked listevery node in the list contains a pointer to the previous node in the list and to the next node in the list. This enables class template list to support bidirectional iterators that allow the container to be traversed both forward and backward. Any algorithm that requires input, output, forward or bidirectional iterators can operate on a list. Many of the list member functions manipulate the elements of the container as an ordered set of elements.

In addition to the member functions of all STL containers in Fig. 23.2 and the common member functions of all sequence containers discussed in Section 23.2, class template list provides nine other member functionssplice, push_front, pop_front, remove, remove_if, unique, merge, reverse and sort. Several of these member functions are list-optimized implementations of STL algorithms presented in Section 23.5. Figure 23.17 demonstrates several features of class list. Remember that many of the functions presented in Figs. 23.1423.15 can be used with class list. Header file must be included to use class list.

Figure 23.17. Standard Library list class template.

(This item is displayed on pages 1133 - 1135 in the print version)

 1 // Fig. 23.17: Fig23_17.cpp
 2 // Standard library list class template test program.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include  // list class-template definition
 8 #include  // copy algorithm
 9 #include  // ostream_iterator
10 
11 // prototype for function template printList
12 template < typename T > void printList( const std::list< T > &listRef );
13 
14 int main()
15 {
16 const int SIZE = 4;
17 int array[ SIZE ] = { 2, 6, 4, 8 };
18 std::list< int > values; // create list of ints
19 std::list< int > otherValues; // create list of ints
20 
21 // insert items in values
22 values.push_front( 1 ); 
23 values.push_front( 2 ); 
24 values.push_back( 4 ); 
25 values.push_back( 3 ); 
26 
27 cout << "values contains: ";
28 printList( values );
29 
30 values.sort(); // sort values
31 cout << "
values after sorting contains: ";
32 printList( values );
33 
34 // insert elements of array into otherValues 
35 otherValues.insert( otherValues.begin(), array, array + SIZE );
36 cout << "
After insert, otherValues contains: ";
37 printList( otherValues );
38 
39 // remove otherValues elements and insert at end of values
40 values.splice( values.end(), otherValues ); 
41 cout << "
After splice, values contains: ";
42 printList( values );
43 
44 values.sort(); // sort values
45 cout << "
After sort, values contains: ";
46 printList( values );
47 
48 // insert elements of array into otherValues 
49 otherValues.insert( otherValues.begin(), array, array + SIZE );
50 otherValues.sort(); 
51 cout << "
After insert, otherValues contains: ";
52 printList( otherValues );
53 
54 // remove otherValues elements and insert into values in sorted order
55 values.merge( otherValues ); 
56 cout << "
After merge:
 values contains: ";
57 printList( values );
58 cout << "
 otherValues contains: ";
59 printList( otherValues );
60 
61 values.pop_front(); // remove element from front
62 values.pop_back(); // remove element from back 
63 cout << "
After pop_front and pop_back:
 values contains: "
64 printList( values );
65 
66 values.unique(); // remove duplicate elements
67 cout << "
After unique, values contains: ";
68 printList( values );
69 
70 // swap elements of values and otherValues
71 values.swap( otherValues ); 
72 cout << "
After swap:
 values contains: ";
73 printList( values );
74 cout << "
 otherValues contains: ";
75 printList( otherValues );
76 
77 // replace contents of values with elements of otherValues
78 values.assign( otherValues.begin(), otherValues.end() ); 
79 cout << "
After assign, values contains: ";
80 printList( values );
81 
82 // remove otherValues elements and insert into values in sorted order
83 values.merge( otherValues ); 
84 cout << "
After merge, values contains: ";
85 printList( values );
86 
87 values.remove( 4 ); // remove all 4s
88 cout << "
After remove( 4 ), values contains: ";
89 printList( values );
90 cout << endl;
91 return 0;
92 } // end main
93 
94 // printList function template definition; uses
95 // ostream_iterator and copy algorithm to output list elements
96 template < typename T > void printList( const std::list< T > &listRef )
97 {
98 if ( listRef.empty() ) // list is empty
99 cout << "List is empty";
100 else
101 {
102 std::ostream_iterator< T > output( cout, " " );
103 std::copy( listRef.begin(), listRef.end(), output );
104 } // end else
105 } // end function printList

 

 values contains: 2 1 4 3
 values after sorting contains: 1 2 3 4
 After insert, otherValues contains: 2 6 4 8
 After splice, values contains: 1 2 3 4 2 6 4 8
 After sort, values contains: 1 2 2 3 4 4 6 8
 After insert, otherValues contains: 2 4 6 8
 After merge:
 values contains: 1 2 2 2 3 4 4 4 6 6 8 8
 otherValues contains: List is empty
 After pop_front and pop_back:
 values contains: 2 2 2 3 4 4 4 6 6 8
 After unique, values contains: 2 3 4 6 8
 After swap:
 values contains: List is empty
 otherValues contains: 2 3 4 6 8
 After assign, values contains: 2 3 4 6 8
 After merge, values contains: 2 2 3 3 4 4 6 6 8 8
 After remove( 4 ), values contains: 2 2 3 3 6 6 8 8

 

---

Lines 1819 instantiate two list objects capable of storing integers. Lines 2223 use function push_front to insert integers at the beginning of values. Function push_front is specific to classes list and deque (not to vector). Lines 2425 use function push_back to insert integers at the end of values. Remember that function push_back is common to all sequence containers.

Line 30 uses list member function sort to arrange the elements in the list in ascending order. [Note: This is different from the sort in the STL algorithms.] A second version of function sort that allows the programmer to supply a binary predicate function that takes two arguments (values in the list), performs a comparison and returns a bool value indicating the result. This function determines the order in which the elements of the list are sorted. This version could be particularly useful for a list that stores pointers rather than values. [Note: We demonstrate a unary predicate function in Fig. 23.28. A unary predicate function takes a single argument, performs a comparison using that argument and returns a bool value indicating the result.]

Line 40 uses list function splice to remove the elements in otherValues and insert them into values before the iterator position specified as the first argument. There are two other versions of this function. Function splice with three arguments allows one element to be removed from the container specified as the second argument from the location specified by the iterator in the third argument. Function splice with four arguments uses the last two arguments to specify a range of locations that should be removed from the container in the second argument and placed at the location specified in the first argument.

After inserting more elements in otherValues and sorting both values and otherValues, line 55 uses list member function merge to remove all elements of otherValues and insert them in sorted order into values. Both lists must be sorted in the same order before this operation is performed. A second version of merge enables the programmer to supply a predicate function that takes two arguments (values in the list) and returns a bool value. The predicate function specifies the sorting order used by merge.

Line 61 uses list function pop_front to remove the first element in the list. Line 62 uses function pop_back (available for all sequence containers) to remove the last element in the list.

Line 66 uses list function unique to remove duplicate elements in the list. The list should be in sorted order (so that all duplicates are side by side) before this operation is performed, to guarantee that all duplicates are eliminated. A second version of unique enables the programmer to supply a predicate function that takes two arguments (values in the list) and returns a bool value specifying whether two elements are equal.

Line 71 uses function swap (available to all containers) to exchange the contents of values with the contents of otherValues.

Line 78 uses list function assign to replace the contents of values with the contents of otherValues in the range specified by the two iterator arguments. A second version of assign replaces the original contents with copies of the value specified in the second argument. The first argument of the function specifies the number of copies. Line 87 uses list function remove to delete all copies of the value 4 from the list.

23.2.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 STL 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 23.4.2).

---

Additional storage for a deque can be allocated at either end of the deque in blocks of memory that are typically maintained as an array of pointers to those blocks.[3] 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 or pointer-based arrays.

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

Performance Tip 23.13

In general, deque has slightly higher overhead than vector.

Performance Tip 23.14

Insertions and deletions in the middle of a deque are optimized to minimize the number of elements copied, so it is 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 adds member functions push_front and pop_front to allow insertion and deletion at the beginning of the deque, respectively.

Figure 23.18 demonstrates features of class deque. Remember that many of the functions presented in Fig. 23.14, Fig. 23.15 and Fig. 23.17 also can be used with class deque. Header file must be included to use class deque.

Figure 23.18. Standard Library deque class template.

(This item is displayed on pages 1137 - 1138 in the print version)

 1 // Fig. 23.18: Fig23_18.cpp
 2 // Standard Library class deque test program.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include  // deque class-template definition
 8 #include  // copy algorithm
 9 #include  // ostream_iterator
10
11 int main()
12 {
13 std::deque< double > values; // create deque of doubles
14 std::ostream_iterator< double > output( cout, " " );
15
16 // insert elements in values
17 values.push_front( 2.2 ); 
18 values.push_front( 3.5 ); 
19 values.push_back( 1.1 ); 
20
21 cout << "values contains: ";
22
23 // use subscript operator to obtain elements of values
24 for ( unsigned int i = 0; i < values.size(); i++ )
25 cout << values[ i ] << ' ';
26
27 values.pop_front(); // remove first element
28 cout << "
After pop_front, values contains: ";
29 std::copy( values.begin(), values.end(), output );
30
31 // use subscript operator to modify element at location 1
32 values[ 1 ] = 5.4; 
33 cout << "
After values[ 1 ] = 5.4, values contains: ";
34 std::copy( values.begin(), values.end(), output );
35 cout << endl;
36 return 0;
37 } // 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 13 instantiates a deque that can store double values. Lines 1719 use functions push_front and push_back to insert elements at the beginning and end of the deque. Remember that push_back is available for all sequence containers, but push_front is available only for class list and class deque.

---

The for statement at lines 2425 uses the subscript operator to retrieve the value in each element of the deque for output. Note that the condition uses function size to ensure that we do not attempt to access an element outside the bounds of the deque.

Line 27 uses function pop_front to demonstrate removing the first element of the deque. Remember that pop_front is available only for class list and class deque (not for class vector).

Line 32 uses the subscript operator to create an lvalue. This enables values to be assigned directly to any element of the deque.