Advanced Programming II Class Notes

Lecture Notes for Advanced Programming II

6 November 2003 - Function Objects

Function Objects

A counting problem
Function objects
- Declarations
- Instances
- Uses
Problems old and new.
Function Adapters
- Argument-Reducing Adapters
- Negating Function Adopters
- Converting Adapters
Yet more problems solved.
STL-Defined Functors

Counting Votes

How many votes were cast for each candidate?

The STL makes this easy to find out.

cnt_votes(vector<int> votes)

  vector<unsigned> candidates(votes.size())

  for unsigned i = 0; i < votes.size(); i++
    candidates[votes[i]]++

But there's a loop. Isn't there a generic algorithm?
- std::for_each(b, e, f) is a good candidate.
- It calls f() for each value in the range (b, e).
Use std::for_each() with the function
```
void count_vote(int vote)
  candidates[vote]++
```
- But from where did candidates come?
- It's not a parameter, it must be a global.

Counting Votes With Globals

For access, candidates must be left as a global.

vector<unsigned> candidates(n)

cnt_votes(vector<int> & votes)
  for (unsigned i = 0; i < votes.size(); i++)
    candidates[votes[i]]++

Globals are bad code too.
- Difficult to promote disciplined access.
- Can't count more than one voide at once.
  - The various counts conflict over candidates.
Loops and no globals, or globals and no loops.
- Not a pleasant choice.

What are Function Objects?

The call operator () can be defined in classes and structs.
- "and structs" assumed from now on.

Defining operator () allows class instances to be called as if they were functions.

struct callable { 
  char operator () (int i, string s) { ... }
  };

callable c;
char ch = c(1, "hello");

A functor is a class that defines one or more operator () member functions.
- The class callable is a functor.
An instance of a functor is a function object.
- c is a function object; that is, an object that responds as if it were a function.
These terms are open to much interpretation, however.

Function Object Declarations

Call declarations look odd, but follow other operator declarations.
The general declaration form is
```
struct name {
  return-type-spec operator () ( argument-list-decls )
  }
```
- The declaration may include a definition, or the definition may be in a separate file.

For example

struct count {
  void operator () (int i);
  }

The call operator must be a member function.
- It must be non-static too. (why?)
The call operator may be overloaded.
- Resolution is as it is for function overloading.
- Argument type, number, and order; no return type.

Calling Object Instances

A class instance is treated like a function.
```
callable c;
int i = c(1);
```
- A class instance is not a function, however.
Don't confuse instance creation with instance calling.
```
callable c = callable()  // instance creation
int i = c()              // instance calling
```
- If it's a class name, it's creation.
- If it's an instance name, it's a call.

Function Object Uses

Function objects have lots of uses.
- The STL makes heavy use of them.
Function objects can be easily modified.
- Save one function object inside another.
Function objects can store state without resorting to globals.
- Function object instance variables are like globals.
Function objects can intercept regular function calls.
- Implementing your own debugging trace routines.

Revisiting Vote Counting

Function objects can save us from the unpleasant choice of loops or globals.

Store the vote count in a function object to eliminate the global.

struct vote_count {

  vector<unsigned> candidates;

  vote_count(unsigned n) : candidates(n) { }

  void operator () (unsigned v) {
    candidates[v]++
    }
  };  

cnt_votes(vector<unsigned> & votes)
  vote_count vc(n);
  for_each(votes.begin(), votes.end(), vc);
  cout << "Candidate 0 got " 
       << vc.candidates[0] << " votes";

Function Objects vs. Functions

Function objects and functions can both be called, but they are different.
- A function object is not a function; it's a class instance.
Confused? Think about dot member function access.
- c.operator()(1, "hello") works via member function access.
- isdigit.operator()('c') fails because isdigit() isn't a class.

Function Objects and Functions

Write code accepting both function objects and functions.
- It makes for more generally applicable code.
- It requires templates.
```
template < typename testT >
bool is_str_type(string str, testT test)
  for unsigned i = 0; i < str.size(); i++
    if !test(str[i]) return false
  return true
```
- Only the call operator is applied to test.

Candidate Vote Counts

How many votes did Candidate c get?

unsigned count = 0
for unsigned i = 0; i < votes.size(); i++
  if votes[i] == c
    count++

A vector loop is bad code. Is there a generic algorithm?
- Look for a non-mutating generic algorithm.
There's count() and count_if().
count(b, e, c) returns the number of votes for the candidate c.
count_if(b, e, p) returns the number of elements satisfying p().
- p() is a unary (one-argument) predicate (boolean returning function).

Counting Individual Votes

How about using
```
bool is_c_vote(unsigned v)
  return c == v
```
as the predicate for count_if()?

And we're done.

count = count_if(votes.begin(), votes.end(), 
                 is_c_vote)

Other Candidate Counts

How many votes did Candidate c_j get? Candidate c_k?

We've turned that crank before.

bool is_cj_vote(unsigned v) { return cj == v }
bool is_ck_vote(unsigned v) { return ck == v }

cicount = count_if(h.begin(), h.end(), is_ci_vote)
cjcount = count_if(h.begin(), h.end(), is_cj_vote)
ckcount = count_if(h.begin(), h.end(), is_ck_vote)

Oh yuck - duplicate code. Is there a better way?
- How about
```
bool is_vote(unsigned c, unsigned v)
  return c == v
```
count_if() requires a unary predicate, not a binary (two argument) one.
- ~~count_if(h.begin(), h.end(), is_vote)~~ doesn't compile.
- Even if it did, how does c get a value?

