Function Objects (aka Functors)

The need for function objects

Consider the following function for finding the "minimum" of an array of strings, along with a program making use of it.

#include <string>
using namespace std;

string Minimum(string* A, int n) {
  string m = A[0];
  for(int i = 1; i < n; i++)
    if (A[i] < m)
      m = A[i];
  return m;
}

#include <iostream>
#include "Ex1.h"

int main() {
  cout << "Enter 5 strings: ";
  string A[5];
  for(int i = 0; i < 5; i++)
    cin >> A[i];

  cout << "The \"minimum\" alphabetically is: ";
  string m = Minimum(A,5);
  cout << m << endl;

  return 0;
}

$ g++ -o go Ex1main.cpp
$ go
Enter 5 strings: the Hope azure always Zoo
The "minimum" alphabetically is: Hope
$

Notice that the "minimum" element we get is the element that's first in alphabetical order - counting capitals as coming before lower-case. Why does it work this way? Well, because that's what the operator< has been overloaded to do for class string. In SI204 you observed that this problem of finding the minimum really depends on how we define when one object comes before another. Because we're using operator< here it's done one way, but we could do it another way - say by the length of strings, or perhaps by alphabetical order ignoring capitalization, or perhaps by how different the string is from some reference string.

So we come up with this idea that we use a function bool before(string, string) inside of our Minimum function instead of simply using operator<. That way the user of the Minimum function can define before for themselves and use whatever ordering they want. The following program uses that scheme to return the smallest element by string length:

#include <string>
using namespace std;

bool before(string a, string b);

string Minimum(string* A, int n) {
  string m = A[0];
  for(int i = 1; i < n; i++)
    if (before(A[i],m))
      m = A[i];
  return m;
}

#include <iostream>
#include "Ex2.h"

bool before(string a, string b) {
  return a.length() < b.length();
}

int main() {
  cout << "Enter 5 strings: ";
  string A[5];
  for(int i = 0; i < 5; i++)
    cin >> A[i];

  cout << "The \"minimum\" by length is: ";
  string m = Minimum(A,5);
  cout << m << endl;

  return 0;
}

$ g++ -o go Ex2main.cpp
$ go
Enter 5 strings: the Hope azure always Zoo
The "minimum" by length is: the
$

OK, this sounds like a pretty good and flexible way to define the Minimum function, but it breaks down when we want to do just a little bit more. What if I wanted to augment the above program so that it would print out both the the minumum alphabetically and the minimum by length? Can't do it, can we? You have to commit to just one definition of before! What we really need is a mechanism for passing the particular function that we want to use as before to each call to Minimum. The before function should be a parameter of the Minimum function!

Function Objects (Functors)

The mechanism we'll use to achieve our goal of passing the before function as a parameter to Minimum is the function object. Function objects are not actually anything magical and new, rather they are a convenient convention for using what we already know about operator overloading to create objects that can be used as functions - the advantage being that objects can be passed around as parameters to functions!

So, how do we make an object (remember, an object is something that has type and value - like int variables or variable of some class we define) that can be used like a function? Well, the ()'s operator (aka the "function call operator" or operator()) can be overloaded just like all of the others, that's how. An example should make this clearer. In the following, we'll define a class Cube, such that objects of type Cube behave like a function that takes a doubleargument and returns its cube.

#include <iostream>
using namespace std;

class Cube {
public:
  double operator()(double x) {
    return x*x*x;
  }
};

int main() {
  // Initialize some variables
  Cube var1;
  double a, b;
  a = 2.5;

  // Call operator() as a member function
  b = var1.operator()(a);
  cout << "b = " << b << endl;

  // Call operator() as an operator - These two calls are identical!
  b = var1(a);
  cout << "b = " << b << endl;

  return 0;
}

$ g++ -o go Ex4.cpp
$ go
b = 15.625
b = 15.625
$

Because of the way we've overloaded operator() for the class Cube, an object of type Cube (like var1 in the program) acts like a function that takes a double argument and returns its cube.

Now, we want function objects for our Minimum problem that behave like the before function, i.e. taking two strings as argument and returning true if the first should come before the second and false otherwise. A class defining function objects that compare strings by length might look like this:

class CompByLength {
public:
  bool operator()(string a, string b) {
    return a.length() < b.length();
  }
};

An object of type CompByLength can now be used as a function that takes two strings and returns a bool.

We'd define a different class for function objects that compare strings alphabetically. The following class defines function objects that compare strings alphabetically ignoring upper/lower-case distinctions.

