Previous Table of Contents Next


Because all information is available, the only reason to produce less than optimal code is a poor compiler. In practice, C++ compilers are pretty good at generating code for calls like these. In particular, critical operations such as comparisons are trivially inlined. Where the default operation is unsuitable, the user can supply a suitable one. In the preceding case, I provided an alternative to the default < operator as a third argument. Again, the overload resolution and template instantiation mechanisms resolve the call into close to optimal code.

The STL relies heavily on function objects to provide flexibility and efficiency. For example, consider finding the first element in a list with a value less than some integer i:

   void f(list<int>& m, int i)
   {
       list<int>::iterator p = find_if(m.begin(),m.end(),less_than(i));
       // ...
   }

Note the use of the nested type iterator to ensure that the programmer doesn’t have to know the actual mechanism used to iterate through a list. Every standard container has an iterator type.

How would I define less_than? It cannot be an ordinary function because it needs to be initialized with a value that it later uses to compare against a sequence of values from the list. As used, less_than must be a function that returns an object that can be invoked to do a comparison:

   template<class T> class Less_than {
       T val;
   public:
       Less_than(const T& v) val(v) { }               // store value
       bool operator()(const T& v) { return v<val; }  // compare against
value
   };

    template<class T> Less_than<T> less_than(const T& v)
   {
       return Less_than<T>(v);  // create and return Less_than object for v
   }

This style was inspired by the use of higher-order functions (that is, functions that return functions) in functional programming languages.

Note that the function object Less_than and the function less_than() were defined as templates so that they could be used for a variety of types:

   void g(vector<string>& m, string s)
{
       vector<string>::iterator p = find_if(m.begin(),m.end(),
          less_than(s));
       // ...
   }

The find_if algorithm might be expressed like this:

   template<class Iter, class Pred> Iter find_if(Iter first,
   Iter last, Pred p)
   {
       while (first!=last && !p(*first)) first++;
       return first;
   }

The part of the STL that was accepted into the standard did not include a hash table. This was an obvious disadvantage and several people—notably Javier Barreiro, Robert Fraley, and David R. Musser—promptly proceeded to produce hash tables that fitted into the STL framework. Unfortunately, these implementations and their specifications reached the committee so late in the standards process that they were not accepted into the standard. Instead, these hash table implementations were made publicly available.

The standard library containers store copies of objects given as arguments to insertion functions. That is, the critical requirement on an element type of a standard container is that it can be copied. There is no requirement that an element type has to be derived from a particular class. Thus, the standard library containers are non-intrusive. This is essential to allow standard containers to hold built-in types, such as int and char*, and types that were not defined with the containers in mind, such as types from older code and data structures shared with C programs. For applications where it is essential, a programmer can provide optimized intrusive implementations as specializations. To preserve polymorphic behavior of contained objects, we can insert pointers or handle objects into containers. The standard library provides function objects that allow the standard algorithms to operate on containers of pointers. These member function adapters were my main technical contribution to the STL.

The actual algorithms of the STL were chosen to be a significant subset of the fundamental algorithms described by Knuth (1973). In particular, the STL provided a superset of what AT&T’s Standard Components offered, most of what CLOS offered, and most of what Ada offered in the area of fundamental algorithms.


Previous Table of Contents Next