Tiny Template Library: implementing functor template

• Download source files - 34.3 Kb

Introduction

This project requires at least MSVC v7.1 or GCC v3.2.3 compilers. Please don't even try to compile it with broken compilers like MSVC v6.0 The source contains a sample.

Typically in generic programming, function pointers are passed around as so called functors. A functor is a class that defines the '()' operator. For example

struct compare
{
    template< typename T1, typename T2 > 
    bool operator()( const T1& v1, const T2& v2 ) 
    { 
        return v1 > v2; 
    } 
};

is a functor type that can be used to compare two values.

int n1 = 1, n2 = 2; 
double d1 = 1.1, d2 = 2.; 

compare c; 
if( c(n1, n2) ) {...}
if( c(d1, d2) ) {...}

STL defines several functor classes (pointer_to_unary_function, pointer_to_binary_function, etc.) that can be used in STL algorithms such as for_each.

In a typical application, callbacks are defined as typedefs. For instance:

typedef void (*my_callback_type)( int event_code );
void register_callback( my_callback_type cb );

void my_callback( int event_code );

main()
{
    register_callback(my_callback);
}

This works just fine. Now assume that we have a functor with the same signature.

struct my_callback_functor
{
    void operator()( int event_code );
};

my_callback_functor cb; 
cb( 2 );  

The question is how can we pass the functor to register_callback? We cannot...

We can solve this problem by overloading register_callback().
void register_callback( const my_callback_functor& cb );
This has to be done for each possible functor type. Would not it be nice if there was a generic way for passing functors and function poiners around using only the function signature. Our objective is to implement a template that can be used generically as demonstrated in the following example.

typedef function<VOID (int)> callback;  //define callback's signature
void register_callback( callback cb );

//callback functor
struct my_callback_functor
{
    void operator()( int event_code );
};
//plain callback function
void my_callback( int event_code );

main()
{
    register_callback(my_callback);
    register_callback(my_callback_functor);
}

So we want to implement the function<> template. Such function can also be used for wrapping functions up to be passed to STL algorithm as unary_function or binary_function objects. We focus our discussion on implementing function that support functions with maximum 2 parameters (the maximum arity is 2). The attached source code supports arities up to 10! It is very easy to extended it.

function< void () > //no parameters, no return values
function< void (int) > //1 int parameter, no return values
function< void (int, char) > //2 parameters, no return values
function< int (int, char) > //2 parameters and return values
...

Implementation

It is obvious that function should itself behave like a functor. For the maximum arity 2 and a return type, we define the function template as following:

template< typename R, typename T1, typename T2 >
struct function;

So how do we figure out what the actual function signature is. The answer is partial specialization!

struct empty {}; //some empty type

template< typename R=empty, typename T1=empty, typename T2=empty > 
struct function;

//now specialize
template< typename R, typename T1, typename T2 > 
struct function< R (), T1, T2 > //no parameters
{
    typedef R result_type;

    R operator()();
};

template< typename R, typename T1, typename T2 > 
struct function< R (T1), T2 > //1 parameter
{
    typedef T1 argument_type;
    typedef R result_type;

    R operator()(T1 p1);
};

template< typename R, typename T1, typename T2 > 
struct function< R (T1, T2) > //2 parameters
{
    typedef T1 first_argument_type;
    typedef T2 second_argument_type;
    typedef R result_type;

    R operator()(T1 p1, T2 p2);
};

Ok, fine. Now how do we actually store a reference to the user functions and functors so they could be called by function<>::operator() latter? First of all, we need to define a template assignment operator that parameterizes user types.

struct function
{
    typedef function this_t;

    template<typename F>
    this_t& operator=( F& f )
    {
        ...
        return *this;
    }
};

In this code, F is the user defined function type. The problem is that this data type is not present in the template parameters list of function, so somehow we need to store the type information that is known only during the assignment for latter use.

To accomplish that we define a set of polymorphic classes, that hold a copy of the user object. We'll need a separate class for each arity.

//0-arity
template<typename R>
struct functor_caller_base0
{
    typedef functor_caller_base0 this_t;
    typedef R return_type;
    virtual ~functor_caller_base0() {}
    virtual return_type operator()() = 0;
    virtual this_t* clone() const = 0;
};

//1-arity
template< typename R, typename T1 >
struct functor_caller_base1
{
    typedef functor_caller_base1 this_t
    typedef R return_type;
    virtual ~functor_caller_base1() {}
    virtual return_type operator()( T1 p1 ) = 0;
    virtual this_t* clone() const = 0;
};

