Chapter 19 Standard Template Library

Instructor’s Resource Manual for Savitch Absolute C++ 04/12/02 Page 13

Chapter 19 CHAPTER Standard Template Library

Chapter 19

Standard Template Library

0. Introduction

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

A container is an object that holds other objects. We have seen linked list classes, the primitive array and the STL vector that can contain other objects.

An iterator is an object used to specify a position in a container. All iterators can be incremented to move the position towards the end by one or dereferenced to fetch the value in the container to which the iterator refers. Thus iterators allow traversal of a container without compromising the internal structure of the container.

A generic algorithm, or just algorithm, is a template function that uses iterator types for its parameter types. Generic algorithms are used to manipulate the contents of a container for which an iterator type with sufficient strength is available.

A function object is a class that overloads the function call operator, operator() so that an object of this class can be used like a function and can be passed as a template parameter.

An allocator makes room in memory for STL components. Each container is given a memory allocator that the container's constructor uses as it needs memory. Allocators are required in environments with multiple memory models. Typically, 16 bit PC applications require allocators beyond the defaults provided in the STL. Except for embedded applications, these are apparently obsolete. Our purposes are well served by the default allocators, and allocators are beyond the scope of the text and this document, we will not discuss allocators. See the book by Josuttis in the text's references.

1. Outline of topics in the chapter

19.1 Iterators

Iterator Basics

Kinds of Iterators

Constant and Mutable Iterators

Reverse Iterators

Pitfall: Compiler Problems

Other kinds of Iterators

19.2 Containers

Sequential Containers

Pitfall: Iterators and Removing Elements

Tip: Type Definitions in Containers

The Container Adapters stack and queue

The Associative Containers set and map

Efficiency

19.3 Generic Algorithms

Running Times and Big-O Notation

Container Acce3ss Running Times

Nonmodifying Sequence Algorithms

Modifying Sequence Algorithms

Set Algorithms

Sorting Algorithms

2. General remarks on the chapter

19.1 Iterators

Iterator Basics

In many data structures and in containers, we need some idea of position or location of an item in the structure. In C, and in C++ before the Standard Template Library (STL), the pointer met this need. Pointers have the advantage of speed but are dangerous. The STL provides the iterator as a replacement for pointers that is as efficient as a pointer but is much safer.

The iterator is an object used to specify a position in a container and is a generalization of the notion of pointer. The syntax for manipulating an iterator is a subset of the syntax of pointers. To access an item referred to by an iterator iter, one writes *iter. Such an access can be used to fetch the value of the element (used as an r-value) or to assign this value (used as an l-value). To step the iterator forward to refer to the next item in the container, one writes iter++. Thus iterators allow traversal of a container without compromising the internal structure of the container.

Each STL container defines one or more iterator types, specified by syntax such as vector<int>::iterator. The specific operations and properties of the iterator defined by a container depend heavily on what can be efficiently implemented given internal the structure of the container. The inner workings of the iterator, such as the detail of advancing the position in the container are also specific to the container being used and are hidden from the user.

In addition to overloading the dereferencing operator (*), the following operators are overloaded for some classes of iterators. prefix and postfix forms of the ++ and -- operator, equal and unequal operators (== and !=). Each of the STL containers provides functions that return the first and last elements in the container. If c is a container, then

c.front() returns the first element in the container.

c.back() returns the last element in the container.

There are also member functions that return iterators that refer to special places in the container.

c.begin() returns an iterator that refers to the first data item in the container.

c.end() returns an iterator that refers to a position beyond the end of the container.

Do not to confuse the past-end iterator value and the null pointer value. That there is an essential difference between these ideas can be seen from the following scenario.

Suppose you have an iterator of a type that supports the decrement operator, --, and suppose the iterator has the past-end value for a container that is not empty. You can decrement the iterator with the result being an iterator that refers to the same element that that c.back()returns. You cannot decrement or increment the null pointer to obtain anything useful. There is a programming analogy, but you should take care not to confuse these ideas.

