Advanced Programming II Class Notes

Lecture Notes for Advanced Programming II

6 March 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 Suits

How many of each suit appear in a hand?

The STL makes this easy to find out.

cnt_suits(vector hand)

  unsigned suits[] = { 0, 0, 0, 0 };

  for (unsigned i = 0; i < hand.size(); i++)
    suits[hand[i].suit]++

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_suit(const card & c)
  assert(is_suit(c.suit))
  suits[c.suit]++
```
- But from where did suits come?
- It's not a parameter, it must be a global.

Counting Suits With Globals

For access, suits must be left as a global.

unsigned suits[] = { 0, 0, 0, 0 }

cnt_suits(vector & hand)
  for (unsigned i = 0; i < hand.size(); i++)
    suits[hand[i].suit]++

Globals are bad code too.
- Difficult to promote disciplined access.
- Can't count more than one hand at once.
  - The various counts conflict over suits.
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

Funcion 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 Suit Counting

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

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

struct suit_count {
  unsigned suits[] = { 0, 0, 0, 0 }

  void operator () (card c) {
    assert(is_suit(c.suit);
    suits[c.suit]++
    }
  };  

cnt_suits(vector & hand)
  suit_count sc;
  for_each(hand.begin(), hand.end(), sc);
  cout << "There were " 
       << sc.suits[0] << " clubs";

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.

Diamond Suit Counts

How many cards in a hand are diamonds?

unsigned count = 0
for unsigned i = 0; i < hand.size(); i++
  if hand[i].suit == heart
    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 elements equal to the single card c.
- We want the number of diamond cards.
count_if(b, e, p) returns the number of elements satisfying p().
- p() is a unary (one-argument) predicate (boolean returning function).

Counting Individual Suits

How about using

bool is_heart_card(card c)
  return c.suit == heart

as the predicate for count_if()?

And we're done.

count = count_if(hand.begin(), hand.end(), 
                 is_heart_card)

Other Suit Counts

How many cards are spade cards? Club cards?

We've turned that crank before.

bool is_spade_card(card c) { return c.suit == spade }

bool is_club_card(card c) { return c.suit == club }

hcount = count_if(h.begin(), h.end(), is_heart_card)
ccount = count_if(h.begin(), h.end(), is_club_card)
scount = count_if(h.begin(), h.end(), is_spade_card)

Oh yuck - duplicate code. Is there a better way?
- How about
```
bool is_suit(card c, int suit)
  return c.suit == suit
```
count_if() requires a unary predicate, not a binary (two argument) one.
- ~~count_if(h.begin(), h.end(), is_suit)~~ doesn't compile.
- Even if it did, how does suit 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 Suits with Function Objects

is_heart_suit() doesn't work with std::count_if().
- is_suit(card c, int s) has two arguments; can't set s.
The function adapter bind2nd() can solve these problems.
- Convert is_suit() from a function to a function object with std::ptr_fun().
```
std::ptr_fun(is_suit)
```
- Set the suit s for is_suit() with std::bind2nd().
```
std::bind2nd(std::ptr_fun(is_suit), s)
```

And we're done.

unsigned count_suit(vector hand, int s)
  return 
    count(hand.begin(), hand.end(), 
          bind2nd(fun_ptr(is_suit), s))

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

Special! Counting Suits with Template Functions

The problem with

bool is_club(card c) 
  return c.suit == club

bool is_diamond(card c) 
  return c.suit == diamond

bool is_heart(card c) 
  return c.suit == heart

bool is_spade(card c) 
  return c.suit == spade

is duplicate code, differing only in the suit.

Abstract the difference suits with a value-template parameter.

template <card::suit s>
bool is_suit(card c) 
  return c.suit == s

And we're done.

unsigned hearts = 
  std::count_if(hand.begin(), hand.end(), 
                is_suit<card::heart>);

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_suit(vector<card> hand, card::suit s) 
  return std::count_if(hand.begin(), 
                       hand.end(),
                       is_suit<s>);

The value of s in is_suit<s> 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 < card::suit s >
unsigned 
count_suit(std::vector<card> hand) 
  return std::count_if(hand.begin(), 
                       hand.end(),
                       is_suit<s>);

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

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 27 March 2003.