Page 1 of 1

A Guide to Function Objects How to make, use function objects directly and with the STL Rate Topic: ***** 1 Votes

#1 Banfa  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 83
  • View blog
  • Posts: 109
  • Joined: 07-June 10

Posted 03 July 2010 - 06:19 PM

*
POPULAR

Function Objects

A Function Object is also known as a functor, functional, or functionoid, but my preference is functor with emphasis on the last syllable, are objects that can be called like a function. I'll start with how to define them and move on to what they are useful for a bit later and finally talk about the classes available in the STL to assist functor creation and usage.

Prerequisites:

You should already know

Basic C++ syntax and operators
Class Definition
Template Classes


Some Terms aka Glossary

So here are a few terms you will seen bandied around when talking about functors

Unary Function : a functor that takes a single parameter
Binary Function : a functor that takes 2 parameters
Predicate : a functor that returns bool indicating the result true or false of some test


The last one can be combined with either of the first 2 so a binary predicate is a functor that takes 2 parameters and returns bool.

Functor Basics

So creating a functor is really very simple, you simply overload the function call operator, operator() something like this

class HelloWorld
{
public:
    void operator()();
};



Firstly notice the rather strange appearance of () twice at the end of the declaration. The first () is part of the operator name, operator(), the second () is actually defining the parameter list for this operator. So adding the method definition and putting it into a program you might get

#include <iostream>
using namespace std;

class HelloWorld
{
public:
    void operator()();
};

void HelloWorld::operator()()
{
    cout << "Hello World" << endl;
}

int main()
{
    HelloWorld hw;

    hw();
}



And there you have hello world written as a functor.

The first thing to note is that unlike many other operators there is no best practice return or parameter types, they really can be anything you'd like although you will obviously have to choose something that fits with the logic of your program. Also, like the other operators as long as you obey the rules of overloading you can have as many function call operators in a class as you'd like.

So here is the declaration of a more complex functor declared in Enigma1.h

class Enigma1
{
public:
    Enigma1(char key);
    ~Enigma1();

    char operator()(char input);

protected:
    static const int LetterCount = 26;

    static int rota[LetterCount];
    static int reversed[LetterCount];
    static int reflector[LetterCount];
    int rotapos;
};



So this functor demonstrates the obvious advantage that functors have over functions. They can have associated data. In the case of this class both static data and instance data. The class in this case is a implementation the the Enigma machine used by the Germans for encoding messages in WWII, albeit a very simple one with a single rotor. The static data represents the physical machine itself which, obviously, doesn't change from one instance to the next and the instance data represents the key data that the operator punches into the machine. The instance data is set in the constructor since the machine can't operate without it.

This allows us to write a program that looks something like

#include <iostream>
#include <string>

#include "Enigma1.h"

using namespace std;

int main()
{
    string text = "Hook line and sinker";
    string encrypted;
    string decrypted;

    char key = 'j';

    cout << "Initial text  : " << text << endl;

    Enigma1 encrypter(key);
    for(string::iterator iter = text.begin(); iter != text.end(); iter++)
    {
        encrypted.push_back(encrypter(*iter));
    }

    cout << "Encrypted text: " << encrypted << endl;

    Enigma1 decrypter(key);
    for(string::iterator iter = encrypted.begin(); iter != encrypted.end(); iter++)
    {
        decrypted.push_back(decrypter(*iter));
    }

    cout << "Decrypted text: " << decrypted << endl;
}



The class processes all letters into upper case so the output of this is

Initial text  : Hook line and sinker 
Encrypted text: FEHA GSEX DSX NTXQDF 
Decrypted text: HOOK LINE AND SINKER 



So at this point you may well be saying something along the lines of “that's all very well but I can do all that with a simple method call, no need for a functor”. Well of course you would be correct and in fact up to now a method call would probably be better, it is not terribly usual practice to call functors directly like that, to start with it can be a little obfuscating.

Functor Uses

So the primary use of a functor is as the callback of the C++ world. Callback functions are useful and powerful, in C they are accomplished by passing a function pointer and while you can do this in C++ using a functor is more powerful. You can fit more into a functor than a function, data for example or an adaption of something that would not normally be able to be a callback. So a quick re-write of the above code produces

#include <iostream>
#include <string>

