The algorithms delivered with the library are divided into four groups:

group algorithm type

1 mutating sequence operations 2 non-mutating sequence operations 3 sorting and related operations 4 generalized numeric operations

*Table 6: STL algorithm types*

Group 1 contains algorithms which don't change (mutate) the order of the elements in a container, this has not to be true for algorithms of group 2.

The algorithm `for_each` of group 1 takes two iterators
and a function `f` of type `Function` as arguments:

template <class InputIterator, class Function> Function for_each (InputIterator first, InputIterator last, Function f);

The template argument `f` of type `Function` must
not be mixed up with a "pure" C++ function, because
such a function can only be used in a roundabout way (see section 4.4.3).
The template
function `for_each` expects a *function object* (section 2.2)
as argument. `f` is assumed not to apply any non-constant
function through the dereferenced iterator.

`for_each` applies f to the result of dereferencing every
iterator in the range `[first, last)` and returns `f`.
If `f` returns a value, it is ignored. The following example
computes the sum of all elements in the range `[first, last)`.

template <class T> class sum_up { public: static T sum; void operator() (const T& value) { sum += value; } const T& read_sum() { return sum; } }; int sum_up<int>::sum; void main(void) { deque<int> d (3,2); sum_up<int> s; for_each (d.begin(), d.end(), s); cout << s.read_sum(); }

__Output:__ *6*

**Note:** To use a `deque` include `deque.h`

Group 1 also contains an algorithm

template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);

`find` takes a range and a reference to a value of arbitrary
type. It assumes that `operator==` for the value type of
the iterator and `T` is defined. Additionally to `find`
an algorithm named `find_if` is provided, which takes a*
*predicate `pred` of type `Predicate`.

template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

`find_if` (like `find`) returns the first iterator
`i` in the range `[first, last)`, for which the
following condition holds: `pred(*i) = true`. If such an
iterator doesn't exist, a past-the end iterator is returned.

template <class T> class find_first_greater { public: find_first_greater() : x(0) {} find_first_greater(const& xx) : x(xx) {} int operator() (const T& v) { return v > x; } private: T x; }; vector<int> v; // fill vector with 1 2 3 4 5 vector<int>::iterator i = find_if (v.begin(), v.end(), find_first_greater<int> (3)); i != v.end()? cout << *i : cout << "not found";

__Output:__ *4*

Generally, if there is a version of an algorithm which takes a predicate, it gets the name of the algorithm with the suffix

Some algorithms, like `adjacent_find`, take a binary predicate
`binary_pred` of type `BinaryPredicate`. `adjacent_find`
returns the first iterator `i`, for which the following
condition holds: `binary_pred (*i, *(i+1)) == true`.

template <class InputIterator, class BinaryPredicate> InputIterator adjacent_find(InputIterator first, InputIterator last, BinaryPredicate binary_pred);

For example, if you want to find the first pair of values, whose product is odd, you could write this:

template <class T> class prod_odd { public: int operator() (const T& v1, const T& v2) { return v1%2 != 0 && v2%2 != 0; } }; list<int> l; // fill list with 2 9 6 13 7 list<int>::iterator i = adjacent_find (l.begin(), l.end(), prod_odd<int>()); if (i != l.end()) { cout << *i << " "; i++; cout << *i++; } else cout << "not found";

__Output:__ *13 7*

Algorithms can work

template <class Iterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if(Iterator first, Iterator last, OutputIterator result, Predicate pred, const T& new_value);

All the operations in group 3 have two versions. One that takes
a function object `comp` of type `Compare` and another
that uses `operator<` to do the comparison.
`operator<` and `comp`,
respectively, have to induce a total ordering relation on the
values to ensure that the algorithms work correctly.

vector<int> v; // fill v with 3 7 5 4 2 6 sort (v.begin(), v.end() ); sort (v.begin(), v.end(), less<int>() ); sort (v.begin(), v.end(), greater<int>() );

__Output:__ *2 3 4 5 6 7*

__Output:__ *2 3 4 5 6 7*

__Output:__ *7 6 5 4 3 2*

Since the library provides function objects for all of the comparison operators in the language we can use

All the provided function objects are derived either from `unary_function`
or from `binary_function` to simplify the type definitions of the
argument and result types.

template <class Arg, class Result> struct unary_function { typedef Arg argument_type; typedef Result result_type; };

template <class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };

STL provides function objects for all of the arithmetic operations
in the language. `plus`, `minus`, `times`,
`divides` and `modulus` are binary operations whereas
`negate` is a unary operation. As examples, look at `plus`
and `negate`, the other functions objects are defined accordingly.

template <class T> struct plus : binary_function<T, T, T> { T operator()(const T& x, const T& y) const { return x + y; } };

