Introduction to the Standard Template Library (STL)

We have 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 templatesintroduced in Chapter 14, Templates, and demonstrated in detail in Chapter 21, Data Structures. [Note: In industry, the features presented in this chapter are commonly 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 will see, the STL was conceived and designed for performance and flexibility.

This chapter introduces the STL and discusses its three key componentscontainers (popular templatized data structures), iterators and algorithms. The STL containers are data structures capable of storing objects of any data type. We will see that there are three container categoriesfirst-class containers, adapters and near containers.

Performance Tip 23.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 STL's design.

Performance Tip 23.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 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 as STL containers, using standard pointers as iterators. We will see that manipulating containers with iterators is convenient and provides tremendous expressive power when combined with STL algorithmsin some cases, reducing many lines of code to a single statement. There are five categories of iterators, each of which we discuss in Section 23.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). Approximately 70 algorithms are implemented in the STL. 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 will 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 23.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.

In Chapter 21, we studied data structures. We built linked lists, queues, stacks and trees. We carefully wove link 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 23.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 23.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.

23.1.1. Introduction to Containers

The STL container types are shown in Fig. 23.1. The containers are divided into three major categoriessequence containers, associative containers and container adapters.

---

Figure 23.1. Standard Library container classes.

Standard Library container class	Description
Sequence containers
vector	rapid insertions and deletions at back direct access to any element
deque	rapid insertions and deletions at front or back direct access to any element
list	doubly linked list, rapid insertion and deletion anywhere
Associative containers
set	rapid lookup, no duplicates allowed
multiset	rapid lookup, duplicates allowed
map	one-to-one mapping, no duplicates allowed, rapid key-based lookup
multimap	one-to-many mapping, duplicates allowed, rapid key-based lookup
Container adapters
stack	last-in, first-out (LIFO)
queue	first-in, first-out (FIFO)
priority_queue	highest-priority element is always the first element out

 

STL Containers Overview

The sequence containers (also referred to as sequential 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. As we saw in Chapter 21, 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 four other container types that are considered "near-containers"C-like pointer-based arrays (discussed in Chapter 7), strings (discussed in Chapter 18), 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 four 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.

STL Container Common Functions

All 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 23.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.]

---

Figure 23.2. STL container common functions.

Common member functions for all STL containers	Description
default constructor	A constructor to provide a default initialization of the container. Nor-mally, each container has several constructors that provide different initialization methods for the container.
copy constructor	A constructor that initializes the container to be a copy of an existing container of the same type.
destructor	Destructor function for cleanup after a container is no longer needed.
empty	Returns true if there are no elements in the container; otherwise, returns false.
size	Returns the number of elements currently in the container.
operator=	Assigns one container to another.
operator<	Returns true if the first container is less than the second container; otherwise, returns false.
operator<=	Returns TRue if the first container is less than or equal to the second container; otherwise, returns false.
operator>	Returns true if the first container is greater than the second con-tainer; otherwise, returns false.
operator>=	Returns true if the first container is greater than or equal to the sec-ond container; otherwise, returns false.
operator==	Returns true if the first container is equal to the second container; otherwise, returns false.
operator!=	Returns TRue if the first container is not equal to the second con-tainer; otherwise, returns false.
swap	Swaps the elements of two containers.
Functions found only in first-class containers
max_size	Returns the maximum number of elements for a container.
begin	The two versions of this function return either an iterator or a const_iterator that refers to the first element of the container.
end	The two versions of this function return either an iterator or a const_iterator that refers to the next position after the end of the container.
rbegin	The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container.
rend	The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the next position after the last element of the reversed container.
erase	Erases one or more elements from the container.
clear	Erases all elements from the container.

---

STL Container Header Files

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

[1] Some older C++ compilers do not support the new-style header files. Many of these compilers provide their own versions of the header-file names. See your compiler documentation for more information on the STL support your compiler provides.

Figure 23.3. Standard Library container header files.

Standard Library container header files
	Contains both queue and priority_queue.
	Contains both map and multimap.
	Contains both set and multiset.

 

