MFC Programmer's SourceBook : Thinking in C++
Bruce Eckel's Thinking in C++, 2nd Ed Contents | Prev | Next

Function objects

A concept that is used heavily in the STL algorithms is the function object , which was introduced in the previous chapter. A function object has an overloaded operator( ), and the result is that a template function can’t tell whether you’ve handed it a pointer to a function or an object that has an operator( ); all the template function knows is that it can attach an argument list to the object as if it were a pointer to a function:

//: C21:FuncObject.cpp
// Simple function objects
#include <iostream>
using namespace std;

template<class UnaryFunc, class T>
void callFunc(T& x, UnaryFunc f) {
  f(x);
}

void g(int& x) {
  x = 47;
}

struct UFunc {
  void operator()(int& x) {
    x = 48;
  }
};

int main() {
  int y = 0;
  callFunc(y, g);
  cout << y << endl;
  y = 0;
  callFunc(y, UFunc());
  cout << y << endl;
} ///:~ 

The template callFunc( ) says “give me an f and an x, and I’ll write the code f(x).” In main( ), you can see that it doesn’t matter if f is a pointer to a function (as in the case of g( )), or if it’s a function object (which is created as a temporary object by the expression UFunc( )). Notice you can only accomplish this genericity with a template function; a non-template function is too particular about its argument types to allow such a thing. The STL algorithms use this flexibility to take either a function pointer or a function object, but you’ll usually find that creating a function object is more powerful and flexible.

The function object is actually a variation on the theme of a callback, which is described in the design patterns chapter. A callback allows you to vary the behavior of a function or object by passing, as an argument, a way to execute some other piece of code. Here, we are handing callFunc( ) a pointer to a function or a function object.

The following descriptions of function objects should not only make that topic clear, but also give you an introduction to the way the STL algorithms work.

Classification of function objects

Just as the STL classifies iterators (based on their capabilities), it also classifies function objects based on the number of arguments that their operator( ) takes and the kind of value returned by that operator (of course, this is also true for function pointers when you treat them as function objects). The classification of function objects in the STL is based on whether the operator( ) takes zero, one or two arguments, and if it returns a bool or non- bool value.

Generator: Takes no arguments, and returns a value of the desired type. A RandomNumberGenerator is a special case.

UnaryFunction: Takes a single argument of any type and returns a value which may be of a different type.

BinaryFunction: Takes two arguments of any two types and returns a value of any type.

A special case of the unary and binary functions is the predicate, which simply means a function that returns a bool. A predicate is a function you use to make a true /false decision.

Predicate: This can also be called a UnaryPredicate. It takes a single argument of any type and returns a bool.

BinaryPredicate: Takes two arguments of any two types and returns a bool.

StrictWeakOrdering: A binary predicate that says that if you have two objects and neither one is less than the other, they can be regarded as equivalent to each other.

In addition, there are sometimes qualifications on object types that are passed to an algorithm. These qualifications are given in the template argument type identifier name:

LessThanComparable: A class that has a less-than operator<.

Assignable: A class that has an assignment operator= for its own type.

EqualityComparable: A class that has an equivalence operator== for its own type.

Automatic creation of function objects

The STL has, in the header file <functional>, a set of templates that will automatically create function objects for you. These generated function objects are admittedly simple, but the goal is to provide very basic functionality that will allow you to compose more complicated function objects, and in many situations this is all you’ll need. Also, you’ll see that there are some function object adapters that allow you to take the simple function objects and make them slightly more complicated.

Here are the templates that generate function objects, along with the expressions that they effect.

Name

Type

Result produced by generated function object

plus

BinaryFunction

arg1 + arg2

minus

BinaryFunction

arg1 - arg2

multiplies

BinaryFunction

arg1 * arg2

divides

BinaryFunction

arg1 / arg2

modulus

BinaryFunction

arg1 % arg2

negate

UnaryFunction

- arg1

equal_to

BinaryPredicate

arg1 == arg2

not_equal_to

BinaryPredicate

arg1 != arg2

greater

BinaryPredicate

arg1 > arg2

less

BinaryPredicate

arg1 < arg2

greater_equal

BinaryPredicate