#include "Enigma1.h"

using namespace std;

void Operate(const string& input, string& output, Enigma1 machine)
{
    for(string::const_iterator iter = input.begin(); iter != input.end(); iter++)
    {
        output.push_back(machine(*iter));
    }
}

int main()
{
    string text = "Hook line and sinker";
    string encrypted;
    string decrypted;

    char key = 'j';

    cout << "Initial text  : " << text << endl;

    Operate(text, encrypted, Enigma1(key));

    cout << "Encrypted text: " << encrypted << endl;

    Operate(encrypted, decrypted, Enigma1(key));

    cout << "Decrypted text: " << decrypted << endl;
}



In this listing both the loops are replaced with a call to a function that performs the loop and calls back to the Enigma1 class as a functor. This is getting better but could it be better still?

Part of C++ is about generalising code so that it can be reused rather than having to re-write portions of code for specific instances. Also notice, rather than passing a reference to the Enigma functor I have passed it by value. This is on purpose and I hope it will become apparent later why. Right now passing by value lets us call the function with a temporary object, a reference doesn't allow that. A constant reference does but in this case it is not possible to take a constant reference to Emigma1 because operator() is not const and for a callback this might often be the case so not const means no constant reference means using pass by value if you want to allow passing a temporary object.

However suppose I have another encryption functor can what is here be generalised a bit more to handle a different encryption algorithms?

Yes, absolutely, the function Operate needs to be generalised and we have a way of generalising functions in C++, it's called templates. The definition of Operate can be changed to the following template function

template <typename Functor>
void Operate(const string& input, string& output, Functor machine)
{
    for(string::const_iterator iter = input.begin(); iter != input.end(); iter++)
    {
        output.push_back(machine(*iter));
    }
}


In this version of Operate instead of specifically expecting an Enigma1 object we just expect any object that can be called as a functor that accepts a single char as a parameter and a returns a char. If we pass the right sort of object the compiler should sort out the specialisation of Operate.

Using this version of Operate in the previous code listing produces exactly the same output as the previous version, the rest of the code does not need to change.

However having made that change to a generalised solution for encoding/decoding I can now easily implement other encoding techniques. I can declare other functors such as

class Autokey
{
public:
    Autokey(const std::string& ikey, bool iencrypt);
    Autokey(const char* ikey, bool iencrypt);
    ~Autokey();

    char operator()(char input);

private:
    static const int LetterCount = 26;

    std::string key;
    bool encrypt;
    int index;
};



but also because of the way templates work I can declare a simple function such as

char Rot13(char input)
{
    locale loc;
    if (std::isalpha(input, loc))
    {
       input = (std::toupper(input, loc) - 'A' + 13) % 26 + 'A';
    }

    return input;
}



Both of these work in place of the original Enigma1 functor...

#include <iostream>
#include <string>
#include <locale>

#include "Enigma1.h"
#include "Autokey.h"

using namespace std;

template <typename Functor>
void Operate(const string& input, string& output, Functor machine)
{
    for(string::const_iterator iter = input.begin(); iter != input.end(); iter++)
    {
        output.push_back(machine(*iter));
    }
}

char Rot13(char input)
{
    locale loc;
    if (std::isalpha(input, loc))
    {
       input = (std::toupper(input, loc) - 'A' + 13) % 26 + 'A';
    }

    return input;
}

int main()
{
    string text = "Hook line and sinker";
    string encrypted;
    string decrypted;

    char enigma1key = 'j';
    string autokeykey = "dreamincode";

    cout << "Initial text  : " << text << endl;
    cout << "Engima1" << endl;

    Operate(text, encrypted, Enigma1(enigma1key));

    cout << "Encrypted text: " << encrypted << endl;

    Operate(encrypted, decrypted, Enigma1(enigma1key));

    cout << "Decrypted text: " << decrypted << endl;

    encrypted.clear();
    decrypted.clear();
    cout << "Autokey" << endl;

    Operate(text, encrypted, Autokey(autokeykey, true));

    cout << "Encrypted text: " << encrypted << endl;

    Operate(encrypted, decrypted, Autokey(autokeykey, false));

    cout << "Decrypted text: " << decrypted << endl;

    encrypted.clear();
    decrypted.clear();
    cout << "ROT13" << endl;

    Operate(text, encrypted, Rot13);

    cout << "Encrypted text: " << encrypted << endl;

    Operate(encrypted, decrypted, Rot13);

    cout << "Decrypted text: " << decrypted << endl;
}



