Jul 20

What is a C++ Functor?

Category: C++, Programming

I did a presentation on the spirit library in the flesh recently and was surprised to find the big sticking point was C++ functors. So I thought I’d cover the concept here.


The Concept

Functors provide a generic callback mechanism al la C function pointers. In C you typically see the following (see this):

void sort(void *data, 
             size_t element_size, 
             size_t element_count, 
             int (*comp)(const void *, const void *) ){
    ...
    //equivalent to int diff = (*comp)(a,b)
    int diff = comp(a, b);
    ...
}

where a comparator is passed as a function pointer to the sort.

In C++ you can do the same thing with greater flexibility by using a template:

template<class IteratorT, class FunctorT>
void sort(IteratorT start, IteratorT end, FunctorT func){
    ....
    int diff = func(*a, *b);
    ....
}

where IteratorT could be a pointer or an iterator object and FunctorT can be anything that supports the value = func(..arglist...) syntax. This actually covers a lot thanks to C++’s ability to override operators. For instance:

//override the () operator
struct comparator_functor_type{
    int operator()(int a, int b){
        return a - b;
    }
}
 
comparator_functor_type functor_declaration;
 
//this calls the () operator of comparator_functor_type
int diff = functor_declaration(3, 5);

Why Functors


Convenience

The primary programming advantage to functors is that a functor struct can be used to wrap any sort of generic context along with the callback. In the case of objects, functors can be used to wrap an object pointer and method function pointer as a single callback:

class my_class{
public:
    ....
    int compare(int a, int b);
    ....
private:
    ....
};
 
struct my_functor_type{
public:
    my_functor_type(my_class &obj):obj_ref(obj){}
 
    int operator()(int a, in b){
        return obj.compare(a, b);
    }
private:
    my_class &obj_ref;
};

Efficiency

In addition to the semantic benefits, functors can be heavily optimized by the compiler. With C function pointers, the C compiler cannot inline the callback code into the function using it becuase the compiler does not know at compile time what function pointers will be used.

With C++ functors and templated functions however, the compiler re-compiles the function (potentially) for each different combination of iterator and functor types used. This means that the compiler can inline and optimize the algorithm code as well as the functor callback at compile time.

Common Uses in C++


STL

Functors are used extensively in C++ although it is possible to use C++ without ever writing one yourself. The biggest user is, unsurprisingly, the Standard Template Library. The algorithm portion of the STL is almost completely made up of standard operations such as for_each, find, remove_if, and so on that take some variety of start and end iterator as well as a functor:

struct remove_condition_functor_type{
public:
    remove_condition_functor_type(Database &d_in):d(d_in){}
 
    bool operator(int value){
       return !d.find_in_table(value);
    }
private:
    Database &d;
};
 
vector<int> values;
 
remove_if(values.begin(), values.end(), 
              remove_condition_functor_type(some_database));

Boost

The boost library also uses them all over the place. In particular the bind library provides a mechanism for taking existing functors and transforming them by binding individual parameters to particular values:

int compare_widgets(widget_db &db, bool ignore_cromulence,
    const widget &a, const widget &b);
 
vector<widget> widget_collection;
 
//sort expects int functor(const widget &a, const widget &b)
//so use compare_widgets but bind argument 1 to global_db,
//argument 2 to true, argument 3 to the first argument
//of the bound functor, and argument 4 to the second
//argument of the bound functor.
sort(widget_collection.begin(), widget_collection.end(),
    bind(&compare_widgets, global_db, true, _1, _2));

The function library provides a set of standard functor objects that look a lot like C# delegates (described later in this article).

int func_comparator(const widget &a, const widget &b);
struct struct_comparator{
    int operator()(const widget &a, const widget &b);
};
 
//function reference
function f1<int (const widget &, const widget &)>(func_comparator);
 
//functor
struct_comparator instance;
function f2<int (const widget &, const widget &)>(instance);
 
//bound functor
function f3<int (const widget &, const widget &)>(
    bind(instance, _2, _1));
 
f1(a,b);
f2(a,b);
f3(a,b);

Anonymous Namespaces

Functor definitions can really clutter up your library and it is easy to define two structs called, say, incremental_generator or compare. For functions you have the static keyword that defines a function as being local to that file:

static int compare(void *a, void *b);

It turns out that C++ has something similar to that for structs, objects, functions, etc. which is the anonymous namespace:

namespace{
    struct compare{
        int operator(int a, int b){...}
    };
}

When defined in a source file this has the same effect as:

namespace __UNIQUE_NAME1234___{
    struct compare{
        int operator(int a, int b){...}
    };
}
using namespace UNIQUE_NAME1234;

How This is Done in Other Languages

So although functors are a nice tool in C++, there are less long winded ways of getting the same functionality in other programming languages.

Java makes the same sort of thing somewhat less tedious by permitting anonymous class definitions:

//Rather than having to define this in a separate file
//for each trivial comparator I'd like to implement
class MyComparator implements Comparator<MyType>{
    int compare(MyType a, MyType b){
        ...
    }
};
 
//I can define it inline at the location it is used.
Set<MyType> sorted = new TreeSet<MyType>(new Comparator<MyType>(){
    int compare(MyType a, MyType b){
        ...
    }
});

This still requires implementing an interface, however. Another option is to treat all functions/methods as first class objects. C# takes this approach via a feature called delegates:

public class Class1 {
    public void doSomething(String s) { ... }
}
public class DemonstrateDelegate
{
    public delegate void delegateType(String s);
 
    public static void Main(string[] args) 
    {
        Class1 obj = new Class1();
        delegateType del= new delegateType(obj.doSomething)
 
        //equivalent to obj.doSomething("someString");
        del("someString");
    }
}

Finally, there are closures in languages like Ruby where a block of code can be encapsulated for later use. This is a lot like java anonymous classes, but it looks better and you don’t have to implement an interface:

class my_collection_type{
    def foreach
        yield(1)
        yield(2)
        yield(3)
    end
end
 
c  = my_collection_type.new()
c.foreach(){ |X| //this is the value from the collection
    //this code is executed in this stack
    //context with 1, 2, and 3 for X
}

The Author

Michael Smit is a software engineer in Seattle, Washington who works for amazon

1 comment

1 Comment so far

  1. [...] test macro is to implement it as a functor. If you do now know what a functor is please refer to this [...]