arg1 >= arg2

less_equal

BinaryPredicate

arg1 <= arg2

logical_and

BinaryPredicate

arg1 && arg2

logical_or

BinaryPredicate

arg1 || arg2

logical_not

UnaryPredicate

!arg1

not1( )

Unary Logical

!(UnaryPredicate(arg1))

not2( )

Binary Logical

!(BinaryPredicate(arg1, arg2))

The following example provides simple tests for each of the built-in basic function object templates. This way, you can see how to use each one, along with their resulting behavior.

//: C21:FunctionObjects.cpp
// Using the predefined function object templates
// in the Standard C++ library
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
// This will be defined shortly:
#include "Generators.h"
using namespace std;

template<typename T> 
void print(vector<T>& v, char* msg = "") {
  if(*msg != 0)
    cout << msg << ":" << endl;
  copy(v.begin(), v.end(), 
    ostream_iterator<T>(cout, " "));
  cout << endl;
}

template<typename Contain, typename UnaryFunc> 
void testUnary(Contain& source, Contain& dest,
  UnaryFunc f) {
  transform(source.begin(), source.end(), 
    dest.begin(), f);
}

template<typename Contain1, typename Contain2, 
  typename BinaryFunc> 
void testBinary(Contain1& src1, Contain1& src2,
  Contain2& dest, BinaryFunc f) {
  transform(src1.begin(), src1.end(), 
    src2.begin(), dest.begin(), f);
}

// Executes the expression, then stringizes the
// expression into the print statement:
#define T(EXPR) EXPR; print(r, "After " #EXPR);
// For Boolean tests:
#define B(EXPR) EXPR; print(br,"After " #EXPR);

// Boolean random generator:
struct BRand {
  BRand() { srand(time(0)); }
  bool operator()() {
    return rand() > RAND_MAX / 2;
  }
};

int main() {
  const int sz = 10;
  const int max = 50;
  vector<int> x(sz), y(sz), r(sz);
  // An integer random number generator:
  URandGen urg(max);
  generate_n(x.begin(), sz, urg);
  generate_n(y.begin(), sz, urg);
  // Add one to each to guarantee nonzero divide:
  transform(y.begin(), y.end(), y.begin(),
    bind2nd(plus<int>(), 1));
  // Guarantee one pair of elements is ==:
  x[0] = y[0];
  print(x, "x");
  print(y, "y");
  // Operate on each element pair of x & y,
  // putting the result into r:
  T(testBinary(x, y, r, plus<int>()));
  T(testBinary(x, y, r, minus<int>()));
  T(testBinary(x, y, r, multiplies<int>()));
  T(testBinary(x, y, r, divides<int>()));
  T(testBinary(x, y, r, modulus<int>()));
  T(testUnary(x, r, negate<int>()));
  vector<bool> br(sz); // For Boolean results
  B(testBinary(x, y, br, equal_to<int>()));
  B(testBinary(x, y, br, not_equal_to<int>()));
  B(testBinary(x, y, br, greater<int>()));
  B(testBinary(x, y, br, less<int>()));
  B(testBinary(x, y, br, greater_equal<int>()));
  B(testBinary(x, y, br, less_equal<int>()));
  B(testBinary(x, y, br, 
    not2(greater_equal<int>())));
  B(testBinary(x,y,br,not2(less_equal<int>())));
  vector<bool> b1(sz), b2(sz);
  generate_n(b1.begin(), sz, BRand());
  generate_n(b2.begin(), sz, BRand());
  print(b1, "b1");
  print(b2, "b2");
  B(testBinary(b1, b2, br, logical_and<int>()));
  B(testBinary(b1, b2, br, logical_or<int>()));
  B(testUnary(b1, br, logical_not<int>()));
  B(testUnary(b1, br, not1(logical_not<int>())));
} ///:~ 

To keep this example small, some tools are created. The print( ) template is designed to print any vector<T>, along with an optional message. Since print( ) uses the STL copy( ) algorithm to send objects to cout via an ostream_iterator, the ostream_iterator must know the type of object it is printing, and therefore the print( ) template must know this type also. However, you’ll see in main( ) that the compiler can deduce the type of T when you hand it a vector<T>, so you don’t have to hand it the template argument explicitly; you just say print(x) to print the vector<T> x .

