Previous Table of Contents Next


6.6.3. The Standard Template Library

For about a decade, Alexander Stepanov had been searching for a way to write uncompromisingly generic algorithms. For example, he wanted to write a find()—that is, a linear search—for a given value in a container in such a way that it

  Worked for elements of arbitrary type (such as int, string, and Payroll_record)
  Worked on any type of container (such as built-in array, list, and map)
  Was as efficient as a similar search anyone could write for a value of a specific type on a specific type of container

This work led to libraries written in Scheme, CLOS, and Ada86 (Musser & Stepanov, 1989), which failed to meet the stringent criteria set by Stepanov and his collaborators (notably David Musser from Rensselaer Institute of Technology). During a dinner with Andrew Koenig and Barbara Moo in August 1993, Stepanov explained that he had completed a C++ library that met his criteria. Koenig took an interest in that library—ambitiously called the STL (the Standard Template Library)—and managed to get me interested also.

To my surprise, the STL met almost all the criteria for a set of containers suitable for a standard that I had formulated over the years. Years earlier, Stepanov had in AT&T Bell Labs worked on the Standard Components Library and had taken part in some of the early discussion about the design of templates. However, I had lost contact with him, and the STL went beyond any library that I had seen for C++ (Stepanov & Lee, 1994). In style and contents, it differed from existing C++ libraries. In fact, its style was closer to what you see in functional programming languages than to any of the commonly used C++ foundation libraries.

After some thought, Koenig invited Stepanov to give a technical presentation of the STL at a C++ standards meeting in November 1993. This presentation led to some enthusiasm, some thoughts about how the STL vectors, sets, maps, and so on might serve as standard containers for C++, and eventually to a detailed proposal to make a set of templates closely resembling part of the STL part of the C++ standard library. An initial outline of this proposal was worked out at a meeting of committee members (Tom Keffer, Nathan Meyer, Larry Podmolik, Mike Vilot, Richard Wilhelm, and me) hosted by Stepanov at HP in spring 1994 and completed by Stepanov and his coworker at HP, Meng Lee. This proposal, strongly supported by Koenig and me, was accepted by the standards committee in July 1994.

In The C++ Programming Language, Third Edition (Stroustrup, 1997), I summarized the criteria for a standard library facility like this:

The facilities offered by the C++ standard library are designed to be

  Invaluable and affordable to essentially every student and professional programmer, including the builders of other libraries.
  Used directly or indirectly by every programmer for everything within the scope of the library.
  Efficient enough to provide genuine alternatives to hand-coded functions, classes, and templates in the implementation of further libraries.
  Either policy free or giving the user the option to supply policies as arguments.
  Primitive in the mathematical sense. That is, a component that serves two weakly related roles will almost certainly suffer overhead compared to individual components designed to perform only a single role.
  Convenient, efficient, and reasonably safe for common uses.
  Complete at what they do. The standard library may leave major functions to other libraries, but if it takes on a task, it must provide enough functionality so that individual users or implementors need not replace it to get the basic job done.
  Able to blend well with and augment built-in types and operations.
  Type safe by default.
  Supportive of commonly accepted programming styles.
  Extensible to deal with user-defined types in ways similar to the way built-in types and standard-library types are handled.

For example, building the comparison criteria into a sort function is unacceptable because the same data can be sorted according to different criteria. This is why the C standard library qsort() takes a comparison function as an argument rather than rely on something fixed, say, the < operator. On the other hand, the overhead imposed by a function call for each comparison compromises qsort() as a building block for further library building. For almost every data type, it is easy to do a comparison without imposing the overhead of a function call.

The STL manages to meet most of these criteria by formalizing the notion of a sequence of elements, by providing containers that support that notion, and by having functions operate on sequences through an abstraction of a pointer to an element of a sequence (called an iterator). In addition to offering the most common types of containers (such as list, vector, set, and map), the STL provides the most common algorithms on containers (such as find, sort, and merge).

From a language point of view, the key to the STL is the use of overload resolution to determine what template specializations are to be generated for a specific call:

   template<class Iterator> void sort(Iterator,Iterator);
   template<class Iterator, class Cmp> void sort(Iterator,Iterator,Cmp);

   void f(vector<int>&vi, list<string>&lst)
   {
       sort(vi.begin(),vi.end());
       sort(lst.begin(),lst.end());
       sort(lst.begin(),lst.end(),my_string_compare);
   }

Here, vi.begin() and vi.end() produce iterators for the beginning and the end of the vector<int> called vi. Then a version of the generic sort() is called for two iterators pointing to ints in a vector. Similarly, lst.begin() and lst.end() produce iterators for the beginning and the end of the list<string> called lst. Then a version of the generic sort() is called for two iterators pointing to strings in a list.


Previous Table of Contents Next