Advanced Programming II Class Notes

Lecture Notes for Advanced Programming II

7 November 2002 - Function Objects

Function Objects

A word count 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
A final langnappe.

Counting Words

How many times do words appear in text?

The STL makes this easy to find out.

cnt_wds(istream & is)
  map<string, unsigned> wd_cnt
  while is >> str
    wc_cnt[str]++

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

Counting Words With Globals

For access, wd_cnt must be left as a global.

map<string, unsigned> wd_cnt

cnt_wds(istream & is)
  for_each(istream_iterator<string>(is),
           istream_iterator<string>(),
           count_wd)

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

What are Function Objects?

The call operator () can be defined within 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 pointer.
```
callable c;
int i = c(1);
```
A class instance is not a function pointer, however.
- No * needed.
```
callable c;
int i = (* c)(1);
```
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

Funcion objects have lots of different 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 Word Counting

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

Store the word map in a function object to eliminate the global.

struct word_count {
  map<string, unsigned> wdcnt;

  void operator () (string wd) {
    wdcnt[wd]++
    }
  };  

cnt_wds(istream & is)
  word_count wc;
  for_each(istream_iterator<string>(is),
           istream_iterator<string>(),
           wc)
  cout << wc.wdcnt.size() << "words read.\n"

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.
- &c is not a function pointer; it's a pointer to callable class value.
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.

Zero Residue Counts

How many ints in a vector are congruent to 0 mod 3?

unsigned count = 0
for unsigned i = 0; i < iv.size(); i++
  if iv[i] % 3 == 0
    count++

The value i mod n is the residue mod n.

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, 0) returns the number of zero elements.
- We want the number of zero element residues mod 3.
count_if(b, e, p) returns the number of elements satisfying p().
- p() is a unary (one-argument) predicate (boolean returning function).

Counting Zero Residues

How about using
```
bool zm3(int i)
  return (i % 3) == 0
```
as the predicate for find_if()?

And we're done.

count = count_if(iv.begin(), iv.end(), zm3)

Other Residue Counts

How many elements are congruent to 1 mod 3? To 2 mod 3?

We've turned that crank before.

bool om3(int i) { return (i % 3) == 1 }

bool tm3(int i) { return (i % 3) == 2 }

count0 = count_if(iv.begin(), iv.end(), zm3)
count1 = count_if(iv.begin(), iv.end(), om3)
count2 = count_if(iv.begin(), iv.end(), tm3)

Oh yuck - duplicate code. Is there a better way?
- How about
```
bool cm3(int i, int r)
  return (i % 3) == r
```
find_if() requires a unary predicate, not a binary (two argument) one.
- ~~count_if(iv.begin(), iv.end(), cm3)~~ doesn't compile.
- Even if it did, how does r get a value?

Function Adapters

Sometimes functions 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.
Sometimes STL can deal with both functions and function objects.
- And sometimes it 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 Residues with Function Objects

cm3() doesn't work with std::find_if().
- cm3(int i, int r) has two arguments; can't set r.
The function adapter bind2nd() can solve these problems.
- Convert cm3() from a function to a function object with std::ptr_fun().
```
std::ptr_fun(cm3)
```
- Set the residue r for cm3 with std::bind2nd().
```
std::bind2nd(std::ptr_fun(cm3), r)
```

And we're done.

unsigned count_residues(ivec iv, int r)
  return find_if(iv.begin(), iv.end(), 
                 bind2nd(fun_ptr(cm3), r))

const unsigned modulus = 3
vector<unsigned> r_counts(modulus)
for unsigned i = 0; i < modulus; i++
  r_counts[i] = count_residues(iv, i)

`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_cpt().

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; ctp() 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
- Arithmatic: plus, minus, multiplies, ...
- Comparisons: equal_to, less_equal, ...
- Logical: logical_not, logical_or, ...

`cm3()` Revisited

cm3(int i, int r) didn't work with count_if().
- Too many arguments; can't set r.
bind2nd() works with cm3(), but is there another way?

Let's re-examine the original problem.

Which was duplicate code.

bool zm3(int i) { return (i % 3) == 0 }
bool om3(int i) { return (i % 3) == 1 }
bool tm3(int i) { return (i % 3) == 2 }

The residue value is the only difference. Can it be abstracted away?
- That smells like a job for templates, for value templates.
```
template < int res >
bool cm3(int i) { return (i % 3) == res; }
```

And - amazingly enough - it works, too.

c0 = count_if(iv.begin(), iv.end(), cm3<0>)
c1 = count_if(iv.begin(), iv.end(), cm3<1>)
c2 = count_if(iv.begin(), iv.end(), cm3<2>)

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.
The STL defines a family of functors.
- For arithmatic, comparisons, and logical operations.

This page last modified on 8 November 2002.