Function Objects

Last time, we saw iterators, which are a common interface for traversing over the elements of a sequence. For instance, the following function template works over any sequence of integers, determining if there is and odd element in the sequence:

// REQUIRES: begin is before or equal to end
// EFFECTS:  Returns true if any element in the sequence
//           [begin, end) is odd.
template <typename Iter_type>
bool any_of_odd(Iter_type begin, Iter_type end) {
  for (Iter_type it = begin; it != end; ++it) {
    if (*it % 2 != 0) {
      return true;
    }
  }
  return false;
}

We can then use any_of_odd() with any sequence type, as long as the elements are integers:

List<int> list;
vector<int> vec;
int array[10];
...
cout << any_of_odd(list.begin(), list.end()) << endl;
cout << any_of_odd(vec.begin(), vec.end()) << endl;
cout << any_of_odd(array, array + 10)) << endl;

The template is generic over the iterator type, but it is not generic over the condition that an element must meet – it only searches for odd elements and no other characteristic. Suppose we wanted instead to determine whether the sequence contains an even element. We could write an any_of_even() template:

// REQUIRES: begin is before or equal to end
// EFFECTS:  Returns true if any element in the sequence
//           [begin, end) is even.
template <typename Iter_type>
bool any_of_even(Iter_type begin, Iter_type end) {
  for (Iter_type it = begin; it != end; ++it) {
    if (*it % 2 == 0) {
      return true;
    }
  }
  return false;
}

This code is almost exactly the same as that for any_of_odd(); the only difference is the computation done in the test of the conditional. Most of the code is duplicated, which is undesirable. Furthermore, if we wanted to determine whether a sequence contained an element that met some other condition, say whether an element is positive, we would have to write additional function templates that duplicate code.

Our general strategy for avoiding code duplication in a procedural abstraction is to introduce parameters for the pieces that differ. For a value that differs, we add a function parameter:

int power3(int x) {
  int result = 1;
  for (int i = 0; i < 3; ++i) {
    result *= x;
  }
  return result;
}

int power4(int x) {
 int result = 1;
  for (int i = 0; i < 4; ++i) {
    result *= x;
  }
  return result;
}

int power(int x, int n) {          // add parameter to generalize
  int result = 1;
  for (int i = 0; i < n; ++i) {
    result *= x;
  }
  return result;
}

int main() {
  for (int i = 0; i < 10; ++i) {
    cout << power(42, i);          // supply desired argument
  }
}

When it is a type that differs, we make the function a template and introduce a template parameter:

int max_int(int x, int y) {
  return x < y ? y : x;
}

Card max_card(const Card &x, const Card &y) {
  return x < y ? y : x;
}

template <typename T>            // add template parameter to generalize
T max(const T &x, const T &y) {  // pass objects of template-parameter type
                                 //   by reference
  return x < y ? y : x;
}

int main() {
  cout << max(3, -1) << endl;    // template parameter deduced from arguments
  cout << max(Card(Card::RANK_TWO, Card::SUIT_SPADES),
              Card(Card::RANK_TOW, Card::SUIT_HEARTS)) << endl;
}

For a generic any_of(), however, it is an actual computation that differs: *it % 2 != 0 for odd numbers, *it % 2 == 0 for even numbers, *it > 0 for positive numbers, and so on. We can use a function to represent such a computation:

bool is_odd(int x) {
  return x % 2 != 0;
}

bool is_even(int x) {
  return x % 2 == 0;
}

bool is_positive(int x) {
  return x > 0;
}

Once we have a function, the compiler translates it into machine code, which is placed in memory in the text segment when the program runs.

Figure 75 The memory for a program includes a segment that stores the program’s code.

Since the code is in memory, we can construct a pointer to it:

bool (*func)(int) = &is_odd;
func = &is_even;

As the examples above demonstrate, we can apply the address-of operator to a function to obtain its address, just like for an object. Unlike an object, however, the address-of operator is optional:

func = is_positive;