First-Class Container Common typedefs

Figure 23.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.

Figure 23.4. typedefs found in first-class containers.

---

typedef	Description
value_type	The type of element stored in the container.
reference	A reference to the type of element stored in the container.
const_reference	A constant reference to the type of element stored in the container. Such a reference can be used only for reading elements in the container and for performing const operations.
pointer	A pointer to the type of element stored in the container.
iterator	An iterator that points to the type of element stored in the container.
const_iterator	A constant iterator that points to the type of element stored in the container and can be used only to read elements.
reverse_iterator	A reverse iterator that points to the type of element stored in the container. This type of iterator is for iterating through a container in reverse.
const_reverse_iterator	A constant reverse iterator that points to the type of element stored in the container and can be used only to read elements. This type of iterator is for iterating through a container in reverse.
difference_type	The type of the result of subtracting two iterators that refer to the same container (operator - is not defined for iterators of lists and associative containers).
size_type	The type used to count items in a container and index through a sequence container (cannot index through a list).

---

Performance Tip 23.3

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

Portability Tip 23.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 23.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.

 

23.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 will 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 can be used only 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. 23.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.[2]

[2] The examples in this chapter precede each use of an STL function and each definition of an STL container object with the "std::" prefix rather than placing the using declarations or directives at the beginning of the program, as was shown in most prior examples. Differences in compilers and the complex code generated when using STL make it difficult to construct a proper set of using declarations or directives that enable the programs to compile without errors. To allow these programs to compile on the widest variety of platforms, we chose the "std::" prefix approach.

Figure 23.5. Input and output stream iterators.

(This item is displayed on page 1119 in the print version)

 1 // Fig. 23.5: Fig23_05.cpp
 2 // Demonstrating input and output with iterators.
 3 #include 
 4 using std::cout;
 5 using std::cin;
 6 using std::endl;
 7
 8 #include  // 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 23.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 23.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 23.2

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

 

Iterator Categories and Iterator Category Hierarchy

Figure 23.6 shows the categories of iterators used by the STL. Each category provides a specific set of functionality. Figure 23.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.

Figure 23.6. Iterator categories.

(This item is displayed on page 1120 in the print version)

Category	Description
input	Used to read an element from a container. An input iterator can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms-the same input iterator cannot be used to pass through a sequence twice.
output	Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms-the same output iterator cannot be used to pass through a sequence twice.
forward	Combines the capabilities of input and output iterators and retains their position in the container (as state information).
bidirectional	Combines the capabilities of a forward iterator with the ability to move in the backward direction (i.e., from the end of the container toward the beginning). Bidirectional iterators support multipass algorithms.
random access	Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i.e., to jump forward or backward by an arbitrary number of elements.

Figure 23.7. Iterator category hierarchy.

(This item is displayed on page 1120 in the print version)

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 will see, pointers into arrays can be used in place of iterators in most STL algorithms, including those that require random-access iterators. Figure 23.8 shows the iterator category of each of the STL containers. Note that only vectors, deques, lists, sets, multisets, maps and multimaps (i.e., the first-class containers) are traversable with iterators.

---

Figure 23.8. Iterator types supported by each Standard Library container.

(This item is displayed on page 1121 in the print version)

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

---

Figure 23.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 23.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 23.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.

---

Figure 23.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	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[ 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.

 

23.1.3. Introduction to Algorithms

The STL provides algorithms that can be used generically across a variety of containers. STL provides many algorithms you will 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 iteratorsa 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 reuseusing 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 23.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 23.6

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

Software Engineering Observation 23.7

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

Portability Tip 23.2

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

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

Figure 23.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 23.12 shows many of the nonmodifying sequence algorithmsi.e., the algorithms that do not result in modifications of the containers to which they are applied. Figure 23.13 shows the numerical algorithms of the header file .

Figure 23.12. Nonmutating 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

Figure 23.13. Numerical algorithms from header file .

Numerical algorithms from header file
accumulate	partial_sum
inner_product	adjacent_difference