Are You Afraid of The Dark? - Making Sense of the STL

Do you peer in trepidation at the monsters lurking in the C++ Standard header files when you see code using Standard Template Library techniques? Or walk swiftly by, trying to ignore them? Do you sometimes wish you had a good, sturdy torch to have a good look, when your trusty old pen-light won't do? OK, well, join us for a while. Some of you may have taken Alan Griffiths' tour of the "Heights of Exception Safety" [Griffiths2000] in the mountains above us, and some of you may be on your first visit to this region, so welcome! These caverns are often dark and mysterious to new visitors, and the lighting conditions are often poor, but we've got good, strong torches for you. Don't be afraid of the dark, because you'll find it's not really that dark, and once you've passed this way once, your footing will be more confident and secure when you visit again, and I hope many of you first-timers will come by more often.

There are several caverns that we'll see on our trip, and on this first visit we'll be looking at some of the main features exhibited, rather than a detailed examination of them. We won't get to look at some of the harder to reach caves, which are perhaps best left to experts. For today, our itinerary will encompass just the main features: Containers and Iterators, Functors, and Algorithms.

All substantial programs require collections of things; a list of employees, a stack of windows; a set of indices. These collections are handled by container classes, that is, classes that manage collections of other objects, and provide different methods of accessing those objects.

The C++ Standard Library [ISO1998] provides seven main container classes, each with different characteristics. They are broadly divided into two sections: sequences and associative containers [Austern1998]

First of all, let's examine the characteristics that all of the containers have in common. The first and most important aspect is that they all own their objects. When you add an element to a container, it is copied directly, so that you now have two such objects - the original and the contained one. This is very important for two reasons: firstly, you can safely get rid of the original, or over-write it, without affecting the contained version; second, the container automatically deletes its contained elements when the container itself is deleted or goes out of scope. This imposes some restrictions on how elements behave, and some containers impose more restrictions than others.

Related to this is the fact that all the containers are able to grow dynamically in memory as more space is required. Each of the sequence containers does this differently in ways which are important to understand.

All containers rely on their elements being copy-constructible (having a valid and visible copy constructor), because the containers manage value objects. They expect that when an object is copied, a second instance of that object is made, rather than a reference to some original object. This concept becomes harder to manage when you consider containers of pointers, but we will not explore that path at the moment.

The other main aspect that all container classes have in common is iterators. These are a mechanism whereby the navigation of the elements in a container is separate from the container itself. The important thing to all this is that iterators from any of the containers look the same when used for simple operations like getting to an element's value. We won't get very far without encountering iterators in this trip, as you'll see.

We don't have time to examine the associative containers here, because a cursory overview would be more cryptic than helpful. Let's go right ahead and look at the sequence containers.

Each of the three sequence containers has different properties and idiosyncrasies. As their name suggests, they handle elements as a simple, linear sequence, with a start position and an end position. These elements are not sorted by their respective values, and in fact, sorting the elements is generally "expensive" in terms of code efficiency. Notwithstanding this, it is possible to sort a sequence container.

list< string > names;
string name;
while( cin >> name && name != "done" )
{
  names.push_back( name );
}
list< string >::iterator i; 
for( i = names.begin(); 
      i != names.end(); ++i )
{
  cout << *i << "\n";
}
// do something with i

list< string > names;

typedef list< string >::iterator output;

vector< string > names;
string name;
while( cin >> name && name != "done" )
{
  names.push_back( name );
}
vector< string >::iterator i;
for( i = names.begin(); i != names.end(); ++i )
{
  cout << *i << "\n";
}
// do something with i

vector< string > names;
// ... 
string temp = names[ 10 ];
vector< string >::iterator a_name = 
              names.begin() + 10;
string temp2 = *a_name;

It is important that you choose carefully among the sequence containers, depending on what your requirements are. As a simple guide, you may find the following useful:

Use a list. Unless...

If you require contiguous elements, or need random access, use a vector.

If you know in advance how many elements there will be, and/or you are creating a collection from another collection, use a vector.

If you want random access and the ability to insert or remove at either end, use a deque.

(After [Meyers1999])