The compiler implicitly inserts the operator for us.

We can call a function through a pointer by first dereferencing the pointer:

bool (*func)(int) = is_odd;
(*func)(-2);                 // returns false

Like with the address-of operator, the compiler can implicitly insert this dereference for us:

func(-2);                    // returns false

Function-Pointer Types

Before we proceed to implement a generic any_of(), let us examine the syntax of a function pointer more closely.

bool (*func)(int);

C++ declarations are generally read from right to left. However, the parentheses around *func associate the * symbol with the name func. Without the parentheses, we would have the following:

bool *func2(int);

This is a declaration of a function called func2 that takes in an int and returns a pointer to a bool – the * is associated with the return type rather than the name func2.

With the parentheses, the * has the same meaning as for other variables: it indicates that the variable we are declaring is a pointer. Thus, func is a pointer. The rest of the declaration tells us what kind of pointer it is: a pointer to a function that takes an int as a parameter and returns a bool.

To declare an appropriate function pointer, we can use the following steps:

• Start with a function signature:

  int max_int(int x, int y);
  

• Remove the parameter names, which serve only as documentation in a declaration:

  int max_int(int, int);
  

• Replace the function name with a variable name and the * symbol to indicate it is a pointer, surrounded by parentheses:

  int (*func3)(int, int);
  

The result is that func3 is a pointer to a function that takes two ints and returns an int.

Function-Pointer Parameters

We can now write a generic any_of() that is parameterized both by an iterator type as well as a function to test an element:

template <typename Iter_type>
bool any_of(Iter_type begin, Iter_type end, bool (*func)(int)) {
  for (Iter_type it = begin; it != end; ++it) {
    if (func(*it)) {
      return true;
    }
  }
  return false;
}

Since different iterators may have different types, we use a template parameter to allow an arbitrary kind of iterator. For the test of whether an element satisfies a condition, we add a function parameter that is a pointer to a function. We call it using parentheses like any other function, and the compiler automatically dereferences the pointer to get to its code.

We can then specify which function to use when calling any_of():

List<int> list;
vector<int> vec;
int array[10];
...
cout << any_of(list.begin(), list.end(), is_odd) << endl;
cout << any_of(vec.begin(), vec.end(), is_even) << endl;
cout << any_of(array, array + 10, is_positive)) << endl;

The compiler implicitly takes the address of a function when we pass it to a function pointer.

Functions that take in an item and return a truth value are quite common, and they are called predicates. Thus, a better name for the function-pointer parameter in any_of() would be pred rather than func.

// REQUIRES: begin is before or equal to end
// EFFECTS:  Returns true if pred returns true when applied to at
//           least one element in the sequence [begin, end).
template <typename Iter_type>
bool any_of(Iter_type begin, Iter_type end, bool (*pred)(int)) {
  for (Iter_type it = begin; it != end; ++it) {
    if (pred(*it)) {
      return true;
    }
  }
  return false;
}

Functors

With any_of() and is_positive(), we can determine whether a sequence contains an element that is greater than zero. What if we are interested in other thresholds, such as 32 or 212? We don’t want to write separate functions for each value, as this duplicates code:

bool greater32(int x) {
  return x > 32;
}

bool greater212(int x) {
  return x > 212;
}

Since what differs is just a value, we can write a function that has a parameter for the threshold value:

bool greater(int x, int threshold) {
  return x > threshold;
}

Unfortunately, we cannot use this with any_of(): it requires a pointer to a function that takes in one argument, not two:

main.cpp:29:11: error: no matching function for call to 'any_of'
  cout << any_of(arr, arr + SIZE, greater) << endl;
          ^~~~~~
main.cpp:13:6: note: candidate function not viable: no known conversion from
      'bool (int, int)' to 'bool (*)(int)' for 3rd argument
