24.9 Summary

I l @ ve RuBoard

24.9 Summary

Templates provide a convenient way of writing generic classes and functions. Many compiler makers have not completely implemented this feature, however. As a result, you'll probably have to play with the compilation switches and some #pragma directives to get things to work.

When you do get templates working, the result can be some very powerful code. An example of this is the Standard Template Library (see Chapter 25).

I l @ ve RuBoard

24.10 Programming Exercises

Exercise 24-1: Write a template min that returns the minimum of two values. Make sure you handle C-style strings correctly.

Exercise 24-2: Write a template class to implement an array with bounds checking.

Exercise 24-3: Define a template class that implements a set. The class allows you to set, clear, and test elements. (An integer version of this class was presented in Exercise 13-4.)

I l @ ve RuBoard

Chapter 25. Standard Template Library

Goodness and evil never share the same road, just as ice and charcoal never share the same container.

”Chinese proverb

As people began to develop code, they noticed that they were coding the same things over and over again. For example, in every large C program, you'll probably find an implementation of a linked list. Since it's better to reuse than to rewrite, the designers of C++ have added a library of common containers (lists, arrays, and others) to the language. This library is known as the Standard Template Library or STL.

These containers are designed as templates so that they can hold almost anything. The library provides not only the containers but also iterators that make access to the contents of a container easier.

Finally, there are the algorithms that perform common functions on a container, such as sorting, merging two containers, locating elements, and other such functions.

I l @ ve RuBoard

25.1 STL Basics

In this section we take a look at the basic concepts that went into the design of the STL and how all these design elements come together to provide a very robust and flexible way of handling items.

25.1.1 Containers

The core of the STL is the container. We're already familiar with a couple of STL container types, the vector (a single-dimension array) and the stack.

The STL divides containers into sequences, which store their elements in order, and associative containers, in which elements are accessed using a key value.

The basic STL containers are:

vector: A random-access sequential container. This looks pretty much like a C++ array, but you can expand it by inserting elements into it. You can also delete elements from a vector.
deque: Similar to a vector, but it's faster at inserting and deleting elements in the middle of the container.
list: A doubly linked list. Does not allow for random access.
set: A set of items. Items in the set are unordered and unique.
multiset: A set that permits multiple items with the same value to be stored in it.
map: Also known as associative array. This is a container whose values can be looked up by a key. Because this is a template, the key and value can be almost anything. Only one value is stored for each key.
multimap: A map that allows multiple values to be stored for each key.

These containers give you a way of storing most data in almost any way you want to. Now that we've got our data stored, we need access to it.

25.1.2 Iterators

Iterators allow you to go through a container and access the data inside. One form of this is the forward iterator, which allows you to access each element from first to last. There is a reverse iterator that allows you to go the other way and a bidirectional iterator, which goes both ways. Finally, there is the random access iterator, which allows you to access any element randomly .

Not all containers support all iterator types. For example, the vector supports random access iterators, while the list container does not.

We'll see how to use iterators in the class program described later in this chapter.

25.1.3 Algorithms

We have containers to hold the data and iterators so we can access it. For example, the sort algorithm can be used to sort an ordered container such as a vector. Some of the other algorithms include:

find: Finds an item in a container
count: Counts the number of items in a container
equal: Tests to see if containers are equal
for_each: Runs each element of a container through a given function
copy: Copies a container
reverse: Reverses the elements of an ordered container

These three elements ”containers, iterators, and algorithms ”make up the STL. Now that we know the basics, let's see how to use this library in the real world.

I l @ ve RuBoard