Lambda didn't (or won't) kill the expression template star

Now that C++0x is on it's way, and many compilers already implement lambdas, it may be thought that the venerable "functor" is on it's way out. Well aside from the obvious reasons of supporting legacy code, that's simply not true. operator() is here to stay, and I will tell you why.

Lambdas, though convenient, are opaque. You can't peek inside of a lambda or peel back it's inner workings, and the vast majority of the time, that's fine, you don't need to. The same is true for normal named functions and member functions. On occasion however, a slightly more transparent tool can be useful, and operator() can help you build such translucent functions.

Let me try to justify this with an example. LLVM is a library for building compiler backends. It is written in C++, and it happens to have a coding standards document. One of the style points is "Turn Predicate Loops into Predicate Functions".

Basically, instead of code like

bool pred = false;
for(unsigned i = 0; i < list.size(); ++i)
{
  if( list[i].satisfies() )
  {
     pred = true;
     break;
  }
}

if( pred )
{
  ...
}

You should have code like

if( TestPred(list) )
{
  ...
}

They have their justifications, which you can read if you're interested. This really isn't about whether this is a good idea or not, but rather how to write TestPred. There is an obvious approach:

bool TestPred(const std::vector<Something>& list)
{
  for(unsigned i = 0; i < list.size(); ++i)
  {
    if( list[i].satisfies() ) return true;
  }
  return false;
}

The problem with this, is that you can't reuse the predicate. Or rather, that you can, but only in a very specific way. If you need to test a std::list of Something instead you need to either copy the list or duplicate the code. Worse, if you don't know what the code is, you don't even have duplication as an option.

A brief aside, yes a solution to this mess would be to just use std::find_if in the first place. This is just however the motivating example that came to mind when I happened to be reading the LLVM coding guidelines, so bear with me.

So we can change TestPred to operate on iterators. Now we can use it with list, vector, etc.

template <typename FwdIter>
bool TestPred(FwdIter begin, FwdIter end)
{
  for(FwdIter i = begin; i != end; ++i)
  {
    if( i->satisfies() ) return true;
  }
  return false;
  // or return find_if(begin, end, [](const Something& s) { return s.satisfies(); }) != end
}

But before we had the nice feature of being able to call this on a std::vector directly. We could add overloads for that, but that gets tedious especially since we're writing one of these functions every time we have a new predicate we need to loop over. We can use templates to let us get that std::vector overload back (and more, std::list for example, and your plain old array) by writing the code for iteration once and plugging in the varying i->satisfies part.

template<typename F>
struct RangedAnyPredicate
{
 typedef F Tester;
 template<typename FwdIter>
   bool operator()(FwdIter begin, FwdIter end) const
   {
     for(FwdIter i = begin; i != end; ++i)
     {
       if(F::test(*i))
       {
         return true;
       }
     }
     return false;
   }
};

struct satisfier
{
 typedef const Something& testee_type;
 static bool test(const Something& s)
 {
   return s.satifies();
 }
};

static RangedAnyPredicate<satisfier> TestPred;

Here we've extracted out just the looping over part. TestPred will behave almost identically to our templated on a pair of iterators version of the function (exceptions being things like, we can't pass this TestPred around as a function pointer). This is more typing that previous version of course, even with multiple predicates the overhead of a struct for each one is high. Where it starts to pay dividends is when provide more overloads for free. We're going to need some traits to do that, and again while this is a bunch of code up front, some of these traits are independently useful and already exist.

We want to be able to call this on two iterators, on a container with begin and end methods, and on a standard array. We can distinguish between the two argument and single argument forms easily with the normal overloading mechanism. For distinguishing between containers with begin and end and standard arrays we'll assume anything not an array should have a begin and an end.

So to detect arrays will use an is_array trait:

template<typename T>
struct is_array
{ enum {val = false}; };

template<typename T, long N>
struct is_array<T [N]>
{ enum {val = true}; };

We can then use this information to decide to either call TestPred(arg.begin(), arg.end()) or TestPred(arg, arg + N).

 template<bool C>
    struct do_test;

    template<>
    struct do_test<true>
    {
       template <typename Self, typename T, int N>
       static bool go(const Self& self, T (&a)[N])
       {
         return self(a, a + N);
       }
   };

   template<>
   struct do_test<false>
   {
     template<typename Self, typename C>
     static bool go(const Self& self, const C& c)
     {
       return self(c.begin(), c.end());
     }
   };

   ...
   // back inside RangedAnyPredicate
    template<typename Container>
    bool operator()(const Container& c) const
    {
      return do_test<is_array<Container>::val>::go(*this, c);
    }
   ...

Now we've got overloads for vector, list, and any other container that might come along and behave like a standard sequence, as well as old fashioned arrays.

But there's more. You may have noticed we included a Tester typedef in RangedAnyPredicate. This is where the ability to make a functor less opaque than a regular function or a lambda starts to be useful. Let's say we have two predicates, PredA and PredB. And furthermore the coding guidelines were followed and we have TestPredA and TestPredB functions to work with. If we want to find out if a list has an eliminate that satisfies PredA or PredB we can do the obvious:

if( TestPredA(list) || TestPredB(list) )
{
   ...
}

But this is C++! The code above has the potential to needlessly traverse the list twice. We've got to be able to do something about that, right? Well not if TestPredA and TestPredB are regular functions. We can write a third function that does the or-ing, but it can't peek inside the functions. If however, we use RangedAnyPredicate to define TestPredA and TestPredB we can extend them as needed. First will need a predicate to represent the or-ing of the internal predicates of A and B:

template
struct OrCombiner
{
  typedef typename Lhs::testee_type testee_type;
  static bool test(testee_type testee)
  {
    return Lhs::test(testee) || Rhs::test(testee);
  }
};

Next we use a little operator-overloading-fu in RangedAnyPredicate to make this easy to use:

// Back in RangedAnyPredicate
template<typename TestF>
    RangedAnyPredicate< OrCombiner<F, TestF> > operator|(RangedAnyPredicate  )
    {
      return RangedAnyPredicate< OrCombiner<F, TestF> >();
    }

Now our code becomes

if( (TestPredA | TestPredB)(list) )
{
   ...
}

and only one pass is made over the list. If you want different semantics, of course you can just simply use the prior code. The same can be done for logical and as well of course.

This was of course a contrived example, but I hope of demonstrated how the functor still has its place, even in a world of lambdas.