The SFTL algorithms take an STL container and a functor as arguments, but what exactly is a functor ?

From the SFTL point of view, a functor is : something that can be called, that can be given some data as parameter, that may process that data, and that finally returns some other data.

So it's basically something “callable” that does something with something and returns some other thing. Clear enough ?

These callable things are summarized as “functors” and, although their definition may seem rather abstract, they're made of familiar things :

• standard C-style functions
• C++ class methods
• functions objects

Most functors take and return data, but three “family types” of functors exist :

• the predicates : is the name given to functors that evaluate their argument against a certain test and return a boolean value. Predicates are the functor types to use with the filter algorithm.
• the closures : is the name given to functors that apply some kind of processing to the input data and don't return anything. Closures are the functor types to use with the apply algorithm.
• the transformers : is the name given to functors that take some data as input and return some other data as output, the output usually depending solely on the input. Transformers are the functor type to use with the map and reduce algorithms.

An example of predicate would be a function that tests whether a number is prime. All the function does is perform the evalutation and return the result. The given argument isn't modified in any way.

An example of closure would be a void function that takes a number and prints it to the screen. All the function does is perform the operation and return to the caller. Closures can also be made to modify the input argument (altough it breaks the functional spirit). An example would be a function that switches a flag in an object if certain conditions are met.

An example of transformer would be a function that returns the square root of a number.

How the functors are used and what will be returned by algorithms depends on the algorithms themselves.

For instance, the intent of the map algorithm is to transform data. What map does is call the functor for each element of the input container and store each functor return value in a local container. Finally, map returns a copy of that local container, thus returning all the functor results.

In the case of filter, the functor is only used to obtain a boolean value. filter calls the functor for each element of the input container and, if the functor returned true, stores the element in a local container. filter finally returns the list of elements that satisfied the functor test (in this case the functor is called a predicate).

Generally speaking, the functor is called for each element in the container and the result of the functor call may impact the execution of the algorithm as well as the algorithm return value.

Here we'll be be talking about how functors are created in practice.

There are three ways to implement functors that can be used by the SFTL : as a function, as a class method and as a function object.

Are functors implemented as a function.

The function must accept a single argument, either an object or a native data type, that is passed by value, by reference or through a pointer.

That means that the following signatures are possible :

U my_functor( T data );
U my_functor( T* data );
U my_functor( T& data );
U* my_functor( T data );
U* my_functor( T* data );
U* my_functor( T& data );