Our next point of call is a cave which is larger than it looks, and has all sorts of interesting hiding places where you may find fascinating insights into the world of C++'s power and elegance. We've only got time to look at the more conspicuous features for now, but hopefully you'll get an impression of the treasures that we miss on the way.

The main structure underpinning procedural programming was, well, procedures, which in C, as in C++, are represented by functions. Object Oriented programming is underpinned by the object, which has methods - functions which operate on the object rather than on parameters passed to it.

Generic programming is underpinned by the Functor or Function Object, which is something in between, or rather, has elements of both.

Consider the regular C++ function. It is a way of encapsulating a process, of abstracting the "how" of an algorithm from the "what". OK, let's get specific about this. So far, we've been printing the elements in a container^[3]:

void print_me( const string & s )
{
  cout << s << "\n";
}
list< string >::iterator i;
for( i = names.begin(); 
        i != names.end(); ++i )
{
  print_me( *i );
}

This is all very well, but what if the contained elements were not strings? A simple way to solve that problem is to make print_me a template function:

template< typename T >
void print_me( const T & s )
{
  cout << s << "\n";
}

Now it can be used for any type which defines operator<<() for standard output streams. So far, so good. What happens, though, if we want to output our elements to a stream other than the console? Our first attempt might be to overload print_me to take an ostream argument, but we can do better than that.

class print_me
{
public:
  explicit print_me( ostream & s )
    : strm( s )
    { }
  void operator()( const string & rhs )
  {
    strm << rhs << "\n";
  }
  
private:
  ostream & strm;
};

A slight return to allowing only strings to be printed here aside, this is a Function Object, or Functor. It is so called because it defines the function-call operator: operator(). Just as you can overload operators +, -, *, etc, you can provide your own versions of this operator so that an instance of your class can appear in an expression as if it were a function:

print_me printer( cout );
printer( "Steve" );

The constructor associates the print_me object with the required state (the output stream object), and so, "calling" the functor with a matching argument (or, as here, one which is substitutable for the direct match [Henney2000a], [Henney2000b]).

This could then be used inside the loop as before:

list< string >::iterator i;
for( i = names.begin(); 
      i != names.end(); ++i )
{
  printer( *i );
}

When we wanted the function to be able to handle any type for which the stream insertion operator was defined, we made it a template function. However, there is a snag with making the print_me class a template; consider how it would be used:

list< string >::iterator i;
for( i = names.begin(); 
          i != names.end(); ++i )
{
  printer< string >( *i );
}