The next two template functions automate the process of testing the various function object templates. There are two since the function objects are either unary or binary. In testUnary( ), you pass a source and destination vector, and a unary function object to apply to the source vector to produce the destination vector. In testBinary( ), there are two source vectors which are fed to a binary function to produce the destination vector. In both cases, the template functions simply turn around and call the transform( ) algorithm, although the tests could certainly be more complex.

For each test, you want to see a string describing what the test is, followed by the results of the test. To automate this, the preprocessor comes in handy; the T( ) and B( ) macros each take the expression you want to execute. They call that expression, then call print( ), passing it the result vector (they assume the expression changes a vector named r and br, respectively), and to produce the message the expression is “string-ized” using the preprocessor. So that way you see the code of the expression that is executed followed by the result vector.

The last little tool is a generator object that creates random bool values. To do this, it gets a random number from rand( ) and tests to see if it’s greater than RAND_MAX/2. If the random numbers are evenly distributed, this should happen half the time.

In main( ), three vector<int> are created: x and y for source values, and r for results. To initialize x and y with random values no greater than 50, a generator of type URandGen is used; this will be defined shortly. Since there is one operation where elements of x are divided by elements of y, we must ensure that there are no zero values of y. This is accomplished using the transform( ) algorithm, taking the source values from y and putting the results back into y. The function object for this is created with the expression:

bind2nd(plus<int>(), 1)

This uses the plus function object that adds two objects together. It is thus a binary function which requires two arguments; we only want to pass it one argument (the element from y) and have the other argument be the value 1. A “binder” does the trick (we will look at these next). The binder in this case says “make a new function object which is the plus function object with the second argument fixed at 1.”

Another of the tests in the program compares the elements in the two vectors for equality, so it is interesting to guarantee that at least one pair of elements is equivalent; in this case element zero is chosen.

Once the two vectors are printed, T( ) is used to test each of the function objects that produces a numerical value, and then B( ) is used to test each function object that produces a Boolean result. The result is placed into a vector<bool>, and when this vector is printed it produces a ‘ 1’ for a true value and a ‘ 0’ for a false value.

Binders

It’s common to want to take a binary function object and to “bind” one of its arguments to a constant value. After binding, you get a unary function object.

For example, suppose you want to find integers that are less than a particular value, say 20. Sensibly enough, the STL algorithms have a function called find_if( ) that will search through a sequence; however, find_if( ) requires a unary predicate to tell it if this is what you’re looking for. This unary predicate can of course be some function object that you have written by hand, but it can also be created using the built-in function object templates. In this case, the less template will work, but that produces a binary predicate, so we need some way of forming a unary predicate. The binder templates (which work with any binary function object, not just binary predicates) give you two choices:

bind1st(const BinaryFunction& op, const T& t);

bind2nd(const BinaryFunction& op, const T& t);

Both bind t to one of the arguments of op, but bind1st( ) binds t to the first argument, and bind2nd( ) binds t to the second argument. With less, the function object that provides the solution to our exercise is:

bind2nd(less<int>(), 20);

This produces a new function object that returns true if its argument is less than 20. Here it is, used with find_if( ):

//: C21:Binder1.cpp
// Using STL "binders"
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include "Generators.h"
#include "copy_if.h"
using namespace std;

int main() {
  const int sz = 10;
  const int max = 40;
  vector<int> a(sz), r;
  URandGen urg(max);
  ostream_iterator<int> out(cout, " ");
  generate_n(a.begin(), sz, urg);
  copy(a.begin(), a.end(), out);
  int* d = find_if(a.begin(), a.end(), 
    bind2nd(less<int>(), 20));
  cout << "\n *d = " << *d << endl;
  // copy_if() is not in the Standard C++ library
  // but is defined later in the chapter:
  copy_if(a.begin(), a.end(), back_inserter(r),
    bind2nd(less<int>(), 20));
  copy(r.begin(), r.end(), out);
  cout << endl;
} ///:~ 