In the next section we see that the STL classifies iterators according to the features available to the iterator.

Kinds of Iterators

Different STL containers have different properties, so iterators for the various containers also have different properties. Similarly, different STL algorithms require different properties of the iterators they use. For example, sorting a container requires random access; otherwise, performance suffers. Consequently, iterators are classified in increasing "strength" of properties as input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators. The following figure displays the relationships among the iterator categories. We will see later that if an STL algorithm requires an iterator of a particular category, then the programmer can use an iterator of that category or of any stronger category, but not of a weaker category.

Some additional types of iterators are reverse iterators, stream iterators, insertion iterators, and raw storage iterators. Reverse iterators allow iteration through containers from the back to the front. Stream iterators allow you to read and write files from STL algorithms. Insertion iterators allow adding new items to the container rather than overwriting the position referred to by the iterator.

To say random access means that all accesses take the same time, that is the runtime for accesses are O(1). Random access iterators provide random access (in this sense) to the elements in the container that defines the iterator type. In the STL, random access iterators provide indexing and the mixed iterator expression of adding an integer constant, n, to an iterator, iter . The expression , n + iter, yields an iterator value that refers to the element n elements away from the element referred to by iter, in a direction that depends on the sign of n, provided there is an element at that position.

Input Iterators

Input iterators can only be stepped forward by one item per step. Furthermore, they may be dereferenced only to fetch (but not store into) an item from a collection. The following table displays the allowable operations on an input iterator.

Input Iterator Operations

Output Iterators

As with input iterators, output iterators can only be stepped forward by one item per step. However, output iterators may be dereferenced only to store a value at (but not fetch a value from) the specified location. The next table shows the allowable operations on an output iterator.

Output Iterator Operations

At first, it might seem strange that we can modify something but not fetch it, but it begins to make more sense once you know that output iterators are most often used for sending data to an output stream such as cout. (The iostream header file provides output stream iterators.) The idea is to treat an output stream as a "container" of characters and, using an output iterator, write each new character to the stream, one by one. We will not discuss stream iterators further.

Forward Iterators

We have looked at two categories of iterators that step forward through a container, one permitting only fetching, the other permitting only storing. Often we would like to both fetch and store a value at a particular position as we step through a container. Forward iterators allow us to do so. Specifically, the valid operations on a forward iterator are the same as those of an input iterator plus the ability to store into the referenced item (see the next table).

Forward Iterator Operations

Bidirectional Iterators

Bidirectional iterators have all the properties of forward iterators but allow backward movement through a container as well as forward.

Bidirectional Iterator Operations

Adding the decrement operator makes some algorithms easier to implement. We will see that all the (Standard) STL containers support either bidirectional iterators or random access iterators. The list container provides bidirectional iterators. (Hence, some people like to think of list as an abstraction of a doubly linked list because it allows efficient traversal in either direction. Actually, the STL list is more than just an abstraction of a doubly linked list because the STL list is almost always implemented as a doubly linked list.)

Random Access Iterators

Random access iterators have all the properties of bidirectional iterators but support additional operations to allow random (direct) access to any item in a container.

Random Access Iterator Operations

The vector container provides random access iterators, which makes sense because vector is an abstraction of a one-dimensional array.

Constant and Mutable Iterators

The STL containers provide constant iterators. The available iterator types are defined in the container class.

vector<char>::const_iterator constP =container.begin();

You cannot modify the elements in container using the constant iterator constP. This does not make the location itself constant. If I define

vector<char>::iterator p = container.begin();

While we cannot change the front element from the container through dereferenced constP, we can change the front element of container by assigning dereferenced p.

Here is a code fragment illustrating this.

*constP = value; // illegal

*p = value; // OK

This should not be surprising, since this is true of memory locations referred to by const references and const pointers as well.