We’ve repeatedly emphasized the importance of software reuse. Recognizing that many data structures and algorithms commonly are used by C++ programmers, the C++ standard committee added the Standard Template Library (STL) to the C++ Standard Library. The STL defines powerful, template-based, reusable components that implement many common data structures and algorithms used to process those data structures. The STL offers proof of concept for generic programming with templates—introduced in Chapter 14, Templates. [Note: In industry, the features presented in this chapter are often referred to as the Standard Template Library or STL. However, these terms are not used in the C++ standard document, because these features are simply considered to be part of the C++ Standard Library.]

The STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packard and is based on their research in the field of generic programming, with significant contributions from David Musser. As you’ll see, the STL was conceived and designed for performance and flexibility.

This chapter introduces the STL and discusses its three key components—containers (popular templatized data structures), iterators and algorithms. The STL containers are data structures capable of storing objects of almost any data type (there are some restrictions). We’ll see that there are three styles of container classes—first-class containers, adapters and near containers.

Performance Tip 20.1

For any particular application, several different STL containers might be appropriate. Select the most appropriate container that achieves the best performance (i.e., balance of speed and size) for that application. Efficiency was a crucial consideration in the STL’s design.

Performance Tip 20.2

Standard Library capabilities are implemented to operate efficiently across many applications. For some applications with unique performance requirements, it might be necessary to write your own customized implementations.

Each STL container has associated member functions. A subset of these member functions is defined in all STL containers. We illustrate most of this common functionality in our examples of STL containers vector (a dynamically resizable array which we introduced in Chapter 7, Arrays and Vectors), list (a doubly linked list) and deque (a double-ended queue, pronounced “deck”). We introduce container-specific functionality in examples for each of the other STL containers.

STL iterators, which have properties similar to those of pointers, are used by programs to manipulate the STL-container elements. In fact, standard arrays can be manipulated by STL algorithms, using standard pointers as iterators. We’ll see that manipulating containers with iterators is convenient and provides tremendous expressive power when combined with STL algorithms—in some cases, reducing many lines of code to a single statement. There are five categories of iterators, each of which we discuss in Section 20.1.2 and use throughout this chapter.

STL algorithms are functions that perform such common data manipulations as searching, sorting and comparing elements (or entire containers). The STL provides approximately 70 algorithms. Most of them use iterators to access container elements. Each algorithm has minimum requirements for the types of iterators that can be used with it. We’ll see that each first-class container supports specific iterator types, some more powerful than others. A container’s supported iterator type determines whether the container can be used with a specific algorithm. Iterators encapsulate the mechanism used to access container elements. This encapsulation enables many of the STL algorithms to be applied to several containers without regard for the underlying container implementation. As long as a container’s iterators support the minimum requirements of the algorithm, then the algorithm can process that container’s elements. This also enables programmers to create new algorithms that can process the elements of multiple container types.

Software Engineering Observation 20.1

The STL approach allows general programs to be written so that the code does not depend on the underlying container. Such a programming style is called generic programming.

Data structures like linked lists, queues, stacks and trees carefully weave objects together with pointers. Pointer-based code is complex, and the slightest omission or oversight can lead to serious memory-access violations and memory-leak errors with no compiler complaints. Implementing additional data structures, such as deques, priority queues, sets and maps, requires substantial extra work. In addition, if many programmers on a large project implement similar containers and algorithms for different tasks, the code becomes difficult to modify, maintain and debug. An advantage of the STL is that programmers can reuse the STL containers, iterators and algorithms to implement common data representations and manipulations. This reuse can save substantial development time, money and effort.

Software Engineering Observation 20.2

Avoid reinventing the wheel; program with the reusable components of the C++ Standard Library. STL includes many of the most popular data structures as containers and provides various popular algorithms to process data in these containers.

Error-Prevention Tip 20.1

