Functors and Impostor Syndrome
Participation
Loading...

Export your exercise answers to use with another computer or browser.

Functors and Impostor Syndrome

This lecture covers functors in C++, including their use in higher-order functions as predicates and comparators.

Finally, we cover impostor syndrome - a concept not directly related to programming but that is nevertheless relevant for many in our community.

1: Iterator Review, Motivating Example
1.1 Not Started

We'll start by briefly reviewing iterators and setting up the motivation for the main content of today's lecture.


1.1 Exercise: any_of_even()

Consider the function template any_of_odd() below, which takes in two iterators (of any kind) and determines whether any of the elements in the range they define are odd-valued.

  template <typename Iter_type>
  bool any_of_odd(Iter_type begin, Iter_type end) {
    while(begin != end) {
      if (*begin % 2 != 0) {
        return true;
      }
      ++begin;
    }
    return false;
  }

Which of the following would need to change in order to implement a similar function any_of_even() that determines whether any of the elements in the range are even-valued?

Explanation…

Beyond changing the function name, the only thing that needs to change is the condition in the if statement. Instead of checking for odd numbers, we would check for even numbers with *begin % 2 == 0.

The idea of swapping the return statements seems viable at first glace, but on closer inspection, this doesn't change the function to check for evens instead of odds. Rather, it would change the function from "any of" to "none of".


2: Function Pointers
2.1 Not Started

Building on the previous section and exercise - what if we wanted to check for other criteria besides even and odd numbers? How about prime numbers, or numbers that are greater than a certain threshold?

Instead of writing mostly the same code over and over again, let's come up with a generic any_of() function and just tell it what we're looking for when we use it.

There are a few different approaches to specify "what we're looking for" - we'll first try using function pointers, which are not quite the right answer in C++, but are a reasonable place to start.


So, we can use a function pointer to specify which function (e.g. is_prime())should act as a predicate for a higher-order function like any_of(), telling it what to look for. But, there are some limitations to this approach…


2.1 Exercise: Function Pointer Limitations

Here's a copy of the slide with the question from the video:


What do you think? Are any of these good ideas? For each, write "good idea" or "bad idea" in the blank provided. In your own words, justify your answer.

Make a single greater function that uses a global variable to store the threshold.



Make a single greater function with an extra parameter to pass in the threshold.



Add an extra parameter to the any_of function to pass in the threshold.

Sample solution…

It turns out none of these will work correctly.

Option A might work, but would be a bit clunky and error prone. We generally try to avoid global variables. We'll see better options soon…

Option B doesn't work, because the implementation any_of() function would need to pass in this extra parameter, but that wouldn't make sense if it was used with other predicates that don't expect a random extra parameter.

Option C follows from option B, but is flawed for the same reason. A higher-order function like any_of() should simply take in a predicate that is self-contained and does not require juggling extra parameters.

If only we could create customized greater() functions as we needed them, plugging in the specific threshold value we want… see the next section for details!


3: Functors
3.1 Not Started

Regular functions in C++ are not "first-class objects" - they cannot be created and customized at runtime. This inherently restricts the use of functions and function pointers for generic coding.

However, we can do something just as good - we can make a regular class-type object act like a function by overloading its () operator. These "function objects" are often called functors. Because functors are also regular C++ objects, they can be created at runtime, can be customized however we want, and can even store data in member variables!


3.1 Exercise: InRange Predicate Functor

Fill in the implementation of the InRange functor, which is constructed with two thresholds for lower and upper bounds of a range. Its function call operator takes in a value and returns true if that value is within the range (inclusive). Assume the numbers in question are doubles.

class InRange {
public:

  // Constructor
  


  // Function Call Operator
  


private:
  // Member Variables
  

};

Fill in the blanks to complete the implementation of count_if().

// REQUIRES: 'begin' is before or equal to 'end'
// EFFECTS:  Returns the number of elements in the sequence that satisfy 'pred'.
template <typename IterType, >
int count_if(IterType begin, IterType end,  pred) {
  


}

Add code to the main() function below that uses InRange and count_if() to determine the number of elements between 5 and 15, inclusive, in the vector vec. Some comments are provided to guide you.

int main() {

  vector<int> vec = {1, 6, 2, 8, 17, 23, 12};

  // Create an InRange functor with the appropriate thresholds
  



  // Call count_if with begin/end iterators from the vector
  // and the InRange functor you created above. (Make sure
  // that you don't call the functor here, just pass it in!)
  

}

Sample solution…

  class InRange {
  public:

    // Constructor
    InRange(double lower_in, double upper_in)
     : lower(lower_in), upper(upper_in) { }

    // Function Call Operator
    bool operator()(double val) const {
      return lower <= val && val <= upper;
    }

  private:
    // Member Variables
    double lower;
    double upper;
  };

Fill in the blanks to complete the implementation of count_if().

  // REQUIRES: 'begin' is before or equal to 'end'
  // EFFECTS:  Returns the number of elements in the sequence that satisfy 'pred'.
  template <typename IterType, typename Predicate>
  int count_if(IterType begin, IterType end, Predicate pred) {
    int count = 0;
    while(begin != end) {
      if (pred(*begin)) {
        ++count;
      }
      ++begin;
    }
    return count;

  }

Add code to the main() function below that uses InRange and count_if() to determine the number of elements between 5 and 15, inclusive, in the vector vec. Some comments are provided to guide you.

  int main() {

    vector<int> vec = {1, 6, 2, 8, 17, 23, 12};

    // Create an InRange functor with the appropriate thresholds
    InRange in_range(5, 15);


    // Call count_if with begin/end iterators from the vector
    // and the InRange functor you created above. (Make sure
    // that you don't call the functor here, just pass it in!)
    int n = count_if(vec.begin(), vec.end(), in_range);
  }


4: Comparators

Another common use for functors is to define multiple different ways of comparing objects. The functor overloads the () to take in two objects, compare them, and return true if the first is less than the second ("less than" is the conventional direction of comparison, at least). Such a functor is called a comparator.


Comparators have many uses! Higher-order functions can take in a comparator to determine how they search for the smallest element, sort a particular sequence, or any process that depends on ordering. Or, a data structure like a binary search tree could also allow a custom comparator to be used to determine the ordering of elements it contains.


5: for_each()

Here's one more example of a higher-order function for you to consider.


The for_each() function essentially provides a high-level abstraction for using iterators and functors to perform the same tasks we might regularly write out with more verbose code using a loop.

6: Impostor Syndrome

Let's take a break from functors to discuss something just as important…

Impostor syndrome is the name given to a feeling of self-doubt, often accompanied by a difficulty accepting one's own accomplishments or a fear of being exposed as a fraud.


I mentioned a poll in the video above - here's a set of results from a previous term.

We asked, "Have you felt like an impostor in your classes here at the University of Michigan?"
You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.