Notes on Function Pointers

Idea: treat functions like other objects

If we have a function foo with a prototype:

  bool foo(int x, int y);

we want to be able to say:

  f = foo;

for a suitable declaration of f and then use f wherever we might use foo.

Pointers to functions

f isn't really a function - it's a pointer to a function. Function pointers can be declared as:

  <return type>  (* <var>)(<argument types>)

as in:

  bool (*f) (int, int);

The notation looks like a function prototype, except *f appears in parentheses. Notation is a little confusing, but we can use typedefs to make it more clear:

  typedef bool (* int_comparison_fun) (int,int);

Now we can write:

  int_comparison_fun f;
  f = foo;

Functions as arguments to other functions

More important than assigning function pointer variables to point to various functions, we can use function pointers to pass functions as arguments into other functions. For example:

void sort(int A[], size_t n, bool (*compare)(int,int))
{
  int min; 
  size_t k,minIndex;

  for(k=0; k+1 < used; k++) { 
    minIndex = k; 
    min = data[k]; 
    for(size_t j=k+1; j < used; j++) { 
      if (compare(data[j],min)) {
        min = data[j];
        minIndex = j;
      }
    }
    data[minIndex] = data[k]; 
    data[k] = min; 
  }
}

Using the typedef, this function can be declared as:

void sort(int A[], size_t n, int_comparison_fun compare);

Squaring a list of integers

We can make functions more parametric - and allow for more reuse, by passing functions as arguments. This works particularly well with iterators. For example, suppose we have a list of integers:

List<int> L;

We would like to be able to write C++ code that will create a coresponding list of the squares of those integers:
[1, 12, 3] ==> [1, 144, 9]
Using external iterators we might write:

List<int> squareList(const List<int> L)
{
  ListIter<int> iter(L);
  List<int> newList;

  for(; !iter.isEnd(); iter.advance()) {
    int i = iter.current();
    newList.append(i * i);
  }
  return newList;
}

New int lists from old

Now suppose we would like to create a list consisting of twice the corresponding values in the original list:
[1, 12, 3] ==> [2, 24, 6]
Rather than rewriting code very similar to what we have written already, we can reuse the old code, by adding a function argument:

List<int> map(const List<int> L, int (*f)(int))
{
  ListIter<int> iter(L);
  List<int> newList;

  for(; !iter.isEnd(); iter.advance())
    newList.append(f(iter.current()));

  return newList;
}

and then writing two trivial functions:

  int square(int i) { return(i*i); }
  int dbl(int i) { return(2*i); }

We can now write:

  map(L, square);
  map(L, double);

A map function template

Finally, we can write a map function template so that it can be applied over lists of anything:

template <class T>
List<T>* map(const List<T>& source, T (*f)(T))
// maps a list to another list, applying f to each element
{
  ListIter<T> iter(source);
  List<T> *newList = new List<T>;

  for(; !iter.isEnd(); iter.advance())
    newList->append(f(iter.current()));
  
  return newList;
}

Note the use of pointers in the return type to avoid redundant copy construction.