When programming pointer-based data structures and algorithms, we must do our own debugging and testing to be sure our data structures, classes and algorithms function properly. It is easy to make errors when manipulating pointers at this low level. Memory leaks and memory-access violations are common in such custom code. For most programmers, and for most of the applications they will need to write, the prepackaged, templatized containers of the STL are sufficient. Using the STL helps programmers reduce testing and debugging time. One caution is that, for large projects, template compile time can be significant.

This chapter introduces the STL. It is by no means complete or comprehensive. However, it is a friendly, accessible chapter that should convince you of the value of the STL in software reuse and encourage further study.

20.1.1 Introduction to Containers

The STL container types are shown in Fig. 20.1. The containers are divided into three major categories—sequence containers, associative containers and container adapters.

Fig. 20.1 Standard Library container classes.

STL Containers Overview

The sequence containers represent linear data structures, such as vectors and linked lists. Associative containers are nonlinear containers that typically can locate elements stored in the containers quickly. Such containers can store sets of values or key/value pairs. The sequence containers and associative containers are collectively referred to as the first-class containers. Stacks and queues actually are constrained versions of sequential containers. For this reason, STL implements stacks and queues as container adapters that enable a program to view a sequential container in a constrained manner. There are other container types that are considered “near containers”—C-like pointer-based arrays (discussed in Chapter 7), bitsets for maintaining sets of flag values and valarrays for performing high-speed mathematical vector operations (this last class is optimized for computation performance and is not as flexible as the first-class containers). These types are considered “near containers” because they exhibit capabilities similar to those of the first-class containers, but do not support all the first-class-container capabilities. Type string (discussed in Chapter 18) supports the same functionality as a sequence container, but stores only character data.

STL Container Common Functions

Most STL containers provide similar functionality. Many generic operations, such as member function size, apply to all containers, and other operations apply to subsets of similar containers. This encourages extensibility of the STL with new classes. Figure 20.2 describes the functions common to all Standard Library containers. [Note: Overloaded operators operator<, operator<=, operator>, operator>=, operator== and operator!= are not provided for priority_queues.]

Fig. 20.2 STL container common functions.

STL Container Header Files

The header files for each of the Standard Library containers are shown in Fig. 20.3. The contents of these header files are all in namespace std.

Fig. 20.3 Standard Library container header files.

First-Class Container Common typedefs

Figure 20.4 shows the common typedefs (to create synonyms or aliases for lengthy type names) found in first-class containers. These typedefs are used in generic declarations of variables, parameters to functions and return values from functions. For example, value_type in each container is always a typedef that represents the type of value stored in the container.

Fig. 20.4 typedefs found in first-class containers.

Performance Tip 20.3

STL generally avoids inheritance and virtual functions in favor of using generic programming with templates to achieve better execution-time performance.

Portability Tip 20.1

Programming with STL will enhance the portability of your code.

When preparing to use an STL container, it is important to ensure that the type of element being stored in the container supports a minimum set of functionality. When an element is inserted into a container, a copy of that element is made. For this reason, the element type should provide its own copy constructor and assignment operator. [Note: This is required only if default memberwise copy and default memberwise assignment do not perform proper copy and assignment operations for the element type.] Also, the associative containers and many algorithms require elements to be compared. For this reason, the element type should provide an equality operator (==) and a less-than operator (<).

Software Engineering Observation 20.3

The STL containers technically do not require their elements to be comparable with the equality and less-than operators unless a program uses a container member function that must compare the container elements (e.g., the sort function in class list). Unfortunately, some prestandard C++ compilers are not capable of ignoring parts of a template that are not used in a particular program. On compilers with this problem, you may not be able to use the STL containers with objects of classes that do not define overloaded less-than and equality operators.

20.1.2 Introduction to Iterators

Iterators have many features in common with pointers and are used to point to the elements of first-class containers (and for a few other purposes, as we’ll see). Iterators hold state information sensitive to the particular containers on which they operate; thus, iterators are implemented appropriately for each type of container. Certain iterator operations are uniform across containers. For example, the dereferencing operator (*) dereferences an iterator so that you can use the element to which it points. The ++ operation on an iterator moves it to the next element of the container (much as incrementing a pointer into an array aims the pointer at the next element of the array).