bool any_of(Iter_type begin, Iter_type end, bool (*pred)(int)) {
     ^
1 error generated.

Furthermore, we need some way of specifying the threshold, and passing the greater() function directly to any_of() does not do so. What we need is something that internally stores the threshold value and is callable with just one argument.

More specifically, we want a first-class entity, which is an entity that supports the following:

• It can store state.

• It can be created at runtime.

• It can be passed as an argument or returned from a function.

Unfortunately, functions are not first-class entities in C++: they cannot be created at runtime, and they are very limited in how they can store information. [1]

[1]

A function may have a static local variable, but it can only store a single value at a time. We need an arbitrary amount of storage – for instance, we may have any number of threshold values we care about for greater(), so we need a way of creating multiple copies of the function that each have their own stored threshold value.

Class types, on the other hand, do define first-class entities. A class-type object can store state in member variables, can be created at runtime, and can be passed between functions. So a class type could satisfy our needs, as long as there were a way to call it like a function. In fact, C++ does allow a class-type object to be called if the class overloads the function-call operator. We refer to such a class as a functor.

A functor is a class type that provides the same interface as a function, much like an iterator is a class type that provides the same interface as a pointer. The following is a GreaterN class that stores a threshold and is also callable with a single argument:

class GreaterN {
public:
  // EFFECTS: Creates a GreaterN with the given threshold.
  GreaterN(int threshold_in) : threshold(threshold_in) {}

  // EFFECTS: Returns whether or not the given value is greater than
  //          this GreaterN's threshold.
  bool operator()(int x) const {
    return x > threshold;
  }

private:
  int threshold;
};

The function-call operator must be overloaded as a member function, so it has an implicit this pointer that allows us to access a member variable. We have declared the this pointer as a pointer to const, since the function does not modify the GreaterN object. We also get to decide what the parameters are, as well as the return type. We have chosen a single parameter of type int and a bool return type, since we want a GreaterN object to act as a predicate on ints.

We can create and use GreaterN objects as follows:

int main() {
  GreaterN greater0(0);
  GreaterN greater32(32);
  GreaterN greater212(212);

  cout << greater0(-5) << endl;     // 0 (false)
  cout << greater0(3) << endl;      // 1 (true)

  cout << greater32(9) << endl;     // 0 (false)
  cout << greater32(45) << endl;    // 1 (true)

  cout << greater212(42) << endl;   // 0 (false)
  cout << greater212(451) << endl;  // 1 (true)
}

We have declared GreaterN objects as local variables and initialized them by calling the constructor, the same as other class-type objects. We can then use a GreaterN object as the first operand of the function-call operator. We pass whatever arguments are needed to invoke the overloaded member function, and as with any non-static member function, the this parameter is implicitly passed.

Figure 76 Invoking the overloaded function-call operator of a GreaterN object.

A GreaterN object provides the same interface as the functions required by any_of(). However, it is not a function or a pointer to a function; its type is GreaterN, and it cannot be passed to the version of any_of() we wrote previously. Instead, we need to write a new version that allows predicates of any type. Since it is a type that differs, we add a template parameter to refer to that type:

// REQUIRES: begin is before or equal to end
// EFFECTS:  Returns true if pred returns true when applied to at
//           least one element in the sequence [begin, end).
template <typename Iter_type, typename Predicate>
bool any_of(Iter_type begin, Iter_type end, Predicate pred) {
  for (Iter_type it = begin; it != end; ++it) {
    if (pred(*it)) {
      return true;
    }
  }
  return false;
}

Like iterators, functors are generally passed by value. We can now use any_of() with a GreaterN object:

List<int> list;
... // fill list with numbers
GreaterN greater0(0);
cout << any_of(list.begin(), list.end(), greater0);      // pass existing functor
cout << any_of(list.begin(), list.end(), GreaterN(32));  // pass temporary functor

The compiler deduces the template parameter Iter_type as List<int>::Iterator, and the parameter Predicate as GreaterN. We can still call any_of() with a function pointer:

cout << any_of(list.begin(), list.end(), is_odd);        // pass function

In this case, the compiler deduces Predicate as the function-pointer type bool (*)(int).

By parameterizing any_of() with the predicate type, we can now call it on sequences of objects that are of types other than int. As long as a sequence element can be passed to the predicate, the code will work.

bool is_empty(const string &s) {
  return s.empty();
}

int main() {
  vector<string> vec;
  ... // fill vec with strings
  cout << any_of(vec.begin(), vec.end(), is_empty);
}

Exercise 1

Write a function list_count() that counts the number of elements in a list for which the given predicate returns true. Assume that Node is defined as

struct Node {
  int datum;
  Node *next;
};

and use recursion to traverse the sequence of nodes.

// EFFECTS: Returns the number of elements in the list that
//          starts at the given node for which the predicate
//          returns true.
template <typename Predicate>
int last(const Node *node, Predicate pred) {
  // your code here
}

Comparators

Recall the max_element() function template from last time:

// REQUIRES: end is after or equal to begin
// EFFECTS:  Returns an iterator to the maximum element in [begin, end).
//           Returns begin when the sequence is empty.
template <typename Iter_type>
Iter_type max_element(Iter_type begin, Iter_type end) {
  Iter_type max_so_far = begin;
  for (; begin != end; ++begin) {
    if (*max_so_far < *begin) {
      max_so_far = begin;
    }
  }
  return max_so_far;
}

The function template uses the < operator to compare elements, so it only works on types that provide that operator. It will not work with a type such as Duck that does not overload the less-than operator. However, we may still want to compare Ducks according to some criteria, such as by their names or their ages. Thus, we need a way of specifying how max_element() should compare objects. We can do so by adding another parameter to represent a comparator, which takes two objects and returns a value that indicates how they compare to each other.

// REQUIRES: end is after or equal to begin
// EFFECTS:  Returns an iterator to the maximum element in [begin, end)
//           according to the given comparator. Returns begin when
//           the sequence is empty.
template <typename Iter_type, typename Comparator>
Iter_type max_element(Iter_type begin, Iter_type end,
                      Comparator less) {
  Iter_type max_so_far = begin;
  for (; begin != end; ++begin) {
    if (less(*max_so_far, *begin)) {
      max_so_far = begin;
    }
  }
  return max_so_far;
}

Standard comparators in C++ do a less-than comparison, so we have modified max_element() to take in such a comparator. The type of the comparator is a template parameter so that either a functor or a function pointer can be used. The code then calls the comparator with two arguments to determine if the first is less than the second.

We can write a Duck comparator that compares two ducks by name:

class DuckNameLess {
public:
  bool operator()(const Duck &d1, const Duck &d2) const {
    return d1.get_name() < d2.get_name();
  }
};

Here, we have written the comparator as a functor; since it doesn’t require any storage, it could have been written as a function as well. [2] We can then call max_element() as follows:

[2]

While either a functor or function would work, functors are actually more efficient since calling them does not require any indirection. The compiler can statically determine from the functor type which overloaded operator is called, while calling through a function pointer generally requires a dereference at runtime. Thus, functors are usually preferred over functions given a choice between the two.

vector<Duck> vec;
... // fill vec with Ducks
cout << (*max_element(vec.begin(), vec.end(), DuckNameLess())).get_name();

We pass a default-constructed DuckNameLess object as the comparator and get back an iterator to the Duck with the maximum name. We then dereference the iterator to get to the Duck object and call get_name() on it. [3]

[3]

Standard-library iterators overload the -> operator, so we could use that operator to call get_name() directly rather than manually applying dereference followed by the dot operator.

Given our modifications to max_element(), we can no longer call it without a comparator argument, even for types that support the < operator. However, the standard <algorithm> library provides a functor template std::less that just invokes the < operator, so we can use it with types that do have the operator:

vector<int> vec;
... // fill vec with numbers
cout << *max_element(vec.begin(), vec.end(), std::less<int>());

It is also possible to write max_element() to default to using std::less when a comparator is not explicitly provided, but that is beyond the scope of this course.

Iterating over a Sequence

Another common pattern is to iterate over a sequence, performing some operation on each element individually. We can write a for_each() function template that implements this pattern, taking in a function pointer or functor that applies to a single element:

// REQUIRES: end is after or equal to end
// EFFECTS: Applies func to each of the elements in the sequence
//          [begin, end) and returns func.
template <typename Iter_t, typename Func_t>
Func_t for_each(Iter_t begin, Iter_t end, Func_t func) {
  for (Iter_t it = begin; it != end; ++it) {
    func(*it);
  }
  return func;
}

We return the func argument, in case it contains data that are useful to the caller. For instance, the following functor stores the sum of integer elements:

class Accumulator {
public:
  void operator()(int x) {
    sum += x;
  }

  int get_sum() const {
    return sum;
  }

private:
  int sum = 0;
};

We can then compute the sum of the elements in a sequence:

vector<int> vec;
... // fill vec with numbers
Accumulator summer;
summer = for_each(vec.begin(), vec.end(), summer);
cout << summer.get_sum() << endl;

To print out the elements in a sequence to a stream, we can write a functor template for printing:

template <typename T>
class Printer {
public:
  Printer(std::ostream &os) : output(os) {}

  void operator()(const T &item) const {
    output << item << std::endl;
  }

private:
  std::ostream &output;
};

The member variable must be a reference, since streams do not generally support copying. We can then use Printer to print out each element in a sequence:

int main() {
  List<int> list;
  ... // fill list with numbers
  ofstream fout("list.out");
  for_each(list.begin(), list.end(), Printer<int>(fout));
}

Impostor Syndrome

In addition to building our programming skills, it is also important to develop an appropriate awareness of our own abilities. Unfortunately, many of us encounter impostor syndrome, where we do not internalize our own accomplishments. Despite demonstrating success in a course like this, we often fear being exposed as a “fraud.”

Recognizing impostor syndrome is the first step to overcoming it. The following are common characteristics of people who have impostor syndrome:

• They attribute their success to external factors.

• They fear being revealed as a fraud.

• They convince themselves that they are not good enough.

• They have a hard time accepting compliments for their accomplishments.

Impostor syndrome differs from implicit bias in that the latter affects how we subconsciously view others, while the former affects how we view ourselves. The National Center for State Courts defines implicit bias as:

The bias in judgment and/or behavior that results from subtle cognitive processes (e.g., implicit attitudes and stereotypes) that often operate at a level below conscious awareness and without intentional control.

Of course, these implicit attitudes also affect how we view ourselves, so even though impostor syndrome affects everyone, it tends to have a higher effect on people in underrepresented groups.

The result of impostor syndrome is to doubt ourselves, having feelings such as:

• “I was hired to fill a diversity quota.”

• “Everyone else seems smarter than me.”

• “If I’m not getting an A, how am I going to survive in future courses?”

• “Nobody else here is like me – I don’t belong in this class”.

• “I don’t like asking questions in class because I’m afraid others will realize I don’t know what I’m doing.”

• “Maybe EECS isn’t for me; I should drop.”

The truth is that almost everyone suffers from feelings like this. Surveys on impostor syndrome have found that “about 70 percent of people from all walks of life – men and women – have felt like impostors for at least some part of their careers.” [4] The likelihood is that many of us are experiencing this right now, in this course.

[4]

Gravois, J. (2007). You’re not fooling anyone. The Chronicle of Higher Education, 54(11), A1.

There are steps we can take to overcome impostor syndrome:

• Stop comparing ourselves to others.

• Encourage each other.

• Join student organizations and connect with other students.

• Accept our accomplishments.

• Find a mentor.

We do not have to experience this alone; instead, we should support each other and find others we can lean on.

The following are additional resources on impostor syndrome:

• University of Michigan CAPS page on impostor syndrome

• TED talk on how students of color confront impostor syndrome

• American Psychological Association article on impostor syndrome