The vector<int> a is filled with random numbers between 0 and max. find_if( ) finds the first element in a that satisfies the predicate (that is, which is less than 20) and returns an iterator to it (here, the type of the iterator is actually just int* although I could have been more precise and said vector<int>::iterator instead).

A more interesting algorithm to use is copy_if( ), which isn’t part of the STL but is defined at the end of this chapter. This algorithm only copies an element from the source to the destination if that element satisfies a predicate. So the resulting vector will only contain elements that are less than 20.

Here’s a second example, using a vector<string> and replacing strings that satisfy particular conditions:

//: C21:Binder2.cpp
// More binders
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <functional>
using namespace std;

int main() {
  ostream_iterator<string> out(cout, " ");
  vector<string> v, r;
  v.push_back("Hi");
  v.push_back("Hi");
  v.push_back("Hey");
  v.push_back("Hee");
  v.push_back("Hi");
  copy(v.begin(), v.end(), out);
  cout << endl;
  // Replace each "Hi" with "Ho":
  replace_copy_if(v.begin(), v.end(), 
    back_inserter(r), 
    bind2nd(equal_to<string>(), "Hi"), "Ho");
  copy(r.begin(), r.end(), out);
  cout << endl;
  // Replace anything that's not "Hi" with "Ho":
  replace_if(v.begin(), v.end(), 
    not1(bind2nd(equal_to<string>(),"Hi")),"Ho");
  copy(v.begin(), v.end(), out);
  cout << endl;
} ///:~ 

This uses another pair of STL algorithms. The first, replace_copy_if( ), copies each element from a source range to a destination range, performing replacements on those that satisfy a particular unary predicate. The second, replace_if( ), doesn’t do any copying but instead performs the replacements directly into the original range.

A binder doesn’t have to produce a unary predicate; it can also create a unary function (that is, a function that returns something other than bool). For example, suppose you’d like to multiply every element in a vector by 10. Using a binder with the transform( ) algorithm does the trick:

//: C21:Binder3.cpp
// Binders aren't limited to producing predicates
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include "Generators.h"
using namespace std;

int main() {
  ostream_iterator<int> out(cout, " ");
  vector<int> v(15);
  generate(v.begin(), v.end(), URandGen(20));
  copy(v.begin(), v.end(), out);
  cout << endl;
  transform(v.begin(), v.end(), v.begin(),
    bind2nd(multiplies<int>(), 10));
  copy(v.begin(), v.end(), out);
  cout << endl;
} ///:~ 

Since the third argument to transform( ) is the same as the first, the resulting elements are copied back into the source vector. The function object created by bind2nd( ) in this case produces an int result.

The “bound” argument to a binder cannot be a function object, but it does not have to be a compile-time constant. For example:

//: C21:Binder4.cpp
// The bound argument does not have to be a 
// compile-time constant.
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include "copy_if.h"
#include "PrintSequence.h"
#include "../require.h"
using namespace std;

int boundedRand() { return rand() % 100; }

int main(int argc, char* argv[]) {
  requireArgs(argc, 1, "usage: Binder4 int");
  const int sz = 20;
  int a[20], b[20] = {0};
  generate(a, a + sz, boundedRand);
  int* end = copy_if(a, a + sz, b, 
    bind2nd(greater<int>(), atoi(argv[1])));
  // Sort for easier viewing:
  sort(a, a + sz);
  sort(b, end);
  print(a, a + sz, "array a", " ");
  print(b, end, "values greater than yours"," ");
} ///:~ 

Here, an array is filled with random numbers between 0 and 100, and the user provides a value on the command line. In the copy_if( ) call, you can see that the bound argument to bind2nd( ) is the result of the function call atoi( ) (from <cstdlib>).

Function pointer adapters

Any place in an STL algorithm where a function object is required, it’s very conceivable that you’d like to use a function pointer instead. Actually, you can use an ordinary function pointer – that’s how the STL was designed, so that a “function object” can actually be anything that can be dereferenced using an argument list. For example, the rand( ) random number generator can be passed to generate( ) or generate_n( ) as a function pointer, like this:

//: C21:RandGenTest.cpp
// A little test of the random number generator
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
  const int sz = 10000;
  int v[sz];
  srand(time(0)); // Seed the random generator
  for(int i = 0; i < 300; i++) {
    // Using a naked pointer to function:
    generate(v, v + sz, std::rand);
    int count = count_if(v, v + sz, 
      bind2nd(greater<int>(), RAND_MAX/2));
    cout << (((double)count)/((double)sz)) * 100
      << ' ';
  }
} ///:~ 

The “iterators” in this case are just the starting and past-the-end pointers for the array v, and the generator is just a pointer to the standard library rand( ) function. The program repeatedly generates a group of random numbers, then it uses the STL algorithm count_if( ) and a predicate that tells whether a particular element is greater than RAND_MAX/2. The result is the number of elements that match this criterion; this is divided by the total number of elements and multiplied by 100 to produce the percentage of elements greater than the midpoint. If the random number generator is reasonable, this value should hover at around 50% (of course, there are many other tests to determine if the random number generator is reasonable).

The ptr_fun( ) adapters take a pointer to a function and turn it into a function object. They are not designed for a function that takes no arguments, like the one above (that is, a generator). Instead, they are for unary functions and binary functions. However, these could also be simply passed as if they were function objects, so the ptr_fun( ) adapters might at first appear to be redundant. Here’s an example where using ptr_fun( ) and simply passing the address of the function both produce the same results:

//: C21:PtrFun1.cpp
// Using ptr_fun() for single-argument functions
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;

char* n[] = { "01.23", "91.370", "56.661",
  "023.230", "19.959", "1.0", "3.14159" };
const int nsz = sizeof n / sizeof *n;

template<typename InputIter>
void print(InputIter first, InputIter last) {
  while(first != last)
    cout << *first++ << "\t";
  cout << endl;
}

int main() {
  print(n, n + nsz);
  vector<double> vd;
  transform(n, n + nsz, back_inserter(vd), atof);
  print(vd.begin(), vd.end());
  transform(n,n + nsz,vd.begin(), ptr_fun(atof));
  print(vd.begin(), vd.end());
} ///:~ 

The goal of this program is to convert an array of char* which are ASCII representations of floating-point numbers into a vector<double>. After defining this array and the print( ) template (which encapsulates the act of printing a range of elements), you can see transform( ) used with atof( ) as a “naked” pointer to a function, and then a second time with atof passed to ptr_fun( ). The results are the same. So why bother with ptr_fun( )? Well, the actual effect of ptr_fun( ) is to create a function object with an operator( ). This function object can then be passed to other template adapters, such as binders, to create new function objects. As you’ll see a bit later, the SGI extensions to the STL contain a number of other function templates to enable this, but in the Standard C++ STL there are only the bind1st( ) and bind2nd( ) function templates, and these expect binary function objects as their first arguments. In the above example, only the ptr_fun( ) for a unary function is used, and that doesn’t work with the binders. So ptr_fun( ) used with a unary function in Standard C++ really is redundant (note that Gnu g++ uses the SGI STL).

With a binary function and a binder, things can be a little more interesting. This program produces the squares of the input vector d:

//: C21:PtrFun2.cpp
// Using ptr_fun() for two-argument functions
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include <cmath>
using namespace std;

double d[] = { 01.23, 91.370, 56.661,
  023.230, 19.959, 1.0, 3.14159 };
const int dsz = sizeof d / sizeof *d;

int main() {
  vector<double> vd;
  transform(d, d + dsz, back_inserter(vd), 
    bind2nd(ptr_fun(pow), 2.0));
  copy(vd.begin(), vd.end(),
    ostream_iterator<double>(cout, " "));
  cout << endl;    
} ///:~ 

Here, ptr_fun( ) is indispensable; bind2nd( ) must have a function object as its first argument and a pointer to function won’t cut it.

A trickier problem is that of converting a member function into a function object suitable for using in the STL algorithms. As a simple example, suppose we have the “shape” problem and would like to apply the draw( ) member function to each pointer in a coFntainer of Shape:

//: C21:MemFun1.cpp
// Applying pointers to member functions
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include "../purge.h"
using namespace std;

class Shape {
public:
  virtual void draw() = 0;
  virtual ~Shape() {}
};