STL first-class containers provide member functions begin and end. Function begin returns an iterator pointing to the first element of the container. Function end returns an iterator pointing to the first element past the end of the container (an element that doesn’t exist). If iterator i points to a particular element, then ++i points to the “next” element and *i refers to the element pointed to by i. The iterator resulting from end is typically used in an equality or inequality comparison to determine whether the “moving iterator” (i in this case) has reached the end of the container.

We use an object of type iterator to refer to a container element that can be modified. We use an object of type const_iterator to refer to a container element that cannot be modified.

Using istream_iterator for Input and Using ostream_iterator for Output

We use iterators with sequences (also called ranges). These sequences can be in containers, or they can be input sequences or output sequences. The program of Fig. 20.5 demonstrates input from the standard input (a sequence of data for input into a program), using an istream_iterator, and output to the standard output (a sequence of data for output from a program), using an ostream_iterator. The program inputs two integers from the user at the keyboard and displays the sum of the integers.¹

Fig. 20.5 Input and output stream iterators.

 1   // Fig. 20.5: fig20_05.cpp
 2   // Demonstrating input and output with iterators.
 3   #include <iostream>
 4   using std::cout;
 5   using std::cin;
 6   using std::endl;
 7
 8   #include <iterator> // ostream_iterator and istream_iterator
 9
10   int main()
11   {
12      cout << "Enter two integers: ";
13
14      // create istream_iterator for reading int values from cin
15      std::istream_iterator< int > inputInt( cin );             
16
17      int number1 = *inputInt; // read int from standard input
18      ++inputInt; // move iterator to next input value        
19      int number2 = *inputInt; // read int from standard input
20
21      // create ostream_iterator for writing int values to cout
22      std::ostream_iterator< int > outputInt( cout );          
23
24      cout << "The sum is: " ;
25      *outputInt = number1 + number2; // output result to cout
26      cout << endl;
27      return 0;
28   } // end main

Enter two integers: 12 25
The sum is: 37

Line 15 creates an istream_iterator that is capable of extracting (inputting) int values in a type-safe manner from the standard input object cin. Line 17 dereferences iterator inputInt to read the first integer from cin and assigns that integer to number1. Note that the dereferencing operator * applied to inputInt gets the value from the stream associated with inputInt; this is similar to dereferencing a pointer. Line 18 positions iterator inputInt to the next value in the input stream. Line 19 inputs the next integer from inputInt and assigns it to number2.

Line 22 creates an ostream_iterator that is capable of inserting (outputting) int values in the standard output object cout. Line 25 outputs an integer to cout by assigning to *outputInt the sum of number1 and number2. Notice the use of the dereferencing operator * to use *outputInt as an lvalue in the assignment statement. If you want to output another value using outputInt, the iterator must be incremented with ++ (both the prefix and postfix increment can be used, but the prefix form should be preferred for performance reasons).

Error-Prevention Tip 20.2

The * (dereferencing) operator of any const iterator returns a const reference to the container element, disallowing the use of non-const member functions.

Common Programming Error 20.1

Attempting to dereference an iterator positioned outside its container is a runtime logic error. In particular, the iterator returned by end cannot be dereferenced or incremented.

Common Programming Error 20.2

Attempting to create a non-const iterator for a const container results in a compilation error.

Iterator Categories and Iterator Category Hierarchy

Figure 20.6 shows the categories of STL iterators. Each category provides a specific set of functionality. Figure 20.7 illustrates the hierarchy of iterator categories. As you follow the hierarchy from top to bottom, each iterator category supports all the functionality of the categories above it in the figure. Thus the “weakest” iterator types are at the top and the most powerful one is at the bottom. Note that this is not an inheritance hierarchy.

