C ++ functor advantage - persistence

As a really trivial demonstration, consider Quick sort. We select a value (commonly referred to as the "pivot axis") and split the input collection into those that compare less than the pivot point and those that compare greater than or equal to axis ¹ .

The standard library already has std::partition

one that can do the partitioning itself - separates the collection from those items that meet a specified condition and those that don't. So, to do our splitting, we just need to provide a suitable predicate.

In this case, we need a simple comparison: return x < pivot;

. However, transmission of the rotation value becomes difficult each time. std::partition

just passes the value from the collection and asks "does this pass the test or not?" You have nothing to tell std::partition

what the current rotation value is and pass that to your routine when you call it. It can of course be done (for example, many enumeration functions in Windows work this way), but it gets pretty clunky.

When we call std::partition

, we have already selected the rotation value. We want to ... bind this value to one of the parameters that will be passed to the comparison function. One really ugly way to do this is to "pass" it through a global variable:

int pivot;

bool pred(int x) { return x < pivot; }

void quick_sort(int *begin, int *end) { 
    if (end - begin < 2)
        return;

    pivot = choose_pivot(begin, end);

    int *pos = std::partition(begin, end, pred);
    quick_sort(begin, pos);
    quick_sort(pos, end);
}

      

        
        
        
      

    

I really hope I don't need to point out that we'd rather not use the global for this if we can help it. One fairly simple way to avoid this is to create a function object. We pass in the current rotation value when creating the object and store this value as a state in the object:

class pred { 
    int pivot;
public:
    pred(int pivot) : pivot(pivot) {}

    bool operator()(int x) { return x < pivot; }
};

void quick_sort(int *begin, int *end) { 
    if (end-begin < 2)
        return;

    int pivot = choose_pivot(begin, end);

    int *pos = std::partition(begin, end, pred(pivot));        
    quick_sort(begin, pos);
    quick_sort(pos, end);
}

      

        
        
        
      

    

This added a tiny bit of extra code, but instead we removed the global - pretty reasonable exchange.

Of course, with C ++ 11 we can do a little better - the language has added "lambda expressions" that can create a class very similar to us. Using this code, our code looks something like this:

void quick_sort(int *begin, int *end) { 
    if (end-begin < 2)
        return;

    int pivot = find_pivot(begin, end);

    auto pos = std::partition(begin, end, [pivot](int x) { return x < pivot; });
    quick_sort(begin, pos);
    quick_sort(pos, end);
}

      

        
        
        
      

    

This changes the syntax we use to specify a class / create a function object, but it still presents the same basic idea as the previous code: the compiler generates a class with a constructor and operator()

. The values ​​we enclose in square brackets are passed to the constructor and (int x) { return x < pivot; }

basically becomes the body operator()

for this class ² .

This makes the code much easier to write and much easier to read, but it does not change the basic fact that we are creating an object by "capturing" some state in the constructor and using the overloaded operator()

for comparison.

Of course, the comparison just happens for exactly what we need for things like sorting. This is a common use of lambda expressions and function objects in general, but we are certainly not limited to that. Just for another example, let's consider "normalizing" a collection of doubles. We want to find the largest one, and then we split each value in the collection so that each element is in the range 0.0 to 1.0, but all keep the same relationship to each other, as before:

double largest = * std::max_element(begin, end);
std::for_each(begin, end, [largest](double d) { return d/largest; });

      

        
        
        
      

    

Here again we have roughly the same pattern: we create a function object that stores some kind of relevant state, and then we reuse that function object operator()

to do the real work.

• We could split into less or equal and more than instead. Or we could create three groups: less than, more, more. The latter can improve efficiency when there are many duplicates, but for the moment we really don't care.
• There's a lot more to learn about lambda expressions than just that - I'm oversimplifying some things and completely ignoring others that we don't care about right now.