# Function Pointers and Functors

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
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.

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:

```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 `int`s 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]

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 `int`s.

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.

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);
}
```

## 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 `Duck`s 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:

```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]

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.

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: