Previous | Table of Contents | Next |
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 searchfor a given value in a container in such a way that it
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 libraryambitiously 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
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 |