Fig. 20.6 Iterator categories.

Fig. 20.7 Iterator category hierarchy.

The iterator category that each container supports determines whether that container can be used with specific algorithms in the STL. Containers that support random-access iterators can be used with all algorithms in the STL. As we’ll see, pointers into arrays can be used in place of iterators in most STL algorithms, including those that require random-access iterators. Figure 20.8 shows the iterator category of each of the STL containers. Note that vectors, deques, lists, sets, multisets, maps, multimaps (i.e., the first-class containers), strings and arrays are traversable with iterators.

Fig. 20.8 Iterator types supported by each Standard Library container.

Container		Type of iterator supported
Sequence containers (first class)
	vector	random access
	deque	random access
	list	bidirectional
Associative containers (first class)
	set	bidirectional
	multiset	bidirectional
	map	bidirectional
	multimap	bidirectional
Container adapters
	stack	no iterators supported
	queue	no iterators supported
	priority_queue	no iterators supported

Software Engineering Observation 20.4

Using the “weakest iterator” that yields acceptable performance helps produce maximally reusable components. For example, if an algorithm requires only forward iterators, it can be used with any container that supports forward iterators, bidirectional iterators or random-access iterators. However, an algorithm that requires random-access iterators can be used only with containers that have random-access iterators.

Predefined Iterator typedefs

Figure 20.9 shows the predefined iterator typedefs that are found in the class definitions of the STL containers. Not every typedef is defined for every container. We use const versions of the iterators for traversing read-only containers. We use reverse iterators to traverse containers in the reverse direction.

Fig. 20.9 Iterator typedefs.

Predefined typedefs for iterator types	Direction of ++	Capability
iterator	forward	read/write
const_iterator	forward	read
reverse_iterator	backward	read/write
const_reverse_iterator	backward	read

Error-Prevention Tip 20.3

Operations performed on a const_iterator return const references to prevent modification to elements of the container being manipulated. Using const_iterators in preference to iterators where appropriate is another example of the principle of least privilege.

Iterator Operations

Figure 20.10 shows some operations that can be performed on each iterator type. Note that the operations for each iterator type include all operations preceding that type in the figure. Note also that, for input iterators and output iterators, it is not possible to save the iterator and then use the saved value later.

Fig. 20.10 Iterator operations for each type of iterator.