template <class T> struct negate : unary_function<T, T> { T operator()(const T& x) const { return -x; } };

The mentioned comparison function objects are` equal_to`,
`not_equal_to`, `greater`, `less`, `greater_equal`
and `less_equal`, they are all binary function objects.
`less` shall serve as example.

template <class T> struct less : binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x < y; } };

Additionally, the binary function objects `logical_and`
and `logical_or` exist, `logical_not` is a unary
function object.

template <class T> struct logical_and : binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x && y; } };

template <class T> struct logical_not : unary_function<T, bool> { bool operator()(const T& x) const { return !x; } };

The rest of the function object implementations can be found in [2], 6.

In group 4, the algorithm `accumulate` takes a binary operation
`binary_op` of type `BinaryOperation`. The algorithm
`accumulate` does the same as `for_each` used with
the function object `sum_up` (presented earlier in this
section).

template <class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init);

For each iterator `i` in `[first, last)`, `acc
= acc + *i` is computed, then `acc` is returned. `acc`
can be initialized with a starting value. Instead of `operator+`,
an arbitrary binary operation can be defined by the user, or a
STL function object can be used.

vector<int> v; v.push_back (2); v.push_back (5); cout << accumulate (v.begin(), v.end(), 10, divides<int>() );

__Output:__ *1*

I want to present an example which implements a spell-checker. For this purpose we assume the following:

- The dictionary is stored in a file
- The text to check is stored in a file
- The words of the text should be checked against dictionary
- Every word not found or misspelled should be displayed

We decide to use a non-associative container (see section 4.1, introduction), which holds the dictionary. The dictionary is assumed to be sorted. Now, we express the spell-checker functionality in pseudo code.

for every word in text check against dictionary if not in dictionary write to output

This pseudo code can be expressed in different way:

copy every word of text to output that is not in the dictionary

The last pseudo code variation can more directly be translated into a STL program. Since we need a mechanism that tells us if a word is or is not in the dictionary, we encapsulate this functionality in a function object.

template <class bidirectional_iterator, class T> class nonAssocFinder { public: nonAssocFinder(bidirectional_iterator begin, bidirectional_iterator end) : _begin(begin), _end(end) {} bool operator() (const T& word) { return binary_search(_begin, _end, word); } private: bidirectional_iterator _begin; bidirectional_iterator _end; };

The function object `nonAssocFinder` is initialized with
the iterators `begin` and `end` that have to be at least
of the bidirectional iterator category. The function call operator
takes a word and returns a boolean value, which states if the
word has been found in the dictionary (the type `bool`
is defined by STL). This boolean value is returned by the STL
algorithm `binary_search`.

template <class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

The first thing we do in our program is to define a dictionary
as a vector of type `string` and fill it out of an input
stream.

typedef vector<string> dict_type; ifstream dictFile("dict.txt"); ifstream wordsFile("words.txt"); dict_type dictionary; copy (istream_iterator<string, ptrdiff_t>(dictFile), istream_iterator<string, ptrdiff_t>(), back_inserter(dictionary));

**Note:** To use the `string` type include `cstring.h`

Then we use the STL algorithm `remove_copy_if` to achieve
the functionality wanted.

template <class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

`remove_copy_if` writes all elements referred to by the
iterator `i` in the range `[first, last)` to the
output iterator `result`, for which the following condition
does *not* hold:

`pred(*i) == true`. The algorithm returns the end of the
resulting range. The rest of the spell-checker program proves
to be a single statement.

remove_copy_if ( istream_iterator<string, ptrdiff_t>(wordsFile), istream_iterator<string, ptrdiff_t>(), ostream_iterator<string>(cout, "\n"), nonAssocFinder<dict_type::iterator, dict_type::value_type> (dictionary.begin(), dictionary.end()));

`remove_copy_if` reads words from the input stream `wordsFile`
and writes the words for which `nonAssocFinder` returns
`false` (i.e. which are either not found or misspelled)
to `cout`.

Because STL provides its own `operator<`, `operator<`
for the `string` type must be excluded from `cstring.h`
when using Borland C++ (this is shown in section 3.3).
To enable the compiler to compare strings, a *template specialization*
for strings has to be provided, which looks exactly like the one
from `cstring.h`. Use it to make the spell-checker example
work.

inline int operator< (const string far& s1, const string far& s2) { return s1.compare(s2) < 0; }

The components used are:

- algorithms:
`copy`and`remove_copy_if` - container:
`vector` - user defined: function object
`nonAssocFinder`

Now you should have the basics to understand the chapter on algorithms in [2], 10. Since this document is very theoretical, the algorithms in combination with a description and examples can be found in [4], 6. A complete STL example can be found in [4], 5.

Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996