Callable Objects: Part 1

Exercise 0:

Create implementations of call_function_pointer and call_function_object which execute objects passed to them.

void call_function_pointer(void(*func)(int))
{
  func(42);
}

template <typename T>
void call_function_object(T obj)
{
  obj(42);
}

//Usage:
struct function_object
{
  void operator()(int val) const
  { std::cout << val << std::endl; }
};
void print_int(int val)
{ std::cout << val << std::endl; }

call_function(&print_int);
call_function_object(function_object());

The call syntax for function pointers and function objects is equivalent.

---

Exercise 1:

std::sort accepts any valid callable object. Using templates, it is able to generate a custom sort function for its predicate, which allows it to be much faster than other alternatives, depending on the sorting criterion and the argument types. First, show an implementation using a functions predicate:

bool greater_than_function(int lhs, int rhs)
{ return lhs > rhs; }
std::sort(v.begin(), v.end(), &greater_than_function);

---

Exercise 2:

Next, show an implementation using a function object (or functor, as used in common C++ parlance):

struct greater_than_functor
{
  bool operator()(int lhs, int rhs)
  { return lhs > rhs; }
};
std::sort(v.begin(), v.end(), greater_than_functor());

---

Question 1:

What are the pros and cons of using a function pointer versus using a function object?

Answer 1:

Writing a function may save a few keystrokes versus writing a functor. The actual usage is very similar -- the functor must be constructed, requiring an extra (), but both seem equally readable after some minor training. Speaking in terms of execution speed, functors with an inline operator() will execute much more quickly in templatized algorithms like std::sort. This is due to the compiler's ability to inline such code, whereas using function pointers typically inhibits that optimization [^1]. A typical run: 7.4 seconds when sorting with a function pointer, 4.5 seconds when sorting with a functor.

---

Question 2:

What are the pros and cons of using std::sort vs qsort?

Answer 2:

In addition to supporting any callable object, std::sort allows a much more natural syntax for the comparison function. Compare the predicate syntax:

//For qsort:
int greater_than_void_function(const void* lhs, const void* rhs)
{
  return *static_cast<const int*>(rhs) - *static_cast<const int*>(lhs);
}
//For std::sort:
bool greater_than_function(int lhs, int rhs)
{ return lhs > rhs; }

Furthermore, std::sort can be much faster with function objects (nearly a 2x speedup here), another benefit of its templatization. In fact, the only place where qsort wins handily wasn't a suggested comparison: The binary size of objects to link may be smaller with qsort than std::sort. Like most things in this list, it's also due to std::sort being templatized. There is one qsort implementation which all callers execute. std::sort, on the other hand, generates a new version (more or less) with each call with a different predicate. Furthermore, if many different translations units (read: cpp files) call sort with the same predicate, a different instance will still be generated by default. This can lead to longer compile times, larger object files, and longer linker times [^2]. With that said, std::sort is not going to be the straw that breaks the camel's back — use it to the exclusion of qsort in C++ code!

---

Given the following class:

class foo
{
public:
  explicit foo(int i)
    : val(i), dval(42.)
  {}

  int get_value() const
  { return val; }

private:
  friend bool operator==(const Foo& lhs, const Foo& rhs)
  { return lhs.val == rhs.val && lhs.dval == rhs.dval; }

  int val;
  double dval;
};

Exercise 3:

A function which sorts foo objects would look something like:

bool greater_than_foo_sort(const foo& lhs, const foo& rhs)
{ return lhs.get_value() > rhs.get_value(); }

Exercise 4:

A functor which sorts foo objects would look like:

struct greater_than_foo_sorter
{
  bool operator()(const foo& lhs, const foo& rhs) const
  { return lhs.get_value() > rhs.get_value(); }
};

Exercise 5:

And for masochism's sake, here's a qsort-friendly implementation:

int greater_than_void_function(const void* lhs, const void* rhs)
{
  return static_cast<const foo*>(rhs)->get_value() - static_cast<const foo*>(lhs)->get_value();
}

---

Question 3:

With reference to user-defined data types, what are the pros and cons of using std::sort with functions and functors, and qsort with void-pointer functions?

Answer 3:

The pros and cons are pretty much the same — see previous answers. All sort functions mentioned are generic enough to handle most input; but qsort requires more verbosity to achieve that [^3].

---

Exercise 6:

As a teaser for the next training, create a C++11 lambda which matches the behavior of greater_than_function.

std::sort(v.begin(), v.end(), [](int lhs, int rhs) { return lhs > rhs; });

Question 4:

How does the verbosity of lambdas compare with function pointers and functors? How does performance?

Answer 4:

Lambdas are approximately as verbose as regular function calls. The syntax is unlike anything else in C or C++ and may at least be surprising to those unfamiliar with them.

The performance of lambdas matches that of functors. In fact, the compiler generates a functor using the lambda — the inline declaration syntax is purely a matter of convenience. If the implementation of a lambda becomes very long, it may help readability to move it into a named function object. For short pieces of code, however, it can be much more readable.

---

Notes:

[^1] See Effective STL Item 46.

[^2] More exacting use of templatized code can result in incredibly long link times. It's tempting to live with long compile times, particularly if the file in question is infrequently modified. Long link times, however, must be endured each time the software is compiled. Take care with template instantiations on a large or growing code base!

[^3] qsort does suffer from one more drawback — it will not accept list input that is not stored sequentially in memory. std::vector can work with it; things like std::list and std::deque cannot.

Further Reading:

Effective STL Items 38 & 40, a new Scott Meyers article on const, auto and lambdas, and Stephan Lavavej's tutorial introduction to C++11 lambdas.