//2-arity
template< typename R, typename T1, typename T2 >
struct functor_caller_base2 
{
    typedef functor_caller_base2 this_t
    typedef R return_type;
    virtual ~functor_caller_base2() {}
    virtual return_type operator()( T1 p1, T2 p2 ) = 0;
    virtual this_t* clone() const = 0;
};

Now from these bases, we can derive the actual holder of the user functor and function pointers while adding a tempate parameter for the user type.

template< typename F, typename R >
struct functor_caller0 : functor_caller_base0<R>
{
    typedef functor_caller0 this_t;
    typedef R return_type;
    F f_;
    functor_caller0( F f ) : f_(f) {}
    //make the final call to the user function
    virtual return_type operator()() { return f_(); }
    //clone myself
    virtual base_t* clone() const { return new this_t(f_); } 
};

template< typename F=empty, typename R=empty, 
    typename T1 = empty > struct functor_caller1;
template< typename F, typename R, typename T1 >
struct functor_caller1< F, R (T1) > : functor_caller_base1< R, T1 >
{
    typedef functor_caller1 this_t;
    typedef R return_type;
    F f_;
    functor_caller1( F f ) : f_(f) {}
    //make the final call to the user function
    virtual return_type operator()( T1 p1 ) { return f_(p1); }
    virtual base_t* clone() const { return new this_t(f_); }
};

//extrapolate to the arity 2
... (see the source code)

Using this set we can finally implement the function class. The function class creates the function_caller objects and stores a pointer to function_caller_base. In the operator(), it calls the virtual operator () that is defined by function_caller_base.

//definition
template< typename R, typename T1, typename T2 >
struct function;

//0-arity specialization
template<  typename R, typename T1, typename T2 >
struct function
{
    typedef function this_t;
    typedef functor_caller_base0<R> caller;
    typedef R result_type; 
    enum { arity = 0 };
    
    function() : fc_(0) {}
    virtual ~function() { destroy(); }
    
    template< typename F >
    function( F f ) : fc_(0)
    {
        typedef functor_caller0<F,R> caller_spec;
        fc_ = new caller_spec(f);
    }
    function( const this_t& r ) : fc_(0)
    {
        operator=(r);
    }
    
    result_type operator()() 
    { 
        return (*fc_)(); 
    }
    

protected:
    caller *fc_;
    void destroy()
    {
        if(!fc_) return;
        delete fc_;
        fc_ = 0;
    }
};

//1-arity specialization
template<  typename R, typename T1, typename T2 >
struct function<R (T1), T2 >
{
    typedef function this_t;
    typedef functor_caller_base1<R, T1> caller;
    typedef R result_type;
    typedef T1 argument_type;
    enum { arity = 1 };
    function() : fc_(0) {}
    virtual ~function() { destroy(); }
    template< typename F >
    function( F f ) : fc_(0)
    {
        typedef functor_caller1<F,R (T1)> caller_spec;
        fc_ = new caller_spec(f);
    }
    function( const this_t& r ) : fc_(0)
    {
        operator=(r);
    }
    this_t& operator=( const this_t& r )
    {
        if( this == &r ) return *this;
        destroy();
        fc_ = r.fc_->clone();
        return *this;
    }
    result_type operator()(T1 p1)
    {
        return (*fc_)(p1);
    }
protected:
    caller *fc_;
    void destroy()
    {
        if(!fc_) return;
        delete fc_;
        fc_ = 0;
    }
};

//2-arity specializtion
template<  typename R, typename T1, typename T2 >
struct function<R (T1, T2) >
{
    ... for a full implementation, see the source 
};

When function::operator()() is invoked, it calls virtual operator() of the functor_caller_base that actually calls the derived class that has the information about the user functor type and its copy. The derived functor_caller is making the final call to the user functor.

Finally, it is interesting to note that in C++, it is legal to return void. The above code works for functions/functors with no return values only because the following code is legal.

void foobar1();

void foobar2()
{
   return foobar1();
}

A complete implementation that support function arities up to 10, could be found in the Tiny Template Libarary

TTL contains a number of other useful templates (see the docs).

Using the code

The whole library resides in header files only. There is nothing to be built or installed, just copy the TTL files into one of you folders and and make sure that this folder is in the list of include folders in your compiler. You can then include TTL headers as in the following example.

#include "ttl/func/function.hpp" 

The source contains a simple sample in the samples/test folder. The code has been tested with MSVC v7.1 and GCC v3.2.3

Conclusion

The key points of this article are:

• Using partial specialization for defining function signatures.
• Using polymorphic types for capturing and storing information about user types.

It is fascinating what could be done with templates and partial specializations in C++. Finally when the most commonly used compilers are complaint, this truly opens a whole new world in practical C++ programming.