Produces the output

Initial text  : Hook line and sinker

Engima1

Encrypted text: FEHA GSEX DSX NTXQDF

Decrypted text: HOOK LINE AND SINKER

Autokey

Encrypted text: KFSK XQAG OQH ZWBUPZ

Decrypted text: HOOK LINE AND SINKER

ROT13

Encrypted text: UBBX YVAR NAQ FVAXRE

Decrypted text: HOOK LINE AND SINKER




So we have come full circle from looking for a more powerful, more object orientated call back method for C++ (did I tell you we were doing that) that can be used in a generalised manner back to a generalised method for functors that enables the use of old C style callback functions.

Hmmm but how about if we aren't storing our text in a string how about if it was in some other container? Can we change Operate to be even more generalised and accept any container?

The answer is of course yes, in fact there are several of ways to do this. I could declare the container type as a template parameter

template <typename Container, typename Functor>
void Operate(const Container& input, Container& output, Functor machine)
{
    for(typename Container::const_iterator iter = input.begin(); iter != input.end(); iter++)
    {
        output.push_back(machine(*iter));
    }
}



That's all very well but what if I want to use a plain old array of char (ignoring the fact that this is C++ and you shouldn't be using arrays), that doesn't support begin, end or push_back methods.

The solution here is that we aren't really interested in the container at all, we are interested in accessing its members and member access to a container is through iterators. As it happens pointers, as developed to array members, are also iterators so by using iterators I can increase the generalisation of this function that is it will be usable in more ways with more data types.

So replacing my string objects with input and output iterators and additionally taking making allowance for the output iterator not being the same as a the input iterator Operate becomes

template <typename InputIterator, typename OutputIterator, typename Functor>
void Operate(InputIterator inputStart, InputIterator inputEnd, OutputIterator outputStart, Functor machine)
{
    for(; inputStart != inputEnd; inputStart++, outputStart++)
    {
        *outputStart = machine(*inputStart);
    }
}



This can't just be dropped into the current source some other code changes are required. However just before we make that change take a good long look at the prototype for Operate...

Remind you of anything else?

How about std::transform?

Functors and the STL

So this is really where Functors start working for us. Operate has become std::transform changing the program listing to take advantage of this, and reducing back to just using Enigma1 results in

#include <iostream>
#include <algorithm>
#include <string>

#include "Enigma1.h"

using namespace std;

int main()
{
    string text = "Hook line and sinker";
    string encrypted;
    string decrypted;

    char key = 'j';

    cout << "Initial text  : " << text << endl;

    transform(text.begin(), text.end(), back_inserter(encrypted), Enigma1(key));

    cout << "Encrypted text: " << encrypted << endl;

    transform(encrypted.begin(), encrypted.end(), back_inserter(decrypted), Enigma1(key));

    cout << "Decrypted text: " << decrypted << endl;
}



The output of this listing is unchanged from the first listing. Note the use of std::back_inserter, this is an adaptor which adapts any output iterator which do not create extra space in the container they are used to copy into to an iterator that does create the extra space required for inserting the new data.

This listing also looks, to my eyes at least, very clean compared to the previous listing and it is also the shortest so far (no real surprise there).

This is where functors really come into their own. The algorithm and numeric sections of the STL makes extensive use of functors, in fact many algorithms and all numerics have an overload that accepts a functor as its last parameter; normally a unary or binary function or predicate.

Not only that but the STL provides a large number of template functors ready for immediate use available through the functional header.

Learn to use these and you will make a serious dent in the number of code lines required to work with containers and of course you will be taking advantage of the accumulated wisdom of all the those clever chappies that helped design the STL. It is relatively safe to say that however the STL does a job is likely to be the most efficient way to do it on the given platform so off loading any functionality to can to the STL is a good idea.

So what is in the STL? I am not actually going to go into detail about everything because, to be honest, you can just go and read the documentation yourself. But I will describe what's available by category. I am not giving too many examples here because there are lots of links straight out to reference pages with examples.

