Previous Section
 < Free Open Study > 
Next Section


Appendix E: The Standard Template Library

Overview

The Standard Template Library (STL) is a subset of the ISO/ANSI C++ standard library. The STL provides three kinds of facilities for C++ programmers to use: containers, iterators, and generic algorithms.

An STL container holds other objects, much like the containers you have studied in this text: lists, stacks, queues, and so on. Specifically, the STL supplies many useful container classes, some of which are the following:

list

A sequential-access list that can be traversed both forwards and backwards.

vector

An abstraction of a one-dimensional array providing, as expected, random access to the array elements.

stack

A stack, with the usual LIFO access.

queue

A queue, with the usual FIFO access.

deque

A double-ended queue (insertions and deletions can occur at both ends) with the uncommon additional property of random access.

set

An abstraction of a mathematical set.

The container classes are template classes so that, for example, we declare objects of type list<int>, stack<float>, and so forth.

To introduce the concepts of STL iterator and STL algorithm, we begin with the following code segment, which inputs several integer values and outputs them in reverse order. The lines of code are numbered so that we can refer to them in the discussion that follows the code segment.

1  #include <iostream>
2  #include <list>          // For list<T> class
3  #include <algorithm>     // For reverse() function
     
4  using namespace std;

5  list<int> nums;
6  list<int>::iterator iter;
7  int number;

8  cin >> number;
9  while (number != -9999)
10 {
11   nums.push_back(number);
12   cin >> number;
13 }
14 for (iter = nums.begin(); iter != nums.end(); iter++)
15   cout << *iter << end1;
16 reverse(nums.begin(), nums.end());

17 for (iter = nums.begin(); iter != nums.end(); iter++)
18   cout << *iter  << end1;

In this code, lines 2 and 3 cause insertion of the header files list and algorithm, allowing us to use the template class list and the function named reverse. Line 5 creates a list named nums whose components are of type int. The list is initially empty. Line 6 declares iter to be of type list<int>::iterator, a data type defined inside the list<int>class. We discuss its usage in a moment.

Lines 8 through 13 read integer values from the standard input device and insert them into the list. The push_back function, a member of the list class, takes the value in its argument list and appends it to the back (rear) of the list. (Note that the verb push, traditionally used only for insertion into a stack, is used throughout the STL container classes to mean insert.) The loop continues until the sentinel (trailer) value -9999 is read, after which the nums list contains the input values in the order in which they were read.

Next, the loop in lines 14 and 15 traverses the nums list from front to back, printing each list item in turn. The variable iter, which was declared in line 6, is an STL iterator. In one sense, an STL iterator is similar to the iterator concept you have studied in this text (a class member function named something like GetNext). Both STL iterators and GetNext operations enable cycling through a container, one item at a time. On the other hand, an STL iterator is a lower-level concept than a GetNext operation: It simply represents the location of an item within a container. Thus, an STL iterator is a generalization of the notion of a pointer. Iterators allow C++ programs to access a container's stored items without having to know the internal structure of the container. The syntax for manipulating an iterator is very nearly the same as for a pointer. To access an item referred to by an iterator iter, one writes *iter. To step the iterator forward to refer to the next item in the container, one writes iter++. The inner workings of the iterator, such as the detail of advancing the position in the container, are hidden from the user and are specific to the container being used. Each STL container class defines one or more iterator types, such as list<int>::iterator. An iterator may be implemented as an ordinary pointer or a class object, depending on the particular container.

Now, back to lines 14 and 15. In line 14, the variable iter is initialized to the value returned by the function call nums.begin(). The function named begin, a member of the list class, returns the location of the first item in the list. (In the C++ literature-and even in places within this appendix-the phrase "returns an iterator to the first item" is used. What is really meant is "returns the location of." You can even say "returns a pointer to" or "returns the address of," although there is no guarantee that a particular iterator is implemented as a C++ pointer variable.) In the heading of the for statement of line 14, the loop condition is iter ! = nums.end(). The function named end, a member of the list class, returns the location of an imaginary list item that is just beyond the last actual list item. (This position is often called the past-the-end position.) The third piece of the for statement heading, which is iter++, says to advance the iterator to point to the next list item. Therefore, each time through the loop, we obtain the location of the next list item, and we keep looping until we've gone past the end of the list. In each loop iteration, we perform the loop body seen in line 15: We output the value referred to (or "pointed to") by the iterator iter. Note that the output statement uses the expression *iter, not iter. That is, we want to print the list item, not its location.

Next, look at line 16 of the program. The reverse function, available through the header file algorithm, takes as arguments two iterators-a beginning and an ending position in a container-and puts into reverse order all the items from the beginning position up to, but not including, the ending position. So in line 16, all of the items in the nums list are processed because the second argument, nums.end(), specifies the past-the-end position. Finally, lines 17 and 18 traverse the nums list, printing out the new contents of the list.

The reverse function is an example of an STL algorithm. In computer science terminology, an algorithm is an abstract procedural concept, a recipe for solving a problem. An algorithm implemented in a programming language is a program. Every program implements one or more algorithms. In contrast, the STL defines the term algorithm in a much narrower sense. An STL algorithm (or simply an algorithm) is a template function that has iterators for its parameter types. The description of each algorithm specifies the kinds of iterators it requires as its parameters. Later in the appendix, we describe a variety of algorithms supplied by the STL.

Let's look at another example of an STL container class: vector. A vector object is an abstraction of a one-dimensional array and can be used in the same manner as a built-in array:

    #include <vector>         // For vector<T> class
      
    vector<float> arr(100);   // A 100-element array
      
    arr[24] = 9.86;           // Random access is allowed through
    arr[i+j] = arr[k];        // a subscript (index) expression

However, the vector class is far more versatile than a built-in array. A major limitation of built-in arrays is that the array size is fixed at compile time and cannot grow or shrink while the program is running. In contrast, the size of a vector can vary at run time. Suppose we want to input an unknown number of integer values at run time and store them into an array. With a built-in array, we have to estimate its size in advance, and our estimate may be too large (a waste of memory) or too small (our program is in trouble). With a vector, we don't need to specify its size and can let it grow as needed:

    vector<int> vec;                     // Initial size is 0
    int inputVal;

    cin >> inputVal;
    while (cin)                          // Assume 50 numbers are
    {                                    // input before EOF occurs
      vec.push_back(inputVal);
      cin >> inputVal;
    }
    cout << vec.size() << end1;          // Outputs 50

    for (int i = 0; i < vec.size(); i++) // We can still use
      cout << vec[i] << end1;            // indexing

In the preceding code, the size of the vec object keeps increasing as needed, with memory implicitly being allocated dynamically. Notice also in the code that push_back is a member of the vector<int> class as well as the list<int> class. In fact, many of the STL container classes have member functions with the same name (for example, push_back) and the same semantics. Because of this uniformity, it is incredibly easy to reuse code from one context in another context. For example, how might we input several integer values into a vector and then output them in reverse order? The answer: Go back to our first code example with lines numbered 1 through 18 and change only lines 2, 5, and 6:

    2  #include <vector>       // For vector<T> class
    5  vector<int> nums;
    6  vector<int>::iterator iter;

All of the other lines in the program remain absolutely identical because

The first time you study the STL in depth, it will likely be hard to know where to start. In the STL, containers form the heart of the library, but it is difficult to understand containers without some knowledge of the STL algorithms and the iterator requirements, and vice versa. In the STL, algorithms extend the functionality of the containers, and the iterators enable containers and algorithms to work together. In fact, if the user wishes to build his or her own container with iterators or create algorithms that meet the STL requirements, these structures will interact correctly with the STL components.

A problem some have when first learning the STL is that some of the terminology used there (such as iterator and algorithm) is different from common usage in computer science. As in every new subject in computer science, the new vocabulary must be learned. The STL is well worth learning, for it is a fast, flexible, and useful library.

The ISO/ANSI C++ Standard requires that the full Standard Template Library be provided by every compliant compiler. The STL components are nicely designed to work together well. They are as fast as anything a journeyman programmer can create in the time it takes to learn to use the library.

We should point out that in the design of the STL, the Standards committee made a deliberate decision to provide speed rather than safety, so most STL components do not throw exceptions. Most STL member functions either succeed or do nothing. We do not provide further discussion of exceptions in the STL containers and algorithms except for the at () member function supported by the random access containers. We refer you to the 1998 ISO/ANSI C++ Standard 14882 and to Josuttis's The C++ Standard Library for further discussion of this topic. (See the references at the end of this appendix.)

We now examine in more detail the STL components in the following order: iterators, containers, and algorithms.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)