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

This is a quick summary of some of the most useful
**algorithms** in the Standard Template Library.

See also the STL set algorithms.

Algorithm: a generic function for searching or modifying STL containers.

Note that these functions take
**iterators**, not containers.
This is an important pattern of the STL that should be followed in
your own generic code.

Many of them also take functional arguments. What you can do with generic algorithms, iterators, and functional arguments can be pretty amazing.

The generic functions use iterators just as you use pointers in C to get elements from and store elements to various containers. Some generic functions can work with the minimal iterators, others may require the extra features. So a certain algorithm may require certain containers because only those containers can return the necessary kind of iterators.

Many of the generic algorithms take functions as arguments. This brings to C++ the same kind of higher order programming found in Scheme and Lisp.

The concepts behind higher order functions are covered in EECS 111.

Musser et al.
call these **nonmutating** sequence
algorithms. They are used to search containers and collect
information, but they do not change the contents of the containers.

InputIterator find(InputIterator begin, InputIterator end, const T& value);

`find` looks for `value` in the container, starting
at `begin`, and stopping with `end`. As usual for all
STL algorithms, `end` is not looked at. It is the location
just past the last item to check.

resultIter = find(v.begin(), v.end(), value); if (resultIter != v.end()) cout << "Found it!" << endl;

Notice that `find` doesn't return a boolean value, it
returns an iterator. That iterator points to the place where the
value was found. This lets us search for more occurrences, if we want
to. We just add the following code to the above:

resultIter = find(resultIter++, v.end(), value); if (resultIter != v.end()) cout << "Found it again!" << endl;

We could easily use this to write a loop to count how many times
the value occurs in the container, but the STL already provides a
`count` algorithm for us.

`find_if` is for searching with a
general predicate rather than a value.

InputIterator find_if(InputIterator begin, InputIterator end, Predicate pred);

`find_if` returns an iterator pointing to the first value
in the range satisfying the predicate.

As is typical with the STL, we create predicates using function
objects, i.e., defining a class that overloads `operator()`.
There are lots of variations on how to do this. The code below
finds the first even number in a
container, by defining a function object
`IsEven` and an instance of it,
`evenPred`, in one declaration, and passing `evenPred`
to `find_if`:

class IsEven { public: bool operator() (int x) const { return ((x % 2) == 0); } } evenPred; resultIter = find_if(v.begin(), v.end(), evenPred); if (resultIter != v.end()) cout << "Found the even number " << (*resultIter) << endl;

`count` is for counting occurrences of
a value in a container.

size_t count(InputIterator begin, InputIterator end, const T& value);

`count` counts the number of occurrences of the value
between `begin` and `end` and adds the result to
`n`. `size_t` is an integer type defined
to be large enough to hold the maximum size of any container.

int num = count(v.begin(), v.end(), 10); cout << "Found " << num << " occurrences of 10." << endl;

`count_if` is like `count`
and `find_if`. It counts every element in the range that
satisfies the predicate.

size_t count_if(InputIterator begin, InputIterator end, Predicate pred);

The following code, using the same `evenPred` function
object defined above, counts
the even numbers in the given range:

int numEvens = count_if(v.begin(), v.end(), evenPred); cout << "Found " << numEvens << " even numbers" << endl;

Several algorithms are primarilly for working with containers of numbers.

`max_element` and `min_element`
find the maximum and minimum element of a range of elements in a
container. Like `find` and `find_if`, they return an
iterator pointing to the element found. If none is found, the
iterator will point to the end of the range.

ForwardIterator max_element(ForwardIterator begin, ForwardIterator end) ForwardIterator min_element(ForwardIterator begin, ForwardIterator end)

Notice that `max_element` and `min_element` rquire
`ForwardIterator`'s, not just `InputIterator`'s. This
is because they have to save the iterator of the largest or smallest
element found, and `InputIterator`'s don't support saving.

Here is a simple usage:

vector<int> v; vector<int>::iterator result; ... cout << "Looking for max number" << endl; result = max_element(stats.begin(), stats.end()); if (result != stats.end()) cout << "Found " << (*result) << endl;

These versions of `max_element` and `min_element` uses
`operator<` to find the biggest and smallest items. You can also
pass a function object to `max_element` and
`min_element`. The function should return true when the second
argument is "bigger" in some sense than the first argument.

ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, Compare pred) ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Compare pred)

Here's code to find the largest odd number:

class MaxOdd { public: bool operator() (int theMax, int x) { return ((x % 2) == 1) && (x > theMax); } }; ... cout << "Looking for max odd" << endl; result = max_element(stats.begin(), stats.end(), MaxOdd()); if (result != stats.end()) cout << "Found " << (*result) << endl;

Can you think of a situation in which the above code might return an even number?

`accumulate` adds up a range of
elements in a container.

T accumulate(InputIterator begin, InputIterator end, T initial_value)

To add up all the numbers in our vector,

cout << "Sum of all the numbers is " << accumulate(stats.begin(), stats.end(), 0) << endl;

The third argument, 0 in this case, is the initial value for the sum.

The above call to `accumulate` uses `operator+` but
you can pass a function as a fourth argument to change this. That
function should take two arguments. The first argument will be the "sum" so
far, starting with the initial value given. Each element will be
passed in turn to the second element.

T accumulate(InputIterator begin, InputIterator end, T initial_value, BinaryOperation op)

So, to add up just the odd numbers:

class SumOdd { public: int operator() (int sum, int y) { return ((y % 2) == 1) ? sum + y : sum; } }; ... cout << "Sum of all the odd numbers is " << accumulate(stats.begin(), stats.end(), 0, SumOdd()) << endl;

Copying algorithms copy ranges of elements from one container to another.

OutputIterator copy(InputIterator begin1, InputIterator end1, OutputIterator begin2) OutputIterator remove_copy(InputIterator begin1, InputIterator end1, OutputIterator begin2, const T& value) OutputIterator remove_copy_if(InputIterator begin1, InputIterator end1, OutputIterator begin2, Predicate pred) OutputIterator transform(InputIterator begin1, InputIterator end1, OutputIterator begin2 UnaryOperation op)

`copy()` copies the elements in the first range to the
output iterator given. `remove_copy()` does the same thing
except that it doesn't copy anything `==` to `value`.
`remove_copy_if()` is the same as `remove_copy()`
except that it doesn't copy anything satisfying the predicate.
`transform()` is the same as `copy()` except that it
applies `op` to each element and stores the result.

Why is there no
`copy_if()`? Stroustrup apologies for accidentally leaving out
this algorithm (The C++ Programming Language, 3rd Ed., p 530). He
gives the following definition, which shows how easy it is to define
many of the basic generic algorithms:

template<class In, class Out, class Pred> Out copy_if(In begin, In end, Out dest, Pred p) { while (begin != end) { if (P (*begin)) *dest++ = *begin; ++end; } return dest; }

Of course, you can always just use `remove_copy_if()` with
a predicate that selects what you don't want to copy.

If the output iterator is a normal iterator pointer to a container, then the elements being copied replace the existing elements in the output container. It is an error if there's not enough room in the output container.

If the output iterator is an insertion iterator, then the elements being copied are inserted into the container.

If the output iterator is an ostream iterator, then the elements being copied are written to the output stream.

Here's an example of copying all the odd numbers from a vector to
a new vector, using a function object `evenPred` that returns
true for even numbers:

remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), evenPred);

Here's an example of using `transform`. Assume that the
vector `sv` contains `Employee` structures that have
integer `idNum` values. We can copy those values into a simple
vector of integers `iv` thus:

int getIdNum(const Employee &e) { return e.idNum; } transform(sv.begin(), sv.end(), back_inserter(iv), getIdNum);

The STL has a rich assortment of sorting-related algorithms. Just a few are described here.

`sort` sorts a range of elements in a container.

void sort(RandomAccessIterator begin, RandomAccessIterator end)

This is pretty obvious. Given a container that support random
access iterators, it sorts the elements in the range specified by the
iterators, using `operator<` as overloaded by the
underlying elements.

To sort the vector `v`, we just say

sort(v.begin(), v.end());

Not surprisingly, instead of using `operator<` you can
give a specific comparison function to use:

void sort(RandomAccessIterator begin, RandomAccessIterator end, Compare comp)

`sort` is guaranteed to be O(n log n) on the average, but
neither stable nor immune to worst case behavior of O(n^{2}).

To get a stable sort, which will also be O(n log n) but probably
slower than `sort`, use `stable_sort`. It takes the
same arguments as `sort`.

Finally, if you only need the first N elements, e.g., the 5 biggest numbers, you can partially sort the container and save time:

void partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end) void partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Compare comp)

This says "sort the elements in the range until you've gotten the
elements from `begin` to `middle` sorted." It's left
undetermined what order the elements from `middle` to
`end` are in.

For example, to get the first 5 elements sorted:

partial_sort(v.begin(), v.begin()+5, v.end());

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