EECS 311: STL-Think |
Home Course Info Links Grades |
Lectures Newsgroup Homework Exams |

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.

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

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; }

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

Employeewithname()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 ));

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.