Introduction

With the development of the STL generic algorithms, it becomes possible to build algorithms out of building blocks larger than "for i from 1 to N do step, step, step." As with Scheme, we can now construct algorithms from algorithms. This has several benefits:

• Development speed: using bigger pieces leads to answers faster
• Running speed: using carefully engineered pieces leads to faster answers
• Maintainability: each call to a generic algorithm says what it's doing in a way that "for i from 1 to N..." can't

To take advantage of the generic algorithms, you have to learn to think and "pseudo-code" at a higher level, using these bigger building blocks.

I call this "STL-think." When you use STL-think, you rarely write for loops. You don't need them. 80% of the most common for loops are already written in STL generic algorithms.

Key Building Blocks

For me, the generic algorithms that make the biggest difference in thinking are:

• accumulate()
• transform() + inserters
• remove_copy_if()

These are so useful because they make it possible to

• significantly transform a collection of values and collect results,
• using side-effect-free functions

accumulate()

Think accumulate when you want to get one value from a set of values.

For example, the average of a set of values in STL-think is simply

accumulate the sum and divide by the number of values

In C++, this becomes

accumulate( c.begin(), c.end(), 0 ) / (double) c.size()
 

[ Exercise for the reader: why is the cast to double important? ]

Here's another example. It's very common to need to take the square root of the sum of the squares of a set of values. In STL-think:

take the square root of the accumulated sum of squares

In C++, this becomes

sqrt( accumulate( c.begin(), c.end(), 0, squareSum ) )
 

where squareSum() is

double squareSum ( double sum, double x )
{ return sum + x * x; }
 

transform() + inserters

With copy() we can copy a set of values into another container. But a more common need is to copy a set of values, changing them in the process. For example,

• given a vector of numbers, make a vector of their squares
• given a set of employees, make a list of their names

The secret is to use transform(), which is like copy() except that it calls a function on each value value copied, and send the result to an inserter that stores the result in the desired container.

For example, given a vector of numbers, make a vector with the squares of those numbers. In STL-think, this becomes

transform each number with square into a new vector

In C++, this becomes

transform( c.begin(), c.end(), back_inserter( v ), square );
 

where square() is

double square( double x ) { return x * x; }

To do the employee name example, we need to convert the employee name method into a function, using a function adapter.

For example, given a container of instances of Employee with the member function name(), make a vector of their names. In STL-think, that's

transform each Employee with name() into a vector

In C++

transform( c.begin(), c.end(), back_inserter( v ),
           mem_fun_ref( &Employee::name ) );

transform() is also useful for quickly printing out such things,using an ostream_iterator:

 
ostream_iterator<string> outIter(cout, "\n");
...
transform( c.begin(), c.end(), outIter,
           mem_fun_ref( &Employee::name ));

remove_copy_if()

Our final common task is taking a set of objects and making a new set of all objects with a particular property, e.g., all the even numbers or all the primes. This can be done in the STL by removing all the objects without that property, using remove_copy_if().

For example, we want to print all the even numbers in a vector. In STL-think this becomes

copy the numbers to the output streaming, removing all numbers not even

In C++, this is

ostream_iterator<int> outIter(cout, "\n");
...
remove_copy_if( c.begin(), c.end(), outIter,
                not1( isEven ) );
 

where isEven() is

bool isEven( int n ) { return (n % 2) == 0; }
 

Of course, what we'd really like here is copy_if(), which was accidentally left out in the standard is easy to define. Then printing the even numbers in a container becomes

copy_if( c.begin(), c.end(), outIter, isEven );
 

Comments? Send mail to c-riesbeck@northwestern.edu.