STL is a pretty complete set of tinker toys, but you can always find a few more good ones to add.
Introduction
I have had the opportunity, over the past two years, to be part of a major software project that made extensive use of the C++ Standard Template Library. Looking back, I find that one of the remarkable advantages of the STL over earlier attempts at similar libraries is its flexibility and extensibility. This is primarily due to the way the STL decouples containers from algorithms. Algorithms generally take a pair of iterators as arguments and act on the sequence of elements defined by this pair of iterators. Sometimes, they will also take a "functional," or function object, as an additional argument. A typical example is a unary functional returning a bool. An algorithm can operate on each element conditionally, choosing just those elements that return true when passed as an argument to the functional.
All this has nothing directly to do with containers. Containers and their iterators are merely one possible way to supply sequences. As long as you mind the STL's iterator specifications, you can therefore drop in your own containers, iterators, algorithms, and functionals and have them cooperate seamlessly with everything that is already there.
Adding containers to the STL is certainly not something that the average STL client programmer would attempt very often. If the need arises for containers that the STL does not provide, such as hash-tables or singly linked lists, one would try to find them elsewhere. Writing your own algorithms and functionals, on the other hand, is something that happens all the time when using the STL. The STL provides a collection of algorithms and functionals that are so generic in nature that they are likely to be needed in almost every context. But it doesn't try to provide all potentially useful algorithms and functionals. The possibilities are unlimited. The STL specification does a remarkable job in providing just enough to serve everybody's most frequent needs while keeping the entire library reasonably compact. So it is likely that any software project of more than trivial size will add its own specific algorithms and functionals.
I would certainly not want to spoil this pleasant situation by dumping on the rest of the world my own collection of algorithms and functionals. You'll be better served by writing your own as the need arises. However, among those things that I had to add to the STL, I have identified a small number of items that are so frequently needed and so generic that it seems worth having them around at all times. The purpose of this article is to provide and explain these additions to the STL. The complete source code comes with documentation in HTML format.
Member Function Adapters
Let me begin by reminding you that a functional is a class with an overloaded operator(). A predicate is a functional that returns a bool result. Suppose now that cont is some container of objects of type CSomeClass, and you want to find out if cont contains an object that has some property X. To determine whether or not an object of type CSomeClass has property X, CSomeClass supplies a member function:
bool HasPropertyX() const;The task at hand is a typical application of the STL algorithm find_if. The container cont has an object with property X if and only if:
cont.end() != std::find_if(cont.begin(), cont.end(), pred)Here, pred must be a predicate whose operator() is defined something like:
bool operator()(const CSomeClass& x) const { return x.HasPropertyX(); }This would be easy enough to write. However, since turning a member function into a functional in this way is something that will obviously occur quite frequently, the STL provides a generic mechanism to do just that. The template function mem_fun_ref in the std namespace takes as its only argument a pointer to a member function. The only obvious requirement is that the member function take no arguments. There is an additional, less obvious requirement, which we will run into shortly. The return value of mem_fun_ref is a functional of the kind that we need in our example. It takes a reference argument and calls the indicated member function on this argument. If the member function is to be called through a pointer rather than a reference, you must use mem_fun instead of mem_fun_ref. If the member function takes an argument, use mem_fun1 or mem_fun1_ref. The types of the functionals that these non-member functions return are mem_fun_ref_t, mem_fun_t, mem_fun1_ref_t, and mem_fun1_t, respectively. In practice, using these template functions will usually save you from having to refer to these types explicitly.
Rather than writing your own predicate pred for the algorithm find_if, you can solve the problem with the following one-liner:
cont.end() != std::find_if( cont.begin(), cont.end(), std::mem_fun_ref(CSomeClass::HasPropertyX) );Unfortunately, this will compile only if your STL implementation conforms to the final C++ Standard. In earlier drafts of the C++ Standard, there was only one version of mem_fun_ref, which took as its argument a pointer to a non-const member function. The compiler rightfully refuses to cast a pointer to a const member function to a pointer to a non-const member function. The C++ Standard has therefore recently added alternate versions of the four original member function adapters that work for const member functions. Their type names are simply the names of the original adapters prefixed with a const_. By contrast, template functions such as mem_fun are simply overloaded for const member functions, so there is no need to prefix them with const_.
Since there is at least one widely used STL implementation out there that does not yet include the new const member function adapters, I have provided them as part of my STL supplement, enclosed in an #ifdef so they can easily be thrown out.
I said earlier that there is a less obvious requirement on the member functions that can be supplied to mem_fun_ref. To see what that requirement is, suppose now that our class CSomeClass also has a member function:
void Dump(CDumpTarget& dump_target) const;which dumps the state of the object to some suitable target. Suppose further that we wish to iterate through our container and dump each object. Easy enough, it would seem:
std::for_each( cont.begin(), cont_end(), std::mem_fun1_ref(CSomeClass::Dump, dump_target) );No such luck. This will not compile because Dump returns void. The overloaded operator() of the functional that mem_fun1_ref returns looks like this:
R operator()(const T& ref, A arg) const {return (ref.*_Ptr)(arg); }where R, T, and A are template arguments. It is not even necessary to understand this in full detail. It is clear that we cannot use the type void for the return type R here. In a function returning void, the compiler will not accept any lexical token other than a semicolon following the return statement.
Recall that we already have eight member function adapters, four for non-const member functions and the four corresponding const versions. I have provided eight more, which are exact counterparts to the original eight except that they work for member functions returning void. Their names are the original names prefixed with a void_. Here, I have prefixed not only the class type names with void_, but also the names of the generating template functions mem_fun_ref, mem_fun, mem_fun1_ref, and mem_fun1. Using the same names is theoretically possible. However, it requires that the compiler handle partial template specialization, and some widely used compilers still don't do that.
Figure 1 shows void_mem_fun_t as an example of a member function adapter for member functions returning void.
Predicate Logic
Let's stay with the example of the container cont that holds objects of type CSomeClass. Suppose now we wish to find the first element, if any, in the container that does not have property X. We must call the algorithm find_if with a predicate that returns true on a CSomeClass object if and only if that object does not have property X. The member function adapter that we used earlier provided us with a predicate that returns true on a CSomeClass object if and only if that object has property X. Again, we are looking at a situation that cries out for a generic solution.
We need an adapter that takes any predicate and turns it into a new predicate that represents the negation of the original one. The STL does indeed provide two such adapters, called unary_negate and binary_negate, with corresponding template functions called not1 and not2 to generate them. The first one works for predicates taking one argument, the second one for predicates taking two arguments. Since our original member function CSomeClass::HasPropertyX takes no argument, the predicate obtained from the member function adapter mem_fun_ref takes one argument. Therefore, not1 is the function we need to use. The call
std::find_if( cont.begin(), cont.end(), std::not1(std::mem_fun_ref(CSomeClass::HasPropertyX)) );will return an iterator to the first element in cont that does not have property X, or cont.end() if no such element exists.
Now where there's a "not," you can bet that "and" and "or" are not far off. Indeed, I often find myself in a situation where I have two predicates and I need a new one that represents the logical conjunction or disjunction of the two. Every time this has happened to me, the two predicates were reasonably similar in the sense that the number and the types of the arguments were the same. For a rather typical example, suppose CSomeClass also has a const member function HasPropertyY, and we wish to find the first element, if any, in our container that has both properties. Having seen the adapter function not1 in action, we obviously want to be able to say:
std::find_if( cont.begin(), cont.end(), and1( std::mem_fun_ref(CSomeClass::HasPropertyX), std::mem_fun_ref(CSomeClass::HasPropertyY) ) );or, if we are looking for the first element with at least one of the two properties,
std::find_if( cont.begin(), cont.end(), or1( std::mem_fun_ref(CSomeClass::HasPropertyX), std::mem_fun_ref(CSomeClass::HasPropertyY) ) );The STL does not have anything like this. At first glance, you might think that the STL's logical_and and logical_or do the job. However, upon closer inspection you will see that these correspond to the template class logical_not rather than to the template functions not1 and not2, and that is not what we are looking for. I have therefore provided the four adapters unary_and, binary_and, unary_or, and binary_or, with generating functions and1, and2, or1, and or2, respectively. They are modelled after not1 and not2, except that they take two predicates instead of one, and they require that the two predicates have the same number and types of arguments. Usage of these adapters is analogous to not1 and not2 and hence should need no further explanation. Figure 2 shows unary_and as an example.
Composition of Functionals
If f is a function taking one argument of type T and g is a function that returns a T, then we may evaluate f(g(...)), where the ellipsis stands for the parameters of g. As you will recall from elemetary algebra, this is called "composition of functions." When working with STL-style functionals, rather than functions, this situation calls for a certain kind of adapter. This adapter takes two functionals func1 and func2, where the result type of func2 allows a conversion to the type of the sole argument of func1. The adapter would turn these two functionals into a new one whose operator() evaluates func1(func2(...)).
The C++ Standard does not provide such a composition adapter for functionals. However, Austern mentions it as a "frequent addition," on pages 431 through 434 of his book [1]. Since I know of at least one widely used STL implementation that does not, or does not yet, have this addition, I have provided it in my STL supplement, again enclosed in an #ifdef. The actual adapters are called unary_compose and binary_compose, and the template functions that generate them are called compose1 and compose2. Both turn functionals func1 and func2 into func1(func2(...)). The difference is that compose1 requires func2 to be unary, whereas compose2 requires it to be binary.
The following example shows a functional that takes doubles r and t as arguments and returns exp(r * t), the continuously compounded cumulative return on the dollar after time t at a return rate of r.
compose2( std::ptr_fun(exp), std::multiplies<double>() );As with the member function adapters that I have mentioned earlier, the composition adapters will not work if the return type of the outer functional is void. Therefore, I have provided two more adapters void_unary_compose and void_binary_compose, with generating functions void_compose1 and void_compose2. These are precise counterparts to compose1 and compose2, except that they require the outer functional to return void. Figure 3 shows void_binary_compose as an example.
Binary Search
One of the most frequent operations to perform on a container, second perhaps only to iteration, is to look up elements. Trivial as it may seem, this turns out to be a rather subtle issue. There are essentially three different situations.
In the first scenario, your container is a map, a multimap, a set, or a multiset. In the STL, these are all internally based on trees, but there are also hash table versions available. All of these containers were designed for efficient lookup. In the case of sets, you actually look up elements by their value, whereas in a map, you lookup elements by key. To perform a lookup in any one of these containers, you want to use the member function find, not the algorithm find. In the case of multimap and multiset, you can also use the member functions lower_bound, upper_bound, and equal_range to determine an entire range of positions. Using these member functions guarantees you the efficiency that the containers were designed for.
In the second scenario, your container is something other than a map or a set, and the elements are not sorted in any way. In this case, you have no choice but to use the algorithm find, which will simply iterate linearly through the entire collection and stop when it has found the desired element. In terms of complexity, this is about as bad as it gets, but in the absence of an ordering, you cannot do any better than that.
In the third scenario, your container is again anything other than a map or a set. This time, however, there is an ordering relation between the elements, and the container is in fact sorted with respect to that ordering. In other words, if it1 and it2 are two valid iterators and it1 < it2, then *it1 < *it2. If this sounds abstract or contrived to you, think of a vector that holds dates. The dates were placed in the container using push_back, and each newly added date is later than anything that was already in the container. Thus, the vector is in fact an ordered collection of dates. Now if you wish to find a particular date in the collection, even the thought of using the algorithm find should make you cringe. You know that in an ordered sequence, you can use a binary search, which will give you logarithmic complexity as opposed to the linear complexity of find. Need I remind you that the (binary) logarithm of 232 is 32?
Having anticipated this situation, the STL provides the algorithm binary_search. This algorithm will look up an element in the sense that it returns true or false depending on whether or not the element is present. It will do so in logarithmic time, provided that the iterators given to the algorithm are random-access iterators. If you think about the way binary search works, you will agree that it must be possible to determine the distance between two iterators in constant time, and it must be possible to move an iterator forward or backward by any number of steps in constant time. That is what the random-access property ensures. Therefore, you will be out of luck with a container such as a list, but you will be in business with a vector.
The obvious drawback of the binary_search algorithm is the fact that it only tells you whether or not an element is present in the container. It will not give you its position in case of a positive answer. Chances are you will need this position, as the starting or ending point of an iteration, for example. The STL has a solution for you, and here's where things get subtle. Almost every book or document on the STL will give you the hint that the algorithms lower_bound and upper_bound are what you are looking for. Most do not go into any further detail, and at least one book that I have seen goes to great length to explain that you may simply use lower_bound as a drop-in for find. That's almost true, but not quite, as we will see shortly.
There is more than one way to explain precisely what lower_bound does. The most concise and, in my opinion, most practical explanation can be found in Austern [1], on page 310. A similar definition is given in Musser and Saini [2], p. 346. Referring to the declaration:
template<class FwdIt, class T> FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);we may describe the algorithm lower_bound as follows: it returns the first position in the range [first, last] before which val could be inserted without violating the ordering. Let me remind you that the notation [first, last] stands for the interval between first and last with both first and last included. Note that the indicated position always exists. There is no need to add anything like, "... such-and-such if no such position exists." Now consider the following code fragment:
std::vector<int> vect; vect.push_back(41); vect.push_back(43); vect.push_back(44); std::vector<int>::iterator it = std::lower_bound(vect.begin(), vect.end(), 42);A quick glance at the above description of lower_bound will convince you that the iterator it now points to the element 43 at position 1 in the vector. That is dramatically different from the algorithm find, which would have returned vect.end() because the element 42 is not present in the vector.
Do not despair, though, as there is an easy way to make use of lower_bound's superior performance and still get the exact same behavior as find. Recall that the notation [first, last) stands for the interval between first and last with first included but last not included. Now convince yourself that the following statement holds true: If the element val is present at all in the interval [first, last), then the first position before which val could be inserted without violating the ordering is the first occurrence of val in the interval [first, last). Using our definition of lower_bound, we can rephrase this as saying: If the element val is present at all in the interval [first, last), then:
lower_bound(first, last, val);returns an iterator that points to the first occurrence of val in the interval [first, last). That is almost identical to what the algorithm find does. The only difference is that if val is not present in the sequence, we may not conclude that lower_bound will return last, as find would. All we may conclude is that lower_bound will return either last, or some iterator it in [first, last) with *it != val. That was the case in our example of the vector with three elements. The value 42 was not present, and lower_bound returned an iterator it at position 1 with *it != 42.
This argument shows that we can make lower_bound act like find without increasing the complexity. Figure 4 shows you the code for an algorithm that I have called lower_bound_find. The algorithm first calls lower_bound. If the return value of lower_bound equals last or an iterator whose dereferenced value does not equal val, then it returns last. Otherwise, it returns what lower_bound has found. Note that under normal circumstances the if-branching could have been written a little more tightly as:
if(lb == last || *lb != val) return last; return lb;but that may cause *last to be evaluated if some mischievous programmer has done the unspeakable and overloaded operator||.
A few more remarks on the algorithm lower_bound_find are in order. I have provided a second version that uses a predicate pred rather than the binary operator< for the binary search. One can, of course, also base the binary search on the algorithm upper_bound. It's just that lower_bound is a trifle more elegant because it saves one iterator decrement. Also, I strongly recommend that you study the discussion of lower_bound and related algorithms in [1]. Austern explains precisely what prerequisites the various algorithms impose on the underlying ordering relation. In the above discussion, I have been relying on the intuitive understanding that the elements in the container are sorted "like integers," or "like dates," with the possibility of duplicates. Finally, I would have preferred to write lower_bound_find so that it branches on the iterator category of first and last. If these are random-access iterators, my lower_bound_find would be called. Otherwise, the STL's find would be called. However, this feature would require the use of the STL's iterator_traits, and that is not a realistic proposition as long as some major compiler vendors do not support partial template specialization.
Conclusion
Everybody who uses the STL will end up writing their own algorithms and functionals specific to the software project at hand. Here, I have shared with you some elementary additions to the STL which I suspect you will need regardless of the context you are working in. Have fun discussing the STL's binary-search capabilities, and remember: a quick little sample program settles almost every argument in no time.
References
[1] Matthew H. Austern. Generic Programming and the STL (Addison Wesley, 1998).
[2] David R. Musser and Atul Saini. STL Tutorial and Reference Guide (Addison Wesley, 1996).
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at thomas@styleadvisor.com.