C++ functor advantage - holding the state [duplicate]

Question

I did study the whole idea of functors, unfortunately I can't understand the real advantage of functors over typical functions.

According to some academic scripts, functors can hold state unlike functions. Can anyone elaborate on this one with some simple, easy to understand example ?

I really can't understand why typical, regular function are not able to do the same. I'm really sorry for this kind of novice question.

Answer 1

As a really trivial demonstration, let's consider a Quick sort. We choose a value (usually known as the "pivot") and separate the input collection into those that compare less than the pivot, and those that compare greater than or equal to the pivot¹.

The standard library already has std::partition that can do the partitioning itself--separate a collection into those items that satisfy a specified condition, and those that don't. So, to do our partitioning, we just have to supply a suitable predicate.

In this case, we need a simple comparison something like: return x < pivot;. Passing the pivot value every time becomes difficult though. std::partition just passes a value from the collection and asks: "does this pass your test or not?" There's no way for you to tell std::partition what the current pivot value is, and have it pass that to your routine when it's invoked. That could be done, of course (e.g., many enumeration functions in Windows work this way), but it gets pretty clumsy.

When we invoke std::partition we've already chosen the pivot value. What we want is a way to...bind that value to one of the parameters that will be passed to the comparison function. One really ugly way to do that would be to "pass" it via 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 have to point out that we'd rather not use a global for this if we can help it. One fairly easy way to avoid it is to create a function object. We pass the current pivot value when we create the object, and it stores that value as 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 has added a tiny bit of extra code, but in exchange we've eliminated a global--a fairly reasonable exchange.

Of course, as of C++11 we can do quite a bit better still--the language added "lambda expressions" that can create a class pretty much like that for us. Using this, 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 the class/create the function object, but it's still pretty much the same basic idea as the preceding code: the compiler generates a class with a constructor and an operator(). The values we enclose in the square brackets are passed to the constructor, and the (int x) { return x < pivot; } basically becomes the body of the operator() for that class².

This makes code much easier to write and much easier to read--but it doesn't change the basic fact that we're creating an object, "capturing" some state in the constructor, and using an overloaded operator() for the comparison.

Of course, a comparison just happens to be what we need for things like sorting. It is a common use of lambda expressions and function objects more generally, but we're certainly not restricted to it. Just for another example, let's consider "normalizing" a collection of doubles. We want to find the largest one, then divide every value in the collection by that, so each item is in the range 0.0 to 1.0, but all retaining the same ratios to each other as they previously had:

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

Here again we have pretty much the same pattern: create a function object that stores some relevant state, then repeatedly apply that function object's operator() to do the real work.

---

1. We could separate into less than or equal to, and greater than instead. Or we could create three groups: less than, equal to, greater than. The latter can improve efficiency in the presence of many duplicates, but for the moment we really don't care.
2. There's a lot more to know about lambda expressions than just this--I'm simplifying some things, and completely ignoring others that we don't care about at the moment.