Function Adapters

Sometimes functions or function objects don't do quite what we want.
- One more argument than required.
- A predicate of the wrong sense.
A function adapter is an STL feature that can help in these cases.
Some STL features handle functions and function objects.
- And some STL features must have a function object.
The STL has a function adapter for this too.
Everything defined in <functional>.

The Argument-Reducing Function Adapters

The bind2nd() and bind1st() function adaptors.
- They create unary function objects from binary function objects.

bind1st(fo, val) accepts the function object

struct fo { 
  operator () (x, y) { ... } 
  }

and returns the function object

struct fo' { 
  operator () (y) { fo(val, y) } 
  }

bind2nd(fo, val) accepts the function object

struct fo { 
  operator () (x, y) { ... } 
  }

and returns the function object

struct fo' { 
  operator () (x) { fo(x, val) } 
  }

The Converting Function Adapter

The bind adapters work on function objects, not functions.

The function adaptor std::ptr_fun() converts a function to a function object.

The function being converted must have one or two arguments.

Argument types can differ, as can the return type.

void zero(void) { ... }
void one(int i) { ... }
void two(int i, string j) { ... }
void three(int i, int j, int k) { ... }

std::ptr_fun(zero)
std::ptr_fun(one)
std::ptr_fun(two)
std::ptr_fun(three)

Remembering when to use std::ptr_fun() can be a pain.
- One alternative is to use it on every function.

Counting Votes with Function Objects

is_cj_vote() doesn't work with std::count_if().
- is_cj_vote(unsigned c, unsigned v) has two arguments; can't set c.
The function adapter bind1st() can solve these problems.
- Convert is_vote() from a function to a function object with std::ptr_fun().
```
std::ptr_fun(is_cj_vote)
```
- Set the candidate s for is_vote() with std::bind1st().
```
std::bind1st(std::ptr_fun(is_vote), cj)
```

And we're done.

unsigned count_votes(vector<unsigned> votes, int c)
  return 
    count_if(votes.begin(), votes.end(), 
             bind1st(fun_ptr(is_vote), c))

vector<unsigned> s_counts(4)
for unsigned i = 0; i < 4; i++
  s_counts[i] = count_vote(votes, i)

Compile-Time vs. Run-time

Template are expanded at compile time.
- The compiler needs the values for the template parameters.

Consider the function

unsigned 
count_vote(vector<unsigned> votes, int c) 
  return std::count_if(votes.begin(), 
                       votes.end(),
                       is_vote<c>);

The value of c in is_vote<c> is not known at compile time.
- It is only known at run-time, which is too late for template expansion.

Move the template parameter out one level.

template < unsigned c >
unsigned 
count_vote(std::vector<unsigned> votes) 
  return std::count_if(votes.begin(), 
                       votes.end(),
                       is_vote<c>);

`isstrtype` Revisited

Remember isstrtype()? It applied <cctype> predicates to strings.

bool isstrtype(string s, bool (* ctp)(char))
  for (unisgned i = 0; i < s.size(); i++)
    if (!ctp(s[i]))
      return false
  return true

What's with that loop? That's bad code.

Why not use std::find_if()?

bool isstrtype(string s, bool (* ctp)(char))
  string::iterator e = s.end()
  return find_if(s.begin(), e, ctp) == e

find_if() is looking for the wrong thing.
- find_if() looks for characters of the type (digit, for example) and skips characters not of the type.
- isstrtype() looks for characters not of the type (digit, for example) and skips characters of the type.
ctp() is the wrong predicate; it should be not_ctp().

The Negating Function Adopters

The not1() and not2 function adaptors.
They negate unary or binary predicate function objects.

not1(fo) accepts the function object

struct fo { 
  bool operator () (x) { ... } 
  }

and returns the function object

struct fo' { 
  bool operator () (x) { return !fo(x) } 
  }

not2(fo) accepts the function object

struct fo { 
  bool operator () (x, y) { ... } 
  }

and returns the function object

struct fo' { 
  bool operator () (x, y) { return !fo(x, y) } 
  }

`isstrtype()` and Function Adapters

Can the function adapter std::not1() solve this problem?
```
find_if(s.begin(), s.end(), not1(ctp))
```
- Nope; not1() works on function objects, not functions.
Use fun_ptr() to convert a function to a function object.

And we're done.

bool 
isstrtype(string s, bool (* ctp)(char))
  return find_if(s.begin(), s.end(),
                 not1(ptr_fun(ctp)))

while getline(std::cin, str)

  if isstrtype(str, isspace)
    continue

  if !isstrtype(str, isdigit)
    std::cerr << "Number expected.\n";

STL-Defined Functors

The STL defines fifteen functors.
- You've already met less.

Rather than write

  class pt_less {
    bool operator () (point a, point b) {
      return a < b;
      }
    };

  map<point, unsigned, pt_less> points;

write instead

  map<point, unsigned, less<point> > points;

The defined functors include
- Arithmetic: plus, minus, multiplies, ...
- Comparisons: equal_to, less_equal, ...
- Logical: logical_not, logical_or, ...

Points to Remember

Function objects are classes that can be called.
- They define operator () member functions.
Function objects are flexible and powerful.
- The STL uses them a lot.
Don't confuse function objects and functions.
- One's a class or class instance, the other's neither.
Function adapters can munge functions and functors.
- Bind arguments, negate predicates, convert functions.

This page last modified on 17 November 2003.