Lecture Notes for SE 598, Data Structures and Algorithms

21 June 2000, Generic Algorithms, Part 1

1. functional parameters

   1. terms

      1. functional parameter - a function passed in as an argument to another function

      2. binary, unary, nilary functions - functions taking two, one, or zero arguments

      3. predicate - a function returning a boolean value

         1. less than (<) is a binary predicate

         2. not (!) is a unary predicate

   2. some generic functions require a functional parameter

      1. generate(s, e, f)

         1. semantics: for (i = s; i < e; i++) *i = f()

         2. example: generate(v.begin(), v.end(), random)

   3. some generic functions take an optional functional parameter; that is, the functional parameter has a default value

      1. sort(s, e, f)

      2. f is an optional predicate parameter that determines if the first argument is less than the second argument

      3. the default argument is the standard less-then predicate

   4. some generic algorithms require special kinds of functional parameters

      1. sort() actually takes a Comparison, which is a binary predicate with special properties

         1. less-than (<) and greater-than (>) are Comparisons

         2. at-most (<=) and at-least (>=) are not Comparisons

      2. passing the wrong kind of function usually results in errors

      3. unfortunately, it is impossible to catch incorrect functions at compile time; the errors usually manifest themselves as run-time errors

   5. from where do functional parameters come

      1. the stl gives you lots

         1. arithmetic: plus<T>, minus<T>

         2. comparisons: equal_to<T>, greater_than<T>

         3. logical: and<T>

         4. these are actually function objects

         5. the parameter type T must define the associated operator

            1. #include <vector>
               #include <numeric>
               #include <functional>
               #include <stdlib.h>
               
               class test {
                 public:
                   test operator+(const test & t) const {
                     return *this;
                     }
                 };
               
               int main(void) {
                 vector<test> iv(10);
                 accumulate(iv.begin(), iv.end(), test(), plus<test>());
                 return 0;
                 }
               

2. naming conventions

   1. copy and in-place generic algorithms

      1. example - making a reversed copy of a dequeue

         1. copy(d1.begin(), d1.end(), d2.begin()); reverse(d2.begin(), d2.end())

         2. this is expensive - touches the data twice

      2. the stl provides a number of copy-and-operate generic algorithms to eliminate the extra work done by copying

         1. these generic algorithms have _copy as the last part of their name

         2. reverse_copy(d1.begin(), d1.end(), d2.begin())

      3. not all generic algorithms have copying versions

         1. sorting is much more expensive than copying, so there's no advantage to combining copying and sorting

         2. it makes sense to provide copying versions of generic algorithms that are about as expensive as copying is

            1. unique() is as expensive as copying, so unique_copy() is available for use

            2. but not always - random_shuffle() is about as expensive as copying, but there is no random_shuffle_copy()

   2. value-function generic algorithms

      1. sometimes a generic algorithm can take either a value or a function (usually a predicate)

         1. example: remove(s, e, v) - remove all occurrences of the value v from the iterator range (s, e)

         2. example: remove(s, e, f) - remove all occurrences of the value v from the iterator range (s, e) where f(v) is true

      2. however, it is usually impossible for a c++ compile to distinguish between a parameter used as a value and a parameter used as a function

      3. the _if naming convention comes to the rescue

         1. generic algorithms ending in _if use the value parameter as a function

            1. remove_if(s, e, f)

            2. replace(s, e, v1, v2) - replace all occurrences of the value v1 in the iterator range (s, e) with the value v2

            3. replace_if(s, e, f, v) - replace all values v in the iterator range (s, e) with the value v2 when f(v) is true

This page last modified on 27 June 2000.