class Circle : public Shape {
public:
  virtual void draw() {
    cout << "Circle::Draw()" << endl;
  }
  ~Circle() {
    cout << "Circle::~Circle()" << endl;
  }
};

class Square : public Shape {
public:
  virtual void draw() {
    cout << "Square::Draw()" << endl;
  }
  ~Square() {
    cout << "Square::~Square()" << endl;
  }
};

int main() {
  vector<Shape*> vs;
  vs.push_back(new Circle);
  vs.push_back(new Square);
  for_each(vs.begin(), vs.end(), 
    mem_fun(&Shape::draw));
  purge(vs);
} ///:~ 

The for_each( ) function does just what it sounds like it does: passes each element in the range determined by the first two (iterator) arguments to the function object which is its third argument. In this case we want the function object to be created from one of the member functions of the class itself, and so the function object’s “argument” becomes the pointer to the object that the member function is called for. To produce such a function object, the mem_fun( ) template takes a pointer to member as its argument.

The mem_fun( ) functions are for producing function objects that are called using a pointer to the object that the member function is called for, while mem_fun_ref( ) is used for calling the member function directly for an object. One set of overloads of both mem_fun( ) and mem_fun_ref( ) are for member functions that take zero arguments and one argument, and this is multiplied by two to handle const vs. non- const member functions. However, templates and overloading takes care of sorting all of that out; all you need to remember is when to use mem_fun( ) vs. mem_fun_ref( ).

Suppose you have a container of objects (not pointers) and you want to call a member function that takes an argument. The argument you pass should come from a second container of objects. To accomplish this, the second overloaded form of the transform( ) algorithm is used:

//: C21:MemFun2.cpp
// Applying pointers to member functions
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;

class Angle {
  int degrees;
public:
  Angle(int deg) : degrees(deg) {}
  int mul(int times) {
    return degrees *= times;
  }
};

int main() {
  vector<Angle> va;
  for(int i = 0; i < 50; i += 10)
    va.push_back(Angle(i));
  int x[] = { 1, 2, 3, 4, 5 };
  transform(va.begin(), va.end(), x,
    ostream_iterator<int>(cout, " "),
    mem_fun_ref(&Angle::mul));
  cout << endl;
} ///:~ 

Because the container is holding objects, mem_fun_ref( ) must be used with the pointer-to-member function. This version of transform( ) takes the start and end point of the first range (where the objects live), the starting point of second range which holds the arguments to the member function, the destination iterator which in this case is standard output, and the function object to call for each object; this function object is created with mem_fun_ref( ) and the desired pointer to member. Notice the transform( ) and for_each( ) template functions are incomplete; transform( ) requires that the function it calls return a value and there is no for_each( ) that passes two arguments to the function it calls. Thus, you cannot call a member function that returns void and takes an argument using transform( ) or for_each( ).

Any member function works, including those in the Standard libraries. For example, suppose you’d like to read a file and search for blank lines; you can use the string::empty( ) member function like this:

//: C21:FindBlanks.cpp
// Demonstrate mem_fun_ref() with string::empty()
#include <algorithm>
#include <list>
#include <string>
#include <fstream>
#include <functional>
#include "../require.h"
using namespace std;

typedef list<string>::iterator LSI;

LSI blank(LSI begin, LSI end) {
   return find_if(begin, end, 
     mem_fun_ref(&string::empty));
}

int main(int argc, char* argv[]) {
  requireArgs(argc, 1);
  ifstream in(argv[1]);
  assure(in, argv[1]);  
  list<string> ls;
  string s;
  while(getline(in, s))
    ls.push_back(s);
  LSI lsi = blank(ls.begin(), ls.end());
  while(lsi != ls.end()) {
    *lsi = "A BLANK LINE";
    lsi = blank(lsi, ls.end());
  }
  string f(argv[1]);
  f += ".out";
  ofstream out(f.c_str());
  copy(ls.begin(), ls.end(), 
    ostream_iterator<string>(out, "\n"));
} ///:~ 