This is hardly ideal. Since the compiler "knows" the type of *i (it's an iterator for a container of strings, and so points to a string element), we would like very much for the compiler to deduce the template type of the print_me object. The compiler can't do this at all; it can only deduce template arguments for functions because you pass actual arguments to the function itself. And here lies our clue: we can make the member function operator() a template, thus allowing the compiler to deduce the template arguments from our actual parameters to it:

class print_me
{
public:
  explicit print_me(ostream & s)
    : strm( s )
    { }
  template< typename T >
  void operator() (const T & rhs)
  {
    strm << rhs << "\n";
  }
  
private:
  ostream & strm;
};

And there you have it - the final version of our functor. Now we can use it as we would really have used a function. This turns out to be surprisingly expressive and powerful, especially when we come to look at the standard algorithms. We can use it to compose operations together. For example, consider our container of names. Supposing we want to find an element that matches either this name or that one. We might define a functor like this:

struct name_is
{
  explicit name_is(const string & n)
    : name(n)
    { }
  bool operator()
        (const string & rhs) const
  {
    return name == rhs;
  }
  const string & name;
};
name_is name1( "Steve" );
name_is name2( "David" );
vector< string >::const_iterator i;
for( i = names.begin(); i != names.end(); ++i )
{
  if( name1( *i ) || name2( *i ) )
  {
    break;
  }
}
// do something with i

Here we have two objects of type name_is, each with different stored state. Using functions alone, this simply cannot be done: such local state would have to be a global or static variable. The only alternative would be to pass in the second name every time.

As we've already seen, we can use the Standard Library containers to store elements of (nearly) any type, and we can get access to those elements, read them, write to them and so on. For anyone who has had to implement such container "classes" in C, or even in C++, just having them provided has obvious benefits, especially since they inter-operate so well.

The STL portion of the C++ Standard Library is much more than the container classes, however. In fact they represent only a small part of the facilities provided. It is here, with algorithms, that we can combine the simple concepts of Iterators (and through them, the facilities of the Containers) and the power of functors to great effect.

We have already seen that the container classes provide iterators for themselves via begin() and end() member functions, which give iterators to the start and one past the end of the elements. Since iterators from any of the containers, associative and sequence alike, can be incremented to get the next element, every container looks like a sequence when viewed exclusively with iterators. Thus you have the concept of an Iterator Range. For an entire container, such a range is expressed as a half open interval [Austern1998]:

[begin, end)

This notation means that the sequence starts with begin, and that end can be reached by incrementing begin. end itself is one after the last element. Specifically, the range includes begin, but not end.

We have already touched on Iterator Concepts like Random Access and Bidirectional. Some algorithms expect the iterators to conform to a particular concept like this; most require only an Input Iterator (one which can be read from and incremented) but some, like sort(), require Random Access Iterators^[4]. Remembering that these restrictions are minimum requirements is important; a Random Access Iterator makes a perfectly good Input Iterator, as does a Bidirectional one.

Way back when we first looked at containers, we saw a somewhat lengthy piece of code that iterated over a container of strings, printing each one to the console. It was noted at the time we would see a better way to achieve this, and here it is. First, a reminder of the original:

list< string >::iterator i;
for( i = names.begin(); i != names.end(); ++i )
{
  cout << *i << "\n";
}

We can enlist the help of the print_me object we defined earlier to reduce this to a single line of code:

for_each(names.begin(), names.end(), print_me(cout));

There is yet a better way, involving a different beast - an ostream_iterator - which does away with the need for our functor, but that's beyond the current scope.

Here, then, we use a Standard Algorithm, for_each(), which takes an iterator range, and an operation to perform on each element. Note also that the print_me object is an anonymous temporary, which means we have no need to construct it separately, and it automatically goes out of scope at the end of the "loop". We have lost none of the notational convenience of the templated member function - it is still done by the compiler as required, but we have lost all the verbosity of declaring our iterators in the previous cumbersome for-loop.

The print_me functor is an example of a Unary Function. It takes a single argument and can be called like a regular C++ function. Correspondingly, there is a concept of Binary Function, which takes two arguments. There are also special types of Unary and Binary functions called Predicates which differ in that they return a boolean value.

Our name_is functor is a Unary Predicate (takes one argument and returns a bool). We could use it with for_each(), but for_each() doesn't use the return value from the functor it uses. If we want to find an element such as we attempted previously we need a new algorithm:

Our name_is functor is a Unary Predicate (takes one argument and returns a bool). We could use it with for_each(), but for_each() doesn't use the return value from the functor it uses. If we want to find an element such as we attempted previously we need a new algorithm:

  find_if( names.begin(), names.end(),
              name_is("Steve"));

This algorithm returns the iterator where the requested name is found (specifically the point at which the predicate name_is returned true). If the object was not found, then names.end() is returned. In this case, we could have used the simpler find() algorithm, for which you need not provide a predicate, only the value to find. Consider:

list< string > names;
// initialise names...
list<string>::iterator i = find(names.begin(), names.end(),"Steve");
if( i != names.end())
{
  *i = "Stephen";
}

This business of passing in the iterator range, rather than the container itself, provides great flexibility in the way the algorithms operate. In general, algorithms that search for an element, or that change elements in some way, return an iterator into the container, which can then be used as part of the iterator range for another algorithm. Importantly, it is not necessary that [Begin, End) is the complete range of the container.

In our quick look at functors, we ended with a way of using two functors with different state, for the purpose of finding one or the other in the container. Before we leave the caves altogether, let's have a quick look into one of the darkest corners...

Different aspects of the STL are designed to work together, for example, the containers and algorithms are glued together using iterators, and the algorithms themselves can be customised with your own code using functors.

The C++ Standard Library provides several functors for your use, ones which perform simple, but vital operations, such as adding two elements together (requiring only that operator+() is defined for that type), or determining if one is the same as another.

One of the simplest standard functors is called equal_to and does exactly that. Here is equal_to in action:

list< string > names;
find_if(names.begin(), names.end(),   
  bind1st(equal_to<string>(),"Steve"));

So what is this bind1st thing?

bind1st is an Adaptor; it takes one functor and "adapts" it into a different kind of functor. In particular, it adapts binary functors into unary functors by storing the first argument.

This code snippet becomes more clear when you understand that equal_to is a Binary Predicate. It takes two parameters of, in this case, string, and determines if the left one is the same as the right, and returns the result as a bool. Specifically, and this is the difference between equal_to and name_is, you cannot construct an equal_to object with the object to be tested; you must pass both arguments to the function call operator.

Instead, you call bind1st with your first parameter and a functor. bind1st is itself a Unary Function^[5]. What we're trying to achieve is to test each element of the container against the string "Steve", and bind1st allows us to do that. The algorithm find_if will call bind1st (a Unary Function) with each element in its range, and bind1st in turn will pass that on to equal_to, along with the string "Steve".

This magic is possible because equal_to is an Adaptable Predicate. This grand sounding title means nothing more (nor less) than equal_to has internal public typedefs for its arguments and return type. In practice, it means that it publicly inherits from the conveniently provided binary_function class, which provides those typedefs according to template parameters you provide. It looks something like this:

template< typename FirstArgument,
        typename SecondArgument,
         typename ReturnType >
struct binary_function
{
  typedef FirstArgument 
             first_argument_type;
  typedef SecondArgument 
              second_argument_type;
  typedef ReturnType   return_type;
};
template< typename T >
class equal_to : 
  public binary_function< T, T, bool >
{
public:
  bool operator()(const T & l,const T & r)
  {
    return l == r;
  }
};

Now, of course, equal_to has typedefs identifying its argument and return types. bind1st, along with all the other adaptors, require these typedefs so it can construct a function call from the various parts. There is another base class for Unary Functions, called, oddly, unary_function, which has only two typedefs. So far we've discovered that we can combine function objects with each other using adaptors to provide functionality not achievable directly. However, when we first looked at functors, we wanted to be able to search for one of two names in our list of names, and for that we need to extend the STL, because it only provides part of what we need. Before we leave we'll take a quick look behind the scenes of what makes the STL tick.

Our goal is to be able to search a container of strings for either this name or that one, as we did with our own name_is functor:

name_is name1("Steve");
name_is name2("David");
vector< string >::const_iterator i;
for( i = names.begin();
      i != names.end(); ++i )
{
  if( name1(*i) || name2(*i))
  {
    break;
  }
}
// do something with i

Looking through the facilities provided by the C++ Standard Library, we find there is a Binary Predicate called logical_or, which looks like it suits our purpose. Perhaps we could put it to use like this:

find_if(names.begin(), names.end(),
  logical_or< bool >( 
    bind1st(equal_to< string >(), 
           "Steve" ),
    bind1st(equal_to< string >(),
           "David")));

Alas this isn't possible; logical_or expects to be able to apply the || operator to its arguments, which means they must be (convertible to) bool^[6]. What we need is to be able to compose logical_or, and the two bound equal_tos into a single expression.

In an expression like x || y, x and y are operands, and || is the operator. So, we have a left operand, a right operand and an operator to consider. Since we want to make this "composer" object as general as we can, we can use templates to represent these concepts, and start from there.

We'll start with an object called binary_compose. It will be used to compose two operands into a Binary Function, so this makes sense.

template<   class Operator, 
      class XOperand, 
      class YOperand > 
struct binary_compose 
{
  Operator op;
  Xoperand x;
  Yoperand y;
};

We need a constructor in order to store these things so that the function call operator can call them:

binary_compose( const Operator & f, const XOperand & g, const YOperand & h ) 
  : op(f), x(g), y(h) 
  { }

Next we need a function call operator; this is a functor which can be used from an algorithm such as find_if(). How do we define this? The return type needs to be the return type of the operator, and the argument to the (unary) function call operator needs to be the same as that for bind1st (which will be the unary function in our case). This is where the nested typedefs of unary_function come in.

typename Operator::result_type 
  operator()(const typename 
         XOperand::argument_type & l )
{
}

Note the use of the keyword typename here. Without it, the compiler might think that argument_type and result_type were static members of class XOperand, since it doesn't know the type of XOperand due to it being a template parameter. The typename keyword is required when a name of a type is dependent on a template parameter [Stroustrup2000].

Anyway we're at the last hurdle. What should the implementation of operator() be? Well, we need to call the operator; this suggests

  op( ?, ? ); 

as a starting point. Focusing on using logical_or() here, we know that it takes two parameters, both bool. We want to be able to use equal_to(), which returns a bool. We will be using it via the adaptor bind1st, but it turns out that makes no difference. Simple:

typename Operator::result_type 
  operator()(const typename 
          XOperand::argument_type & l)
{
  return op(x(l), y(l));
}

When we substitute what we know in this case will become the various arguments, we have:

logical_or<bool> op;
bind1st x(equal_to<string>(), "Steve");
bind1st y(equal_to<string>(), "David");
op(x(l), y(l));

Remember bind1st is a function, not a class, so this won't compile. So we have two objects, x and y, which are functors, and are later called using the argument to this function call operator. We do have to go one step further, however, because, if you remember, the compiler won't be able to deduce our template parameters, because binary_compose is a class. Since we're storing objects of the template types, we can't use a template member function as we did for our print_me functor, but we can use a helper template function which returns a binary_compose object of the right type. This may seem familiar - it's exactly what bind1st is for binder1st.

template<class Op, class XOp, class YOp>
binary_compose<Op, XOp, YOp> compose2(
            Op op, XOp xop, YOp yop 
{
  return binary_compose<Op, XOp, YOp>
                    (op, xop, yop);
}

So now we can use this in an expression like:

find_if( names.begin(), names.end(),
  compose2(logical_or<bool>,
    bind1st(equal_to<string>, "Steve"),
    bind1st(equal_to<string>,"David")));

Lastly, why binary_compose and compose2? In the first case, we're composing a binary operation (this or that); the binary doesn't relate to the composed functions but the required result. compose2 is so named because we want to "compose two" operands though an operator functor.

However, I must own up. Both binary_compose and compose2, along with unary_compose and compose1 for making a unary operation, are common extensions to the STL. If your implementation doesn't have it, you can use this one^[7]. compose1 and unary_compose are, as ever, left as an exercise...

We have explored quite a lot of territory in our short trip, which has taken a little longer than anticipated, but I hope it's been worth it. There are many more strange and wonderful sights to see, and detailed tours are given by such famous explorers as [Austern1998], [Stroustrup2000] and [Josuttis1999].

I hope, however, that these is enough material here for you to be more sure-footed in your own explorations of the C++ Standard Template Library, and that we've thrown a little light on some possibly heretofore obscure elements and grottoes. The C++ Standard Template Library was designed deliberately to be extended, as we have with compose2, an this is its most important aspect. The STL is a specification for designing generic components, using iterators, adaptors, functors and algorithms, whether provided as part of the Standard Library itself, or written by yours truly. "Using STL effectively means extending it" [Austern1998].

A big "Hurrah!" to Nigel Dickens and Kevlin Henney, who kindly read drafts of this, and provided valuable feedback. Many thanks to Alan Griffiths who graciously gave his permission for me to (ab)use his metaphor from "Here Be Dragons". More thanks to Kevlin Henney, who first inspired the idea of poking around in dark corners to discover secrets, (I'm sure I could have made better use of it - next time maybe!) and for provided me with an advance copy of his "The Miseducation of C++" article for Application Development Advisor [Henney2001], plus some articles yet to be published. I've not referred to them directly, but they provided valuable background. Special Thanks to Nigel Dickens and Phil Hibbs for sparking and encouraging my interest in the STL in the first place. Without whom, etc..