In programming, we use the term algorithm a bit more loosely. We take it to mean any function (in the C/C++ sense) that computes a useful result. A good algorithm does the job with an economy of operations, and with predictable time complexity. It is chary of special cases, like zero repetition counts, and it avoids gratuitous intermediate overflows and other computing anomalies. It is cohesive, presenting a narrow and sensible interface to the outside world.

A well coded algorithm is thus an important asset to the working programmer. We use them all the time, in the guise of the Standard C library. All those math functions, string manipulators, and I/O facilities capture any number of algorithms in code that have proved to be remarkably reusable over the years.

In the case of a function library, the choice of data types is critical to reusability. A square root function is much more widely usable if it takes a double argument than if it takes an int. A sequence of char makes a more widely usable string or file than, say, a string of long elements. Imagine how much more useful all these functions could be, however, if you had some say in what data type should be used.

That's where templates come in. Within some limits, you can specialize (or instantiate) a template function or class for one or more specific types, and the translator fills in the blanks for you. Those limits are dictated by any assumptions made, within the template, about what you can do with the parameter type. If the template wants to add one to an object of the parameter type, then the type you choose had better define what it means to add one to an object of that type.

A significant achievement of STL is that it provides quite a number of useful algorithms. It does so in a helpful framework — the types you can substitute for its parameters fall into a handful of categories. Each of these categories is pretty clearly spelled out, and the template definitions are robustly written. Thus, there's a high probability you will guess right about what types you can use with a given algorithm, and there's an equally high probability that the code will do the right thing.

STL offers around 100 template functions that implement algorithms. On the simple end are templates like for_each, which calls the function you specify for each element of a sequence. On the complex end you will find things like stable_sort, which sorts in place a sequence using an ordering rule you specify, preserving the order of elemnts that compare equal.

As you become familiar with STL, you find that more and more of the "interesting" code you used to write can now be written in just a few lines. Invoking an algorithm template or two does all the hard stuff. And it does the job better than you are likely to do.

I long ago observed an interesting parallel in physics. Some computations are notoriously complex, particularly those that require matching up two solutions at a boundary. One approach to solving such problems is to change coordinate systems. Move to a system where the boundary looks simple and the equations are easy to solve. Of course, changing back and forth between coordinate systems may be messy in its own right. The advantage is that someone has probably solved that problem for you, so you can just recycle a known technique.

We in computing have repeatedly rediscovered a handful of useful ways to organize collections of data. Think of them as the moral equivalent of coordinate systems, for the analogy above. An array is good for quick random access, but it doesn't grow easily, and insertions are a real nuisance. A linked list makes light work of additions and insertions, at the cost of linear access instead of random. And so on.

The sad thing is that we've all reimplemented vectors, lists, and other common data structures repeatedly over the years. The code in each case is highly similar, but it has to change in small ways to accommodate variations in the data being managed. Wouldn't it be nice if someone could implement a linked list once and for all in such a way that we'd all be happy to recycle that implementation?

That's where STL's containers come in. These are template classes that support the half dozen or so commonest ways to organize data. The template parameter lets you specify the type of data in each element. All that code for growing, shrinking, inserting, and visiting all the elements is provided once and for all by the containers themselves.

Once again, you slowly learn that much of the code you tend to write for a new program is just bookkeeping for a common data organization. An STL container or two can save some tedious effort.

for (sum = 0; first != last; ++first)
   sum += *first;

• comparison for (in)equality (first != last)
• dereferencing to access a value (*first)
• (pre)incrementing (++first)

Add a few lines to the example above and you can make a template function that sums the values in a sequence. Add a few more requirements to those listed immediately above and you have the specifications for a typical iterator.

Nearly all of the algorithms that STL provides work on sequences accessed via iterators. A handful of categories describes the various iterators around which the algorithm functions are defined. This is the organizing principle that gives STL much of its strength and flexibility.

Each STL container defines the iterators needed to access its elements. You can, of course, also supply your own iterators for your own data structures as well. Most important of all, ordinary pointers almost always work just fine as iterators. You don't have to define a bunch of fancy classes if you don't want to. And yet you can still easily extend the set of algorithms and containers that work within the STL framework.

"Copyright (C) 1994, Hewlett-Packard Company. Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Hewlett-Packard Company makes no representations about the suitability of this software for any purpose. It is provided 'as is' without express or implied warranty."

Hewlett-Packard

What the validation suites do is keep the library vendors honest. Maybe your code that uses STL won't have to change much with the emerging standard, but those implementations sure have to. Once the flurry of debugging settles down, you can expect more uniformity among commercial offerings that include the new Standard C++ library.