class CompAlphabetical {
  void makelower(string &s) {
    for(int i = 0; i < s.length(); i++)
      if ('A' <= s[i] && s[i] <= 'Z')
        s[i] = s[i] - 'A' + 'a';
  }
public:
  bool operator()(string a, string b) {
    makelower(a);
    makelower(b);
    return a < b;
  }
};

Finishing off the Minimum example

Now we're ready to finally define our minimum function in such a way that the user passes a function object to Minimum, which it will then use to decide when one string in the array should come before another. The thing to keep in mind is that the type of this third parameter is unknown. It could be of type CompByLength, it could be of type CompAlphabetical, it could be of some other type that we haven't even defined yet! When we don't know the type of a parameter to a function, we make that unknown type a template parameter.

In the following, we define Minimum so that it takes a third parameter whose type is given by a template variable. The main program using this function instantiates that template variable first with an object of typeCompByLength and then with an object of type CompAlphabetical.

#include <string>
using namespace std;

template<class CompType>
string Minimum(string* A, int n, CompType before) {
  string m = A[0];
  for(int i = 1; i < n; i++)
    if (before(A[i],m))
      m = A[i];
  return m;
}

#include <iostream>
#include "Ex3.h"

class CompByLength {
public:
  bool operator()(string a, string b) {
    return a.length() < b.length();
  }
};

class CompAlphabetical {
  void makelower(string &s) {
    for(int i = 0; i < s.length(); i++)
      if ('A' <= s[i] && s[i] <= 'Z')
    s[i] = s[i] - 'A' + 'a';
  }

public:
  bool operator()(string a, string b) {
    makelower(a);
    makelower(b);
    return a < b;
  }
};

int main() {
  cout << "Enter 5 strings: ";
  string A[5];
  for(int i = 0; i < 5; i++)
    cin >> A[i];

  cout << "The \"minimum\" by length is   : ";
  CompByLength C1;
  string m1 = Minimum(A,5,C1);
  cout << m1 << endl;


  cout << "The alphabetical \"minimum\" is: ";
  CompAlphabetical C2;
  string m2 = Minimum(A,5,C2);
  cout << m2 << endl;

  return 0;
}

$ g++ -o go Ex3main.cpp
$ go
Enter 5 strings: the Hope azure always Zoo
The "minimum" by length is   : the
The alphabetical "minimum" is: always
$

Now we have a Minimum function that can be used no matter what concept of "before" the user might want! Even different concepts of "before" within the same program!

The power of function objects

You start to realize the true power of function objects when you realize that they are class objects like any other, which means that they may have data members. This means that they can do some things you can't really do with regular functions. In the program below, we'll use the same Minimum function as above but with a different class of function objects for comparison. The class we'll use will compare two strings by the number of positions in which they differ from some reference string. The user will enter the reference string, so it can't be hard-coded into the program in any way. Since we're using the same Minimum function as before, our function object can only take two parameters, so the reference string can't be passed as an extra parameter. Instead, the reference string will be stored as a data member of the function object.

The following program reads a string from the user and prints out the word from a large dictionary file that differs from the user's string in the fewest positions.

#include <string>
using namespace std;

/******************************************************
 * This class defines functions objects which are
 * initialized with a reference string s, and which
 * are a "function" for comparing two strings based on
 * the number of characters that are different from s.
 ******************************************************/
class CompWithString {
  // Data member ref is a reference string
  string ref;

  // Returns the # of positions in which w and ref differ
  int numdiffs(string w) {
    int k = abs(ref.length() - w.length());
    for(int i = 0; i < ref.length() && i < w.length(); i++)
      if (ref[i] != w[i])
        k++;
    return k;
  }

public:
  CompWithString(string w) {
    ref = w;
  }

  // determines if a differs from ref in fewer places
  // than b differs from ref
  bool operator()(string a, string b) {
    return numdiffs(a) < numdiffs(b);
  }
};

#include <iostream>
#include <fstream>
#include "Ex3.h" // defines Minimum function
#include "Ex5.h" // defines CompWithString class

int main() {
  // Read in the 102305 words in dictionary file
  ifstream IN("/usr/share/dict/american-english");
  const int N = 102305;
  string A[N];
  for(int i = 0; i < N; i++)
    IN >> A[i];

  // Get word from user
  cout << "Enter word: ";
  string wrd;
  cin >> wrd;

  // Print out word in dictionary closest to user's word
  CompWithString C(wrd);
  cout << "Minimum with respect to \"" << wrd << "\" is \""
       << Minimum(A,N,C) << "\"." << endl;

  return 0;
}

$ g++ -o go Ex5main.cpp
$ go
Enter word: odange
Minimum with respect to "odange" is "orange".
$

Hopefully you see that what we've just implemented pretty effortlessly is a rudimentary spell-checker!