Help understanding the working of Function Objects?

Question

I found this code on Wikipedia

class compare_class {
  public:
  bool operator()(int A, int B) const {
    return A < B;
  }
};
...
// Declaration of C++ sorting function.
template <class ComparisonFunctor> 
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);
...
int main() {
    int items[] = {4, 3, 1, 2};
    compare_class functor;
    sort_ints(items, sizeof(items)/sizeof(items[0]), functor);
}

At first I wondered how the A and B parameters got passed to operator()(int A, int B), when the functor was mentioned in sort_ints without even any parenthesis.

Then I figured that A and B are being passed to the function object inside the sort_ints function. But then, shouldn't the declaration of sort_ints have 'ComparisonFunctor*** c' instead of 'ComparisonFunctor c', since it's receiving the address of a function?

Inside the sort_ints function, would the function call to the functor be done something like this?

functor(*begin_items, *(begin_items+1));

Answer 1

To understand why sort_ints takes its parameter by value, you have to remember that the object being passed into it as the comparator is not necessarily a function pointer. If, for example, you're using the compare_class function object to do the comparison, then what you're passing into the function is a concrete object of type compare_class. You're not passing in the address of compare_class::operator(), since operator() is a member function, not a free function. That is, the following code:

compare_class myComparator;
myComparator(a, b);

translates into

compare_class myComparator;
myComparator.operator() (a, b);

Consequently, the parameter needs to take in the comparator by value rather than by pointer, since it needs a receiver object, rather than a pointer to a member function or a pointer to the receiver object.

Answer 2

As you've noted, there's nothing in the usage of sort_ints that hints at its requirements of the comparison functor:

compare_class functor;
sort_ints(items, sizeof(items)/sizeof(items[0]), functor);

There's nothing in sort_ints itself either:

template <class ComparisonFunctor>
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);

And in class_compare, we can only deduce the functionality that will be used by observing it offers no other functionality:

class compare_class
{
  public:
     bool operator()(int A, int B) const { return A < B; }
};

The compiler does indeed leave it until it tries to compile the implementation of sort_ints, using the types with which it's instantiated, before it works out whether this all hangs together. sort_ints will have to have exactly the kind of statement you mention:

c(*begin_items, *(begin_items+1));    // note: functor argument is "c"

So, your understanding is correct on all counts. BUT, it's worth noting that the proposed C++0x feature called Concepts was intended to make the requirements of sort_int more explicit without looking at its implementation. Unfortunately, C++0x had to abandon this feature as there's been insufficient time and experience to ensure it's optimal. Hopefully a future version of C++ will incorporate such a feature. You can find lots of discussions of Concepts on the 'net, and they should help you understand the overall issue better.

It's an important issue because when you've only pieces of the puzzle - such as a sort_ints function you want to use but no example ComparisonFunctor, then you have to study the implementation of sort_ints to know how to create that Functor (unless you're super lucky and there's good, current documentation). You may accidentally make your code too dependent on the existing implementation, so that your code breaks or slows down unacceptably when the implementation of sort_int is changed slightly later - even if it is subtly enough not to break the test cases or other users' code or expectations. It's also likely that a small mistake in the provided ComparisonFunctor will produce a very convoluted and confusing compiler error message from somewhere in the guts of sort_int - that's not a nice way to provide a user with an abstracted service. Let's hope Concepts makes it in one day...!

Answer 3

Notice that, compare_class is a class. So it can be declared, passed as function parameter the way you use other classes.

Secondly, compare_class implementes operator(). This allows you to do the following:

compare_class obj;
obj(1, 2);

Now, the second statement in the above code fragment seems like a function call! So in a sense, any object of a class that implements operator() can be use like a function.

That's the point of function objects. Besides, it has other advantages over function pointers which you will find in the same link you've given in your post.

EDIT

Inside sort_ints(), functor is expected to do something like the following:

for (int i = 1; i < num_items; i++)
    if (c(begin_items[i-1], begin_items[i]))
    {
        // begin_items[i-1] is less than begin_items[i], do stuff
    }

Answer 4

Yes, that's correct. The function call operator is applied to the name of the object, not a method of the object. Furthermore, you are not passing an address of a function at all, you are passing (copying) an object. functor objects have no data members, only an operator ( ).