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.
Stalagmites and Stalactites: Containers and Iterators
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 ]
Table 1. Sequences
| list | A doubly-linked list | #include<list> |
| vector | A dynamic array | #include <vector> |
| deque | A dynamic array with some special properties | #include <deque> |
Table 2. Associative Containers
| map | A collection of unique elements sorted by a key | #include <map> |
| multimap | Like map, but allows duplicates | #include <map> |
| set | A collection of unique elements sorted by value | #include <set> |
| multiset | Like set but allows duplicate elements | #include <set> |
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.
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
The list container is perhaps the simplest of all, because it imposes the fewest restrictions on how elements are handled. What this means in practice is that elements can be inserted anywhere in the container easily, and efficiently. Efficiency is an important aspect of the Standard Library in general, and the C++ Standard makes certain guarantees about how efficient operations on containers and algorithms are. For now, it is enough to know that list allows efficient insertion of elements at the beginning, the end and anywhere in between. Here is an example of how a list might be used [ 1 ] :
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
There is a fair amount going on here, which bears explanation. Firstly, the definition of a list:
list< string > names;
This creates a list of string s called names . The string argument is the template argument to the list container class (it isn't called the Standard Template Library for nothing!) and this can be any type which meets certain requirements, which we will look at later.
Next we declare a string , and read it from the standard input. As each string is read, we add it to the list using push_back() . It is important to note that the string is copied into the list as a new value; each iteration round the loop overwrites name, so this is desired behaviour. Also, note that the list grows automatically every time a new element is added to it; you don't have to allocate the memory yourself.
Next comes the really interesting part. We use an iterator to loop through the list to get at each element. We create a new iterator and initialise it to point at the beginning of the list, using the begin() member function of the list itself. It is important that the iterator we create is for a list of string s; any other iterator just will not do. Next, we test to see if the current position of the iterator is at the end() of the list. list::end() is actually one past the last element in the list, so when we reach this point, we know there are no more elements, and in fact trying to dereference the end of a container is a bad idea. Finally, we increment the iterator using the familiar increment notation.
Inside the loop, we dereference the iterator and output the contents to the console. Anyone familiar with pointer notation in C and C++ will recognise this. All iterators for the standard library containers support this usage for iterating over their elements and dereferencing the current element.
If you think that the example above is a little verbose, don't worry; we will be exploring a much better way of achieving the same result later on. For now, a basic understanding of the iterators in standard containers will suffice.
This verbosity can be alleviated using typedef to give a name to the type:
typedef list< string >::iterator output;
vector
In the meantime, we will move on to the next sequence container, vector. The first point of interest here is that the equivalent code for reading the names from the console which we did using a list previously, is almost identical when we replace list with vector: (the differences are underlined)
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
As it turns out, vector's iterators are more sophisticated than list's, but for the main examples, they are identical in appearance. We can increment (and decrement, by the way: --i in this example) the iterator, dereference it, and copy or compare it to another iterator of the same type.
What vector also allows us to do, that list does not, is access the container at any valid location. A side effect of this is that we can increment and decrement a vector's iterator by more than one, provided the result is still valid. A demonstration:
vector< string > names;
// ...
string temp = names[ 10 ];
vector< string >::iterator a_name =
names.begin() + 10;
string temp2 = *a_name;
Here, both temp and temp2 now have copies of element 10 in the vector, assuming that there are at least 11 names contained there (element 0 is the first element). If there were fewer than 11, then both string assignments would be invoking undefined behaviour.
This behaviour is allowed because vector provides Random Access. Why the new font? Random Access is a concept, as opposed to a language feature. The point is that vector uses Random Access Iterators [ Austern1998 ], whereas list uses Bidirectional Iterators. We have already seen the main difference between them, but it is important to note that Random Access is a refinement of Bidirectional, i.e. it implies Bidirectional behaviour as well. There are several iterator types, but suffice to say that all the standard containers provide Bidirectional iterators.
deque
The final sequence container is deque, pronounced "deck". In order to understand the benefits afforded by deque, we need to look at what makes vector and list so different from each other in terms of their management of memory.
vector provides an array of elements, which occupy a contiguous area of memory [ 2 ] . This has implications for two important things. Firstly, inserting an element anywhere but at the end of a vector requires that all existing elements which follow it must be shifted in memory. Secondly, when a vector needs more memory and is unable to satisfy that need from its own memory block, a new block needs to be allocated and all existing elements copied into it. Clearly these are expensive operations for large containers.
list, on the other hand, is at the other extreme. It's elements need not be in a single block of memory (list actually doesn't care either way - it assumes they are not) but it must allocate space for every element as it is added. Memory allocation is also a relatively expensive operation (compared to, say, accessing an element) and where a large number of elements is added to a list in one go, an allocation needs to take place for each element.
So, vector supports direct access to any element in the sequence (courtesy of Random Access), at the expense of what you might call Random Insertion - inserting an element anywhere but at the end is inefficient. list, in contrast, supports efficient Random Insertion at the expense of Random Access.
deque provides the middle ground. There is no guarantee that a deque's elements occupy contiguous memory, but it does provide Random Access to the elements. What this means in practice is that you can insert or remove elements from either end of a deque, and this will be efficient, because when new memory is required, there is no need to copy all the existing elements into it. Insertion or removal from anywhere in the middle is not guaranteed to be efficient, however.
In Summary
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 ])
The Cave of Echoes: Functors
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.
Source of the River: Algorithms
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.
More On Containers And Iterators
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.
An Illustration
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...
The Witches' Broth: Adaptors and Adaptable Function Objects
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 typedef s for its arguments and return type. In practice, it means that it publicly inherits from the conveniently provided binary_function class, which provides those typedef s 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 typedef s identifying its argument and return types. bind1st , along with all the other adaptors, require these typedef s 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 typedef s. 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.
Under The Ropes
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_to s 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 typedef s 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...
Back At The Exit
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 ].
Acknowledgements
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..
Bibliography
[Austern1998] Matthew H Austern, Generic Programming And The STL , Addison Wesley 1998
[Boost2001] www.boost.org
[Griffiths2000] Alan Griffiths, Here Be Dragons, Overload 40 , 2000
[Henney2000a] Kevlin Henney, From Mechanism To Method: Substitutability, C++Report 12(5), May 2000, Overload 39, September 2000
[Henney2000b] Kevlin Henney, From Mechanism To Method: Valued Conversions, C++Report 12(7), July 2000
[Henney2001] Kevlin Henney, Effective C++: The Miseducation of C++, Application Development Advisor , April 2001
[ISO1998] International Standard: Programming Language - C++ , ISO/IEC 14882:1998(E), 1998
[Josuttis1999] Nicolai Josuttis, The C++ Standard Library - A Tutorial and Reference , Addison Wesley 1999
[Koenig-1997] Andrew Koenig, Barbara Moo, Ruminations on C++ , Addison Wesley, 1997
[Meyers1999] Scott Meyers, Effective C++ CD , Addison Wesley 1999
[Stroustrup2000] Bjarne Stroustrup, The C++ Programming Language , Special Edition, Addison Wesley 2000
[STLport2000] www.stlport.org (various source files, binary_compose in particular)
[ 1 ] Please note that all of the code examples here assume " using namespace std; " for brevity
[ 2 ] This is not actually guaranteed by the C++ Standard at the time of writing, but it is certainly intended. For those interested, vector probably couldn't meet its complexity requirements without this feature. It will be in the first round of corrections to the Standard [ ISO1998 ].
[ 3 ] [ Koenig-1997 ] uses a similar example for a rationale of "why C++, and not C, then?"
[ 4 ] Note that list provides its own sort(), since it can't use the standard algorithm version
[ 5 ] bind1st is actually a helper function which deduces the templates for the adaptor itself (called binder1st); recall that the compiler cannot deduce the template parameters for a class. We will refer to bind1st as the adaptor, however to avoid clouding the issue!
[ 6 ] Or overload the || operator. For why this is not a good idea, see item 7 in the "More..." section of [ Meyers1999 ]
[ 7 ] Or look at the much more sophisticated adaptors and composers at [ Boost2001 ]