To use your functor with an algorithm, just give its name as parameter (there's no need to add an & in front since function names are implicitly pointers).

Here is an example of function functors in action :

// source: examples/function_functors.cpp
 
#include <iostream>
#include <vector>
#include "sftl.h"
 
using namespace std;
 
// a predicate functor
bool isEven( int x ) {
    return (x%2)==0;
}
 
// a transformer functor
double* inverse( int& x ) {
    return new double(1.0/x);
} 
 
// a closure functor
void printDouble( double *item ) {
    std::cout << *item << std::endl;
}
 
int main() {
    // container definition
    int array [] = {1,2,3,4,5,6,7,8,9};
    vector<int> numbers( &array[0], &array[9] );
 
    // filtering the numbers with the isEven predicate
    vector<int> evens = filter( numbers, isEven );
 
    // getting the inverses with the inverse transformer 
    vector<double*> inverses = map( evens, inverse );
 
    // print them with the printDouble closure 
    apply( inverses, printDouble );
}

Of course, the three last lines could be reduced to :

  apply( map( filter( numbers, isEven ), inverse ), printDouble );

(Yes, there's a memory leak in this program )

Are functors implemented as class methods.

Any instance class method without arguments can be a functor.

When an algorithm is run over a container of objects of class T using the method T::m() as the functor, the m() method will be called on every object from the container.

This means that, given a container of objects of class T, only methods from the T class can be used as functors.

There's no way, in the current state of the library, to invoke a method from another class as functor (for instance, a static class method in a class U that would take an object of type T as parameter).

To pass the functor to the algorithm, use &T::m where

• T is the object class
• m is the method name in T

Here is an example source code with a Flight class where the methods getDestination(), isCancelled() and cancel() are used as functors.

// source : examples/class_method_functors.cpp
 
#include <string>
#include <iostream>
#include <vector>
#include "sftl.h"
 
using namespace std;
 
class Flight {
    string number;
    string destination;
    bool cancelled;
public:
    Flight( string number, string destination, bool cancelled ) 
    	: number(number), destination(destination), cancelled(cancelled) {};
 
    string getNumber() {
    	return number;
    }
 
    string getDestination() {
        return destination;
    }
 
    bool isCancelled() {
        return cancelled;
    }
 
    void cancel() {
    	cancelled = true;
    }
};
 
int main() {
	vector< Flight* > flights;
	flights.push_back( new Flight("A101","Paris",false) );
	flights.push_back( new Flight("B201","New York",true) );
	flights.push_back( new Flight("C301","London",false) );	
 
	// get the destination names
	vector<string> destinations = map( flights, &Flight::getDestination );
 
	// get the list of cancelled flights
	vector<Flight*> cancelled_flights = filter( flights, &Flight::isCancelled );
 
	// cancel all flights
	apply( flights, &Flight::cancel );
 
	cout << "number of cancelled flights : " << filter(flights,&Flight::isCancelled).size() << endl;
}

Are functors implemented as a function object.

Function objects are objects that define the operator ().

The advantage of function objects is double :

• the operator () allows objects to behave somehow like functions (they can be called simply using <object_name>() )
• they are smarter than functions since, being objects, they can have state

Here is an example of function object that has state :

struct Formula {
    double a, b, c;
    Formula ( double a, double b, double c ) : a(a), b(b), c(c) {}
    double operator () ( double x ) {
        return a*x*x + b*x + c;
    }
};

This function object bears in itself the constants (a,b,c) to compute the formula f(x) = a . x^2 + b . x + c

The function object can be used this way :

Formula f1(1,3,2); // instantiate a formula f1 with a=1,b=3,c=2
cout << f1(100) << "," << f1(150) << endl; // evaluates f1 with x=100 and x=150
Formula f2(-1,0,0.5); // instantiate a formula f2 with a=-1,b=0,c=0.5
cout << f2(10) << "," << f2(30) << endl; // evaluates f2 with x=10 and x=30

To use a function object f with an SFTL algorithm, pass the instance of f as is.

This example re-uses the Formula function object illustrated above.

// source : examples/function_objects_functors.cpp
...
int main() {
    vector<double> numbers;
    for (int i=1;i<=9;i++)
        numbers.push_back( i );		
 
    Formula f1(1,3,2);  // instantiate Formula with a=1, b=3, c=2
 
    // collect results of f1 applied to numbers
    vector<double> results_1 = map<double>( numbers, f1 );
 
    // collect results of inline formula applied to numbers
    vector<double> results_2 = map<double>( numbers, Formula(-1,0,0.5) );
}

Function object functors are special beasts in regard of the SFTL because they're not all created equal.

Notice the <double> template instantiation right after map : it defines the type of objects to be stored in the container returned by map. It has to be explicitly specified because the Formula function object doesn't provide type information and that it can't be automatically deduced by the template system.

But the situation improves when using function objects conforming to the STL standard.

The STL defines a template structure for function objects named unary_function (found in header <functional>) that allows function objects to embed type information.

Here, we've defined a new STL_Formula function object that inherits the unary_function struct :

struct STL_Formula : public unary_function<double,double> {
    double a, b, c;
    STL_Formula ( double a, double b, double c ) : a(a), b(b), c(c) {}
    double operator () ( double x ) {
        return a*x*x + b*x + c;
    }
};

The only difference with the former Formula is that it inherits from unary_function and that two templates parameters have been given. They define the types of the operator () : the first is the argument type and the second is the return type (here both are double).

Now, with such a function object, there's no need to provide type information anymore to the SFTL and one can simply type :

STL_Formula f3(0.1,-2,4);
vector<double> results_3 = map( numbers, f3 );