So we better start with std::unary_function and std::binary_function. These are not functors at all but rather they define public types for the input arguments and output to be used. Every functor in the STL derives from one of these 2 classes.

Operator Classes

Next there are a whole bunch of operator classes:

std::divides
std::equal_to
std::greater
std::greater_equal
std::less
std::less_equal
std::logical_and
std::logical_not
std::logical_or
std::minus
std::modulus
std::multiples
std::negate
std::not_equal_to
std::plus

These are arithmetic and logical functors that do pretty much what there names suggest they do. With the exception of std::negate which is unary these are all binary functions with the comparison and logical operators being predicates.

Adaptor Functions

Then we get the adaptor functions. These are functions that return a functor, good references include the functors they return. I wont be going into those in detail. One of the advantages of these being template functions is that the compiler can often guess what the template parameters are so you not need to mess your code up with <YourTypeHere> type qualifiers.

The adaptor is a design pattern of course and is a class that modifies the interface of some other class to allow it to be used with code that its original interface is incompatible with and jolly useful they are too. I'll deal with these 7 functions in 4 groups of similar functionality.

Some of these adaptors do expect to be passed functors that derive from std::unary_function or std::binary_function so if you want to use them you will need to do this.

std::bind1st
std::bind2nd

These 2 functions return a functor that adapts a binary function to a unary function. They do this by binding a specific value to one of the parameters of the binary function. As you may guess from the name std::bind1st binds a value to the 1st parameter and std::bind second binds a value to 2nd parameter.

Next there are the rather useful

std::mem_fun
std::mem_fun_ref

These 2 function return a functor that binds a class member function allowing you to use a member function as a callback. Remember all those “how can a use this member of my class as a callback?”, “you can't” threads? With using the STL algorithms you can but you have to be using something that the STL algorithms can operate on. The difference between these functions is the first returns a functor that accepts a pointer to the object to call the member function on and the second returns a functor that accepts a reference to the object to call the member function on.

std::not1
std::not2

These functions return functors that respectively invert the result of a unary predicate and binary predicate.

std::ptr_fun

This function returns a functor that encapsulates a function. The function can have 1 or 2 arguments and depending on the return type the returned functor may or may not be a predicate. You may ask what is the point of this since such a function can be passed straight to the algorithms? Well the answer is simple while it could be passed straight to the algorithms some of the functional adaptor functions, as I said earlier, expect a functor that is derived from std::unary_function or std::binary_function, they make use of the types that these classes define. A straight function is not derived from anything, its a function not a class. This particular function then returns a functor that encapsulates the function pointed to and does derive from either std::unary_function or std::binary_function allowing it to be further used with the other adaptor functions.

Some Examples

Count the number of letters in a string. Many people would write some sort of loop examining each character. However this can all be done by the STL, like this

#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <locale>

using namespace std;

int main()
{
    string input;
    locale loc;

    cout << "Enter data> " << flush;

    getline(cin, input);

    ptrdiff_t count = std::count_if(input.begin(), input.end(), std::bind2nd(std::ptr_fun(std::isalpha<char>),loc));

    cout << "Contains " << count << " letters." << endl;

}



So we count are counting characters that are letters, the std::count_if is most appropriate. It expects a binary predicate.

To test a character to see if it is a letter the std::isalpha from the locale STL is used. This would allow the code to be adapted to differing locales. However not that this function takes 2 parameters, it can not be passed directly to count_if. I need to bind the second parameter, a locale using std::bind2nd. However std::isalpha is a function, it needs to be converted to a function by calling std::ptr_fun first.

Or somewhat more contrived count the total length of all strings in a vector

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <functional>

using namespace std;

int main()
{
    vector<string> text;

    text.push_back(string("dream"));
    text.push_back(string("in"));
    text.push_back(string("code"));

    vector<int> lengths;

    transform(text.begin(), text.end(), back_inserter(lengths), std::mem_fun_ref(&string::length));

    int count = std::accumulate(lengths.begin(), lengths.end(), 0);

    cout << "Vector contains " << count << " characters." << endl;
}



Uses std::mem_fun_ref to allow the string::length member function to be called to transform the vector of strings into a vector of string lengths.

Attached File  CodeFiles.zip (6.13K)
Number of downloads: 195

Is This A Good Question/Topic? 7
  • +

Page 1 of 1