Writing Your Own Algorithm

Problem

You need to execute an algorithm on a range and none of the standard algorithms meets your requirements.

Solution

Write your algorithm as a function template and advertise your iterator requirements with the names of your template parameters. See Example 7-10 for a variation on the copy standard algorithm.

Example 7-10. Writing your own algorithm

#include #include #include #include #include #include #include #include "utils.h" // For printContainer( ): see 7.10 using namespace std; template Out copyIf(In first, In last, Out result, UnPred pred) { for ( ;first != last; ++first) if (pred(*first)) *result++ = *first; return(result); } int main( ) { cout << "Enter a series of strings: "; istream_iterator start(cin); istream_iterator end; // This creates a "marker" vector v(start, end); list lst; copyIf(v.begin( ), v.end( ), back_inserter >(lst), bind2nd(less( ), "cookie")); printContainer(lst); }

A sample run of Example 7-10 will look something like this:

Enter a series of strings: apple banana danish eclaire ^Z ----- apple banana

You can see that it only copies values less than "cookie" into the destination range.

Discussion

The standard library contains the copy function template, which copies elements from one range to another, but there is no standard version that takes a predicate and conditionally copies each element (i.e., a copy_if algorithm), so that's what I have implemented in Example 7-10. The behavior is simple enough: given a source range and the beginning of the destination range, copy elements to the destination range for which my unary predicate functor returns TRue.

The algorithm is simple, but there's more going on with the implementation than meets the eye. Starting with the declaration, you can see that there are three template parameters:

template Out copyIf(In first, In last, Out result, UnPred pred) {

The first template parameter, In, is the type of the input iterator. Since this is the input range, all copyIf needs to be able to do is extract the dereferenced value from the iterator and increment the iterator to the next element. This describes the input iterator category (iterator categories are described in Recipe 7.1), so that's the kind of iterator we will advertise we need by naming the template parameter In. There is no standard convention (In and Out are my conventions, which I described in the first recipe of this chapter), but it's easy enough to get your point across with similar naming conventions: InIter, Input_T, or even InputIterator. The second template parameter, Out, is the type of the iterator that refers to the range where elements will be copied to. copyIf needs to be able to write to the dereferenced value of the output iterator and increment the iterator, which is the description of an output iterator. By advertising your iterator requirements with the template parameter names, you make the calling conventions of the algorithm self-documenting. But why use two different iterator categories?

There are at least a couple of reasons why I used two different iterator categories in copyIf. First, the operations on each range are slightly different, and since I will never need to go backward in the input range, or assign to it, all I need is an input iterator. Similarly, I will never need to read from the output range, so all I need there is an output iterator. There are requirements for each of the iterators that do not apply to the other, so it would make no sense to (for example) have one bidirectional iterator type and use that for both ranges. Second, using two different iterator types lets the caller read from one kind of range and write to another. In Example 7-10, I read from a vector and wrote to a list:

vector v(start, end); list lst; copyIf(v.begin( ), v.end( ), back_inserter >(lst), bind2nd(less( ), "cookie"));

If you try doing this using a single iterator type on your algorithm, it won't compile.

In Example 7-10, I passed a back_inserter as the beginning of the output range instead of, say, the iterator returned from lst.begin. I did this because lst has no elements in it, and in this algorithm (as in the copy standard algorithm), the destination range has to be big enough to hold all of the elements that will be copied to it. Otherwise, incrementing the output iterator result inside copyIf will have undefined behavior. A back inserter returns an output iterator that calls push_back on its container whenever you increment the iterator. This increases the size of lst by one each time the output iterator result is incremented. I describe the back_inserter class template in more detail in Recipe 7.5.

When writing your own algorithm for working with ranges (i.e., the standard containers), you should work with iterator arguments and not container arguments. You may be tempted, for example, to declare copyIf to take two container arguments instead of a source range and destination output iterator, but this is a less general solution than using ranges. You can't work with only a subset of elements in a container if you take container arguments, for one. Furthermore, in the body of copyIf, you would depend on the containers' begin and end member functions to get the range you were after, and the return type would depend on the type of container used as the output range. This means that using nonstandard ranges will not work with copyIf, such as built-in arrays or your own custom containers. These, and other reasons, are why the standard algorithms all operate on ranges.

Finally, if you do write your own algorithm, double-check the standard algorithms for what you need. They may seem like very simple algorithms at first glance, but their apparent simplicity is because of their generality, and nine times out of ten they can be extended in some fashion to meet your needs. Reusing the standard algorithms is something you should strive for, since it goes along way in ensuring portability and efficiency.

See Also

Recipe 7.5