The blank( ) function uses find_if( ) to locate the first blank line in the given range using mem_fun_ref( ) with string::empty( ). After the file is opened and read into the list, blank( ) is called repeated times to find every blank line in the file. Notice that subsequent calls to blank( ) use the current version of the iterator so it moves forward to the next one. Each time a blank line is found, it is replaced with the characters “A BLANK LINE.” All you have to do to accomplish this is dereference the iterator, and you select the current string.

SGI extensions

The SGI STL (mentioned at the end of the previous chapter) also includes additional function object templates, which allow you to write expressions that create even more complicated function objects. Consider a more involved program which converts strings of digits into floating point numbers, like PtrFun2.cpp but more general. First, here’s a generator that creates strings of integers that represent floating-point values (including an embedded decimal point):

//: C21:NumStringGen.h
// A random number generator that produces 
// strings representing floating-point numbers
#ifndef NUMSTRINGGEN_H
#define NUMSTRINGGEN_H
#include <string>
#include <cstdlib>
#include <ctime>

class NumStringGen {
  const int sz; // Number of digits to make
public:
  NumStringGen(int ssz = 5) : sz(ssz) { 
    std::srand(std::time(0)); 
  }
  std::string operator()() {
    static char n[] = "0123456789";
    const int nsz = 10;
    std::string r(sz, ' ');
    for(int i = 0; i < sz; i++)
      if(i == sz/2)
        r[i] = '.'; // Insert a decimal point
      else
        r[i] = n[std::rand() % nsz];
    return r;
  }
};
#endif // NUMSTRINGGEN_H ///:~ 

You tell it how big the strings should be when you create the NumStringGen object. The random number generator is used to select digits, and a decimal point is placed in the middle.

The following program (which works with the Standard C++ STL without the SGI extensions) uses NumStringGen to fill a vector<string>. However, to use the Standard C library function atof( ) to convert the strings to floating-point numbers, the string objects must first be turned into char pointers, since there is no automatic type conversion from string to char*. The transform( ) algorithm can be used with mem_fun_ref( ) and string::c_str( ) to convert all the strings to char*, and then these can be transformed using atof:

//: C21:MemFun3.cpp
// Using mem_fun()
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include "NumStringGen.h"
using namespace std;

int main() {
  const int sz = 9;
  vector<string> vs(sz);
  // Fill it with random number strings:
  generate(vs.begin(), vs.end(), NumStringGen());
  copy(vs.begin(), vs.end(), 
    ostream_iterator<string>(cout, "\t"));
  cout << endl;
  const char* vcp[sz];
  transform(vs.begin(), vs.end(), vcp, 
    mem_fun_ref(&string::c_str));
  vector<double> vd;
  transform(vcp,vcp + sz,back_inserter(vd),
    std::atof);
  copy(vd.begin(), vd.end(), 
    ostream_iterator<double>(cout, "\t"));
  cout << endl;
} ///:~ 

The SGI extensions to the STL contain a number of additional function object templates that accomplish more detailed activities than the Standard C++ function object templates, including identity (returns its argument unchanged), project1st and project2nd (to take two arguments and return the first or second one, respectively), select1st and select2nd (to take a pair object and return the first or second element, respectively), and the “compose” function templates.

If you’re using the SGI extensions, you can make the above program denser using one of the two “compose” function templates. The first, compose1(f1, f2), takes the two function objects f1 and f2 as its arguments. It produces a function object that takes a single argument, passes it to f2, then takes the result of the call to f2 and passes it to f1. The result of f1 is returned. By using compose1( ), the process of converting the string objects to char*, then converting the char* to a floating-point number can be combined into a single operation, like this:

//: C21:MemFun4.cpp
// Using the SGI STL compose1 function
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include "NumStringGen.h"
using namespace std;

int main() {
  const int sz = 9;
  vector<string> vs(sz);
  // Fill it with random number strings:
  generate(vs.begin(), vs.end(), NumStringGen());
  copy(vs.begin(), vs.end(), 
    ostream_iterator<string>(cout, "\t"));
  cout << endl;
  vector<double> vd;
  transform(vs.begin(), vs.end(), back_inserter(vd),
    compose1(ptr_fun(atof), 
      mem_fun_ref(&string::c_str)));
  copy(vd.begin(), vd.end(), 
    ostream_iterator<double>(cout, "\t"));
  cout << endl;
} ///:~ 

You can see there’s only a single call to transform( ) now, and no intermediate holder for the char pointers.

The second “compose” function is compose2( ), which takes three function objects as its arguments. The first function object is binary (it takes two arguments), and its arguments are the results of the second and third function objects, respectively. The function object that results from compose2( ) expects one argument, and it feeds that argument to the second and third function objects. Here is an example:

//: C21:Compose2.cpp
// Using the SGI STL compose2() function
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include <cstdlib>
#include <ctime>
#include "copy_if.h"
using namespace std;

int main() {
  srand(time(0));
  vector<int> v(100);
  generate(v.begin(), v.end(), rand);
  transform(v.begin(), v.end(), v.begin(),
    bind2nd(divides<int>(), RAND_MAX/100));
  vector<int> r;
  copy_if(v.begin(), v.end(), back_inserter(r),
    compose2(logical_and<bool>(),
      bind2nd(greater_equal<int>(), 30),
      bind2nd(less_equal<int>(), 40)));
  sort(r.begin(), r.end());
  copy(r.begin(), r.end(),
    ostream_iterator<int>(cout, " "));
  cout << endl;
} ///:~ 

The vector<int> v is first filled with random numbers. To cut these down to size, the transform( ) algorithm is used to divide each value by RAND_MAX/100, which will force the values to be between 0 and 100 (making them more readable). The copy_if( ) algorithm defined later in this chapter is then used, along with a composed function object, to copy all the elements that are greater than or equal to 30 and less than or equal to 40 into the destination vector<int> r . Just to show how easy it is, r is sorted, and then displayed.

The arguments of compose2( ) say, in effect:

(x >= 30) && (x <= 40)

You could also take the function object that comes from a compose1( ) or compose2( ) call and pass it into another “compose” expression ... but this could rapidly get very difficult to decipher.

Instead of all this composing and transforming, you can write your own function objects ( without using the SGI extensions) as follows:

//: C21:NoCompose.cpp
// Writing out the function objects explicitly
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include <cstdlib>
#include <ctime>
#include "copy_if.h"
using namespace std;

class Rgen {
  const int max;
public:
  Rgen(int mx = 100) : max(RAND_MAX/mx) {
    srand(time(0));
  }
  int operator()() { return rand() / max; }
};

class BoundTest {
  int top, bottom;
public:
  BoundTest(int b, int t) : bottom(b), top(t) {}
  bool operator()(int arg) {
    return (arg >= bottom) && (arg <= top);
  }
};

int main() {
  vector<int> v(100);
  generate(v.begin(), v.end(), Rgen());
  vector<int> r;
  copy_if(v.begin(), v.end(), back_inserter(r),
    BoundTest(30, 40));
  sort(r.begin(), r.end());
  copy(r.begin(), r.end(),
    ostream_iterator<int>(cout, " "));
  cout << endl;
} ///:~ 

There are a few more lines of code, but you can’t deny that it’s much clearer and easier to understand, and therefore to maintain.

We can thus observe two drawbacks to the SGI extensions to the STL. The first is simply that it’s an extension; yes, you can download and use them for free so the barriers to entry are low, but your company may be conservative and decide that if it’s not in Standard C++, they don’t want to use it. The second drawback is complexity. Once you get familiar and comfortable with the idea of composing complicated functions from simple ones you can visually parse complicated expressions and figure out what they mean. However, my guess is that most people will find anything more than what you can do with the Standard, non-extended STL function object notation to be overwhelming. At some point on the complexity curve you have to bite the bullet and write a regular class to produce your function object, and that point might as well be the point where you can’t use the Standard C++ STL. A stand-alone class for a function object is going to be much more readable and maintainable than a complicated function-composition expression (although my sense of adventure does lure me into wanting to experiment more with the SGI extensions...).

As a final note, you can’t compose generators; you can only create function objects whose operator( ) requires one or two arguments.

Contents | Prev | Next


Go to CodeGuru.com
Contact: webmaster@codeguru.com
© Copyright 1997-1999 CodeGuru