Content
Review and Introduction Function-Pointer Types Functors Comparators Iterating over a Sequence <- Go BackUniversity of Michigan at Ann Arbor
Last Edit Date: 04/09/2023
Disclaimer and Term of Use:
We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file
This personal note is adapted from Professor Amir Kamil, Andrew DeOrio, James Juett, Sofia Saleem, and Saquib Razak. Please contact us to delete this file if you think your rights have been violated.
This work is licensed under a Creative Commons Attribution 4.0 International License.
We know itertators, 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 an odd element in the sequence:
1 // REQUIRES: begin is before or equal to end
2 // EFFECTS: Returns true if any element in the sequence
3 // [begin, end) is odd.
4 template <typename Iter_type>
5 bool any_of_odd(Iter_type begin, Iter_type end) {
6 for (Iter_type it = begin; it != end; ++it) {
7 if (*it % 2 != 0) {
8 return true;
9 }
10 }
11 return false;
12 }
We can 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:
1 // REQUIRES: begin is before or equal to end
2 // EFFECTS: Returns true if any element in the sequence
3 // [begin, end) is even.
4 template <typename Iter_type>
5 bool any_of_even(Iter_type begin, Iter_type end) {
6 for (Iter_type it = begin; it != end; ++it) {
7 if (*it % 2 == 0) {
8 return true;
9 }
10 }
11 return false;
12 }
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:
1 int power3(int x) {
2 int result = 1;
3 for (int i = 0; i < 3; ++i) {
4 result *= x;
5 }
6 return result;
7 }
8
9 int power4(int x) {
10 int result = 1;
11 for (int i = 0; i < 4; ++i) {
12 result *= x;
13 }
14 return result;
15 }
16
17 int power(int x, int n) { // add parameter to generalize
18 int result = 1;
19 for (int i = 0; i < n; ++i) {
20 result *= x;
21 }
22 return result;
23 }
24
25 int main() {
26 for (int i = 0; i < 10; ++i) {
27 cout << power(42, i); // supply desired argument
28 }
29 }
Try it out:
When it is a type that differs, we make the function a template and introduce a template parameter:
1 int max_int(int x, int y) {
2 return x < y ? y : x;
3 }
4
5 double max_card(const Card &x, const Card &y) {
6 return x < y ? y : x;
7 }
8
9 template <typename T> // add template parameter to generalize
10 T max(const T &x, const T &y) { // pass objects of template-parameter type
11 // by reference
12 return x < y ? y : x;
13 }
14
15 int main() {
16 cout << max(3, -1) << endl; // template parameter deduced from arguments
17 cout << max(Card(Card::RANK_TWO, Card::SUIT_SPADES),
18 Card(Card::RANK_TOW, Card::SUIT_HEARTS)) << endl;
19 }
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:
1 bool is_odd(int x) {
2 return x % 2 != 0;
3 }
4
5 bool is_even(int x) {
6 return x % 2 == 0;
7 }
8
9 bool is_positive(int x) {
10 return x > 0;
11 }
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:
1 bool (*func)(int) = &is_odd;
2 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 address-of operator for us.
We can call a function through a pointer by first dereferencing the pointer:
1 bool (*func)(int) = is_odd;
2 (*func)(-2); // returns false
Like with the address-of operator, the compiler can implicitly insert this dereference for us:
func(-2); // returns false
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);
int max_int(int, int);
* symbol to indicate it is a pointer, surrounded by paratheses:int (*func3)(int, int);
The result is that func3 is a pointer to a function that takes two ints and returns an int.
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:
1 bool greater32(int x) {
2 return x > 32;
3 }
4
5 bool greater212(int x) {
6 return x > 212;
7 }
Since what differs is just a value, we can write a function that has a parameter for the threshold value:
1 bool greater(int x, int threshold) {
2 return x > threshold;
3 }
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.
Class types, on the other hand, do define first-classs entities.
A class object can store state in member variables.
A class object can be created at runtime.
A class object 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 alow a class-type object to be called if the class overloads the function-call operator. We refer such a class as a functor.
A functor is a class type that provides the same interface as a function, much like in 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:
1 class GreaterN {
2 public:
3 // EFFECTS: Creates a GreaterN with the given threshold.
4 GreaterN(int threshold_in) : threshold(threshold_in) {}
5
6 // EFFECTS: Returns whether or not the given value is greater than
7 // this GreaterN's threshold.
8 bool operator()(int x) const {
9 return x > threshold;
10 }
11
12 private:
13 int threshold;
14 };
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 can create and use GreaterN objects as follows:
1 int main() {
2 GreaterN greater0(0);
3 GreaterN greater32(32);
4 GreaterN greater212(212);
5
6 cout << greater0(-5) << endl; // 0 (false)
7 cout << greater0(3) << endl; // 1 (true)
8
9 cout << greater32(9) << endl; // 0 (false)
10 cout << greater32(45) << endl; // 1 (true)
11
12 cout << greater212(42) << endl; // 0 (false)
13 cout << greater212(451) << endl; // 1 (true)
14 }
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.
Try it out:
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:
1 // REQUIRES: begin is before or equal to end
2 // EFFECTS: Returns true if pred returns true when applied to at
3 // least one element in the sequence [begin, end).
4 template <typename Iter_type, typename Predicate>
5 bool any_of(Iter_type begin, Iter_type end, Predicate pred) {
6 for (Iter_type it = begin; it != end; ++it) {
7 if (pred(*it)) {
8 return true;
9 }
10 }
11 return false;
12 }
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);
}
Recall the max_element() function template from last time:
1 // REQUIRES: end is after or equal to begin
2 // EFFECTS: Returns an iterator to the maximum element in [begin, end).
3 // Returns begin when the sequence is empty.
4 template <typename Iter_type>
5 Iter_type max_element(Iter_type begin, Iter_type end) {
6 Iter_type max_so_far = begin;
7 for (; begin != end; ++begin) {
8 if (*max_so_far < *begin) {
9 max_so_far = begin;
10 }
11 }
12 return max_so_far;
13 }
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.
1 // REQUIRES: end is after or equal to begin
2 // EFFECTS: Returns an iterator to the maximum element in [begin, end)
3 // according to the given comparator. Returns begin when
4 // the sequence is empty.
5 template <typename Iter_type, typename Comparator>
6 Iter_type max_element(Iter_type begin, Iter_type end,
7 Comparator less) {
8 Iter_type max_so_far = begin;
9 for (; begin != end; ++begin) {
10 if (less(*max_so_far, *begin)) {
11 max_so_far = begin;
12 }
13 }
14 return max_so_far;
15 }
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:
1 class DuckNameLess {
2 public:
3 bool operator()(const Duck &d1, const Duck &d2) const {
4 return d1.get_name() < d2.get_name();
5 }
6 };
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. 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.
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.
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:
1 // REQUIRES: end is after or equal to end
2 // EFFECTS: Applies func to each of the elements in the sequence
3 // [begin, end) and returns func.
4 template <typename Iter_t, typename Func_t>
5 Func_t for_each(Iter_t begin, Iter_t end, Func_t func) {
6 for (Iter_t it = begin; it != end; ++it) {
7 func(*it);
8 }
9 return func;
10 }
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:
1 class Accumulator {
2 public:
3 void operator()(int x) {
4 sum += x;
5 }
6
7 int get_sum() const {
8 return sum;
9 }
10
11 private:
12 int sum = 0;
13 };
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:
1 template <typename T>
2 class Printer {
3 public:
4 Printer(std::ostream &os) : output(os) {}
5
6 void operator()(const T &item) const {
7 output << item << std::endl;
8 }
9
10 private:
11 std::ostream &output;
12 };
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));
}