Iterator operation	Description
All iterators
++p	Preincrement an iterator.
p++	Postincrement an iterator.
Input iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
p == p1	Compare iterators for equality.
p != p1	Compare iterators for inequality.
Output iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
Forward iterators	Forward iterators provide all the functionality of both input iterators and output iterators.
Bidirectional iterators
--p	Predecrement an iterator.
p--	Postdecrement an iterator.
Random-access iterators
p += i	Increment the iterator p by i positions.
p -= i	Decrement the iterator p by i positions.
p + i or i + p	Expression value is an iterator positioned at p incremented by i positions.
p - i	Expression value is an iterator positioned at p decremented by i positions.
p - p1	Expression value is an integer representing the distance between two elements in the same container.
p[ i ]	Return a reference to the element offset from p by i positions
p < p1	Return true if iterator p is less than iterator p1 (i.e., iterator p is before iterator p1 in the container); otherwise, return false.
p <= p1	Return true if iterator p is less than or equal to iterator p1 (i.e., iterator p is before iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.
p > p1	Return true if iterator p is greater than iterator p1 (i.e., iterator p is after iterator p1 in the container); otherwise, return false.
p >= p1	Return true if iterator p is greater than or equal to iterator p1 (i.e., iterator p is after iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.

20.1.3 Introduction to Algorithms

STL algorithms can be used generically across a variety of containers. STL provides many algorithms you’ll use frequently to manipulate containers. Inserting, deleting, searching, sorting and others are appropriate for some or all of the STL containers.

The STL includes approximately 70 standard algorithms. We provide live-code examples of most of these and summarize the others in tables. The algorithms operate on container elements only indirectly through iterators. Many algorithms operate on sequences of elements defined by pairs of iterators—a first iterator pointing to the first element of the sequence and a second iterator pointing to one element past the last element of the sequence. Also, it is possible to create your own new algorithms that operate in a similar fashion so they can be used with the STL containers and iterators.

Algorithms often return iterators that indicate the results of the algorithms. Algorithm find, for example, locates an element and returns an iterator to that element. If the element is not found, find returns the “one past the end” iterator that was passed in to define the end of the range to be searched, which can be tested to determine whether an element was not found. The find algorithm can be used with any first-class STL container. STL algorithms create yet another opportunity for reuse—using the rich collection of popular algorithms can save programmers much time and effort.

If an algorithm uses less powerful iterators, the algorithm can also be used with containers that support more powerful iterators. Some algorithms demand powerful iterators; e.g., sort demands random-access iterators.

Software Engineering Observation 20.5

The STL is implemented concisely. Until now, class designers would have associated the algorithms with the containers by making the algorithms member functions of the containers. The STL takes a different approach. The algorithms are separated from the containers and operate on elements of the containers only indirectly through iterators. This separation makes it easier to write generic algorithms applicable to many container classes.

Software Engineering Observation 20.6

The STL is extensible. It is straightforward to add new algorithms and to do so without changes to STL containers.

Software Engineering Observation 20.7

STL algorithms can operate on STL containers and on pointer-based, C-like arrays.

Portability Tip 20.2

Because STL algorithms process containers only indirectly through iterators, one algorithm can often be used with many different containers.

Figure 20.11 shows many of the mutating-sequence algorithms—i.e., the algorithms that result in modifications of the containers to which the algorithms are applied.

Fig. 20.11 Mutating-sequence algorithms.

Mutating-sequence algorithms
copy	remove	reverse_copy
copy_backward	remove_copy	rotate
fill	remove_copy_if	rotate_copy
fill_n	remove_if	stable_partition
generate	replace	swap
generate_n	replace_copy	swap_ranges
iter_swap	replace_copy_if	transform
partition	replace_if	unique
random_shuffle	reverse	unique_copy

Figure 20.12 shows many of the nonmodifying sequence algorithms—i.e., the algorithms that do not result in modifications of the containers to which they are applied. Figure 20.13 shows the numerical algorithms of the header file <numeric>.

Fig. 20.12 Nonmodifying sequence algorithms.

Nonmodifying sequence algorithms
adjacent_find	find	find_if
count	find_each	mismatch
count_if	find_end	search
equal	find_first_of	search_n

Fig. 20.13 Numerical algorithms from header file <numeric>.

Numerical algorithms from header file <numeric>
accumulate	partial_sum
inner_product	adjacent_difference

20.2 Sequence Containers

The C++ Standard Template Library provides three sequence containers—vector, list and deque. Class template vector and class template deque both are based on arrays. Class template list implements a linked-list data structure.

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 20.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 20.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. You must choose the container most appropriate for the application.

Performance Tip 20.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 20.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. 20.2, the sequence containers have several other common operations—front to return a reference to the first element in a non-empty container, back to return a reference to the last element in a non-empty 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.

20.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 easily accessible via a subscript or will be sorted. 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 20.7

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

Performance Tip 20.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 20.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 iterators—i.e., all iterator operations shown in Fig. 20.10 can be applied to a vector iterator. All STL algorithms can operate on a vector. The iterators for a vector are sometimes 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 20.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 <vector> to use class template vector.

Fig. 20.14 Standard Library vector class template.

 1   // Fig. 20.14: fig20_14.cpp
 2   // Demonstrating Standard Library vector class template.
 3   #include <iostream>
 4   using std::cout;
 5   using std::endl;
 6
 7   #include <vector> // 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 size—available in every container—returns 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 23–25 use function push_back—available in all sequence containers—to add an element to the end of the vector. If an element is added to a full vector, the vector increases its size—some STL implementations have the vector double its capacity.

Performance Tip 20.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 and reserve 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 3—the 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 elements—a time consuming operation—is 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 32–33 demonstrate how to output the contents of an array using pointers and pointer arithmetic. Line 36 calls function printVector (defined in lines 53–61) 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, when 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 in lines 58–60 initializes constIterator using vector member function begin, which returns a const_iterator to the first element in the vector—there 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 20.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 20.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 44–46 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 20.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 20.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 to—but not including—location array + SIZE.

Fig. 20.15 vector class template element-manipulation functions.

 1   // Fig. 20.15: fig20_15.cpp
 2   // Testing Standard Library vector class template
 3   // element-manipulation functions.
 4   #include <iostream>
 5   using std::cout;
 6   using std::endl;

 7
 8   #include <vector>  // vector class-template definition
 9   #include <algorithm> // copy algorithm
10   #include <iterator> // ostream_iterator iterator
11   #include <stdexcept> // 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<T> 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 output—in this case, the string contains a space character. We use the ostream_iterator (defined in header <iterator>) 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 to—but not including—the location specified by the iterator in its second argument. The first and second arguments must satisfy input iterator requirements—they 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 <algorithm>.

Lines 23–24 use functions front and back (available for all sequence containers) to determine the vector’s first and last elements, 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 20.3

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

Lines 26–27 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 <stdexcept> (as demonstrated in lines 36–43). Figure 20.16 shows some of the STL exception types. (The Standard Library exception types are discussed in Chapter 16, Exception Handling.)

Fig. 20.16 Some STL exception types.

STL exception types	Description
out_of_range	Indicates when subscript is out of range—e.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 new (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 to—but not including—the 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 20.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 to—but not including—this 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’ll cover most of these in the next few sections. We’ll also cover many functions that are specific to each container.]

20.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 20.2.3) provides a more efficient implementation. Class template list is implemented as a doubly linked list—every 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 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. 20.2 and the common member functions of all sequence containers discussed in Section 20.2, class template list provides nine other member functions—splice, 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 20.5. Figure 20.17 demonstrates several features of class list. Remember that many of the functions presented in Figs. 20.14–20.15 can be used with class list. Header file <list> must be included to use class list.

Fig. 20.17 Standard Library list class template.

 1   // Fig. 20.17: fig20_17.cpp
 2   // Standard library list class template test program.
 3   #include <iostream>
 4   using std::cout;
 5   using std::endl;
 6
 7   #include <list> // list class-template definition
 8   #include <algorithm> // copy algorithm
 9   #include <iterator> // 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 and sort, 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 and sort, 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 18–19 instantiate two list objects capable of storing integers. Lines 22–23 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 24–25 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 allows you 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. 20.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 you 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 you 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.

20.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 20.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.² 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.

Performance Tip 20.13

In general, deque has higher overhead than vector.

Performance Tip 20.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 20.18 demonstrates features of class deque. Remember that many of the functions presented in Fig. 20.14, Fig. 20.15 and Fig. 20.17 also can be used with class deque. Header file <deque> must be included to use class deque.

Fig. 20.18 Standard Library deque class template.

 1   // Fig. 20.18: fig20_18.cpp
 2   // Standard Library class deque test program.
 3   #include <iostream>
 4   using std::cout;
 5   using std::endl;
 6
 7   #include <deque> // deque class-template definition
 8   #include <algorithm> // copy algorithm
 9   #include <iterator> // 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 17–19 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 in lines 24–25 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.

The STL’s associative containers provide direct access to store and retrieve elements via keys (often called search keys). The four associative containers are multiset, set, multimap and map. Each associative container maintains its keys in sorted order. Iterating through an associative container traverses it in the sort order for that container. Classes multiset and set provide operations for manipulating sets of values where the values are the keys—there is not a separate value associated with each key. The primary difference between a multiset and a set is that a multiset allows duplicate keys and a set does not. Classes multimap and map provide operations for manipulating values associated with keys (these values are sometimes referred to as mapped values). The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values. In addition to the common member functions of all containers presented in Fig. 20.2, all associative containers also support several other member functions, including find, lower_bound, upper_bound and count. Examples of each of the associative containers and the common associative container member functions are presented in the next several subsections.

Line 10 uses a typedef to create a new type name (alias) for a multiset of integers ordered in ascending order, using the function object less< int >. Ascending order is the default for a multiset, so std::less< int > can be omitted in line 10. This new type (Ims) is then used to instantiate an integer multiset object, intMultiset (line 19).

Good Programming Practice 20.1

Use typedefs to make code with long type names (such as multisets) easier to read.

The output statement in line 22 uses function count (available to all associative containers) to count the number of occurrences of the value 15 currently in the multiset.

Lines 25–26 use one of the three versions of function insert to add the value 15 to the multiset twice. A second version of insert takes an iterator and a value as arguments and begins the search for the insertion point from the iterator position specified. A third version of insert takes two iterators as arguments that specify a range of values to add to the multiset from another container.

Line 34 uses function find (available to all associative containers) to locate the value 15 in the multiset. Function find returns an iterator or a const_iterator pointing to the earliest location at which the value is found. If the value is not found, find returns an iterator or a const_iterator equal to the value returned by a call to end. Line 42 demonstrates this case.

Line 46 uses function insert to insert the elements of array a into the multiset. In line 48, the copy algorithm copies the elements of the multiset to the standard output. Note that the elements are displayed in ascending order.

Lines 52 and 53 use functions lower_bound and upper_bound (available in all associative containers) to locate the earliest occurrence of the value 22 in the multiset and the element after the last occurrence of the value 22 in the multiset. Both functions return iterators or const_iterators pointing to the appropriate location or the iterator returned by end if the value is not in the multiset.

Line 56 instantiates an instance of class pair called p. Objects of class pair are used to associate pairs of values. In this example, the contents of a pair are two const_iterators for our integer-based multiset. The purpose of p is to store the return value of multiset function equal_range that returns a pair containing the results of both a lower_bound and an upper_bound operation. Type pair contains two public data members called first and second.

Line 60 uses function equal_range to determine the lower_bound and upper_bound of 22 in the multiset. Line 63 uses p.first and p.second, respectively, to access the lower_bound and upper_bound. We dereferenced the iterators to output the values at the locations returned from equal_range.

The set associative container is used for fast storage and retrieval of unique keys. The implementation of a set is identical to that of a multiset, except that a set must have unique keys. Therefore, if an attempt is made to insert a duplicate key into a set, the duplicate is ignored; because this is the intended mathematical behavior of a set, we do not identify it as a common programming error. A set supports bidirectional iterators (but not random-access iterators). Figure 20.20 demonstrates a set of doubles. Header file <set> must be included to use class set.

Class stack enables insertions into and deletions from the underlying data structure at one end (commonly referred to as a last-in, first-out data structure). A stack can be implemented with any of the sequence containers: vector, list and deque. This example creates three integer stacks, using each of the sequence containers of the Standard Library as the underlying data structure to represent the stack. By default, a stack is implemented with a deque. The stack operations are push to insert an element at the top of the stack (implemented by calling function push_back of the underlying container), pop to remove the top element of the stack (implemented by calling function pop_back of the underlying container), top to get a reference to the top element of the stack (implemented by calling function back of the underlying container), empty to determine whether the stack is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the stack (implemented by calling function size of the underlying container).

Performance Tip 20.16

Each of the common operations of a stack is implemented as an inline function that calls the appropriate function of the underlying container. This avoids the overhead of a second function call.

Performance Tip 20.17

For the best performance, use class vector as the underlying container for a stack.

Figure 20.23 demonstrates the stack adapter class. Header file <stack> must be included to use class stack.