Introducing Generic Algorithms

Although the containers available provide a number of different useful methods, there are times when we need something a little more, when the container does not provide the necessary facilities to perform some operation. As you'll see, generic algorithms provide a strong set of tools to work with.

In case you are wondering, generic algorithms are exactly what they say they are; algorithms to provide some form of computation, available (under the right circumstances) to many types of data. Thus, a generic algorithm to sort a set of data should be able to compute on a character array; on an array of integers; on some container of objects, and so on.

In fact, we don't actually use data structures directly with generic algorithms. All algorithms accept (at the least) iterators as their arguments, and the type of iterator used with the algorithm determines what containers (and more generally, any object that uses iterators) can be used with the generic algorithm.

For example, consider list, which uses bidirectional iterators. Can we use the sort algorithm with list? Let's check the interface to sort:

     template <typename RandomAccessIterator>
     void sort(RandomAccessIterator first,
               RandomAccessIterator last);
     

Since the interface declares that we need RandomAccessIterator, using the sort algorithm with list is impossible - a compile error will result because list uses bidirectional iterators. This means that we can only use sort with vector and deque. This doesn't mean that we can't sort a list - in fact, list provides it's own sort method. If you're wondering how to sort set and map (because both use bidirectional iterators like list), remember that elements are inserted according to their value anyway, so are sorted automatically using a criterion defined by yourself.

There are many algorithms available to us, far too many to describe here. So instead we'll look closely at a few key algorithms, providing plenty of examples, and provide a summary of the rest of the algorithms in Generic Algorithm Summary, should you wish to explore them.

We'll look at the following generic algorithms here just to get a taste of them:

• for_each enables us to walk through collections of objects, enabling us to perfrom some form of computation on each element of the collection.
• find searches for some specified element.
• transform let's us take some range, and copies the result of calling some operation op to another destination (in fact, both ranges can be the same).
• partition enables us to move through a range of elements, moving elements that satisfy some unary predicate to the start of the range, leaving the rest of the elements to sit at the end of the range.
• accumulate is a numerical algorithm that we can use to move through a range and accumulate some sum as we move through it.