Functor Tutorial

[Peter_APIIT]

Hello to all, i need a tutorial Functor ?

I really don't understand what is mean by bind1st or bind2nd from C++ standard and the usage of boost bind.

Any suggestion ?

Please help.

Thanks.

[potatoCode]

Hello Peter_APITT

I remember you asking something similar before.
I don't think I did a good job explaining it back then.
I wanna try it again, hopefully better this time.
so this might be long, so please bear with me

let's assume you're in CS101.
the class is taught some basic stuff such as loop, conditional, functions, etc.
The next homework is to write a program to check for palindrome word.

lucky for you, the instructor is so cool that
she doesn't mind the students exploring the whole facets of the C++ language.
And being a devoted CS student as you are,
you waste no time to apply the stuff you taught yourself in the summer vacation,
and quickly whips out the following code
with some fancy stuff other students will learn later in the semester

namespace PWord
{
    bool IsIt(const string& str)
    {
        return str.end() == mismatch(str.begin(), str.end(), str.rbegin()).first;
    }
}

Following all the good practice, you also write a code to test the IsIT function

namespace UTest
{
    void Check(const string str)
    {
        cout << str << " is "
             << (PWord::IsIt(str) ? "INDEED" : "NOT") << " a palindrome\n";
    }

    typedef istream_iterator<string> IterType;
    typedef pair<IterType, IterType> Test;
    Test LoadWordsToTest()
    {
        static istringstream iss("wow radar cow racecar"); // a list of words to test
        return make_pair(IterType(iss), IterType());
    }
}

And you run the test in the main like

int main()
{
    using namespace UTest;
    Test range = LoadWordsToTest();
    for_each(range.first, range.second, Check);

    return 0;
}

Dandy! It works great!
But out of the blue,
the face of that beautiful blondee sitting next to you in class thunder-passes in your mind.
And your hearts pump at the mere thought of her looking at you with the starry eyes
while you explain all the advanced C++ stuff in front of the whole class.

So after some pondering on how to improve the code,
you decided to show some break lines as a parameter option
in the Check() function, which you modified to

void Check(const string str, bool showLineBreak)
{
    cout << str << " is "
         << (PWord::IsIt(str) ? "INDEED" : "NOT") << " a palindrome\n";

    if(showLineBreak)
    cout << string(60, '-') << endl;
}

You then run the test again to make sure it works,
but sweet Moses! the following line inside main() fails to compile

    for_each(range.first, range.second, Check);

But you show no signs of worry,
as you quickly discover that the last argument to for_each
is a unary function/functor whose number of explicit arguments must be exactly one,
but your Check() function takes 2 arguments.

Skipping lunch to do some research, you found out that the problem
might be solved by using some of the functions found in <funtional>,
namely bind1st and bind2nd.

But oh my goodness...
you're confused and you don't know which one goes where to where and how.
Another glimpse of the blond chick flashes right before your eyes.

Good Lord! you can't give up now.
Skipping dinner to do some more studying,
you now have a better idea what bind1st and bind2nd are all about.
So you write on a piece of paper what these functions do, like

1. The function I'm trying to bind have 2 parameters
2. Example of #1 is foo(argumentOne, argumentTwo)
3. bind1st/bind2nd also have 2 parameters
4. Example of #3 is bind1st(something, argumentToBind)
5. I went all day today on empty stomach to find out that
'something' can be replaced with function objects
6. Example of #5 is bind1st(foo, argumentToBind) or
bind2nd(foo, argumentToBind)
7. I can pass 'argumentToBind' as the argument
for either 'argumentOne' or 'argumentTwo' of foo() in line #2,
but I'm not still unsure if this findings is correct.

So after jotting down all these, you decided to try bind1st

    for_each(range.first, range.second, bind1st(Check, true));

which fails, so you try the bind2nd instead

    for_each(range.first, range.second, bind2nd(Check, true));

which also fails.
The thought of her looking at you disappointed flashes...

Staying up all night pondering about the problem and the chick,
something suddenly hits you,
and a veil of confusion slowly drapes up from your mind, self-talking
"oh man! how can I be so stupid?
the first argument to bind1st/bind2nd must be a functor!
but my Check() is just a free function!
now, all I gotta do is turn Check() into a functor!"

With an eye like eagle, you spot the function named ptr_fun in <funtional>
which turns a function into a functor!
Full of anticipiation, you change the code to

    for_each(range.first, range.second, bind1st(ptr_fun(Check), true));

Uh oh! it doesn't compile!
Heck, you're too excited to slow donw now.
So you try the bind2nd version in no time

    for_each(range.first, range.second, bind2nd(ptr_fun(Check), true));

Guess what? it finally works!
And you just can see that blond falling for you!

Now, the final line is added to the list

8. Both bind1st and bind2nd take function object as its first argument.
if I use bind1st,
the second argument of bind1st() is passed to the first parameter of the functor,
if I use bind2nd,
the second argument of bind2nd() is passed to the second paramter of the functor.

So the moral of this long post in C++ terms is this;

IsIt(X) is a unary function
Check(X, Y) is a binary function.

ptr_fun(IsIt(X)) returns a unary functor
ptr_fun(Check(X, Y)) returns a binary functor

bind1st(ptr_fun(Check(X, Y), Z) means Z is passed as an argument to X (Z == X)
where Z and X are of the same type (or implicitly convertible)

bind2nd(ptr_fun(Check(X, Y), Z) means Z is passed as an argument to Y (Z == Y)
where Z and Y are of the same type (or implicitly convertible)

If IsIt() or Check() were member functions,
use appropriate function adaptors such as mem_fun in place of ptr_fun.

wow...that took awhile xD

[Amleto]

nice post

[Peter_APIIT]

Thanks for your explanation. This is the learning process.

This is really awesome.

From what i realize, the check() must be a binary functor and the range.begin() to range.end() passes them as first argument to check() and the True is passes as second argument.

If i switch the order of check() function parameter, then i also need to use bind1st() instead.

My Question:
1. Is the range argument always pass to first or second argument ?
2. Why when check() function has one argument we need not to use function adapter?

 for_each(range.first, range.second, Check);

3. Do you have any reference book exercise on this topic ?
4. I not understand this .

The function object returned by bind1st has its operator() defined such that it takes only one argument. This argument is used to call binary function object op with x as the fixed value for the first argument.

Thanks.

[Amleto]

Thanks for your explanation. This is the learning process.

This is really awesome.

From what i realize, the check() must be a binary functor and the range.begin() to range.end() passes them as first argument to check() and the True is passes as second argument.

If i switch the order of check() function parameter, then i also need to use bind1st() instead.

My Question:
1. Is the range argument always pass to first or second argument ?
2. Why when check() function has one argument we need not to use function adapter?

 for_each(range.first, range.second, Check);

3. Do you have any reference book exercise on this topic ?
4. I not understand this .




Thanks.

2: you need the function adapter for bind1st/bind2nd. The argument in for_each(...) can be a freee function.

4:
bind1st makes an object with operator().
operator() takes one parameter.
You pass two arguments to bind1st - one was the binary function, the other was some 'value'.

The 'value' is saved and shoved into the first parameter of your binary function every time operator() is called on the object that bind1st made. The argument that was passed to operator() is put into the second parameter of your binary function.

[potatoCode]

nice post

Thank you Amleto

Your explanation is concisely well written
nice post as well!

[potatoCode]

2. Why when check() function has one argument we need not to use function adapter?

Ah, that just made me realize what I have been doing wrong.

I have a gut feeling that you're trying to tackle this concept from the inside and out.
That explains why you're having a difficult time unerstanding.

As you have noticed by now,
I haven't really talked about in terms of the implementation but only the interface.
Your question #2 is really the bull's eye because it's asking why STL algorithms implements
functors when passing a plain free function seems to work just as well as any functors.

To answer this question,
we need to clear our grounds on function objects
and why one would choose functors over plain functions.

Let's picture ourselves working with some string data.
We're writing a function to check the length,
more specifically to return the truth value if the string length is less than, say, 5.
The code then might look something like below.

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

namespace Funcky
{
    bool FiveCharsOrLess(const std::string& str)
    {
        return str.size() < 5;
    }

    using namespace std;
}

int main()
{
    using namespace Funcky;

    // some string data
    vector<string> vec;
    vec.push_back("foobar");
    vec.push_back("The Avatar the movie");
    vec.push_back("cow");

    cout << "The number of string that are less than " << 5
         << " character(s) is "
         << count_if(vec.begin(), vec.end(), FiveCharsOrLess);
}

we then, compile and run it and it works great.

Let's also assume that we need to change the size of the length to be compared.
What can we do?
We've already used the hard magic number 5 inside the function.
No biggies, we say, we'll just pass another parameter and use it, like

    bool FiveCharsOrLess(const std::string& str, int lengthToCheck)
    {
        return str.size() < lengthToCheck;
    }

but doing so results in compilation error
because the predicate function in count_if expects a unary function, our function is not.
We get clever and say "okay, i'll just give it a default value"

    bool FiveCharsOrLess(const std::string& str, int lengthToCheck = 99)

Wow, the code compiles, but guess what?
that 99 is still hard coded and is no better than hard coding it inside the function
because we still can't pass the value we want without doing some modification to the function,
nor can we pass the value at the time we use count_if.

So then our forgotten functor comes into the picture.
And we write a whole new class and define our operator() to make it a function object, like

    struct CharsLessThan
    {
        CharsLessThan(std::size_t s) : compareSize(s) {}
        bool operator()(const std::string& str)
        {
            return str.size() < compareSize;
        }
    private:
        std::string::size_type compareSize;
    };

We then try our functor like this

count_if(vec.begin(), vec.end(), CharsLessThan(5));

which works great.
Now, if we wanted to check for strings that are less than, say, 9,
we can pass this arbitrary value 9 without ever re-writing the class

count_if(vec.begin(), vec.end(), CharsLessThan(9));

So, by implementing such flexibility, the STL algorithms can work more effectively.
A more prominent example of such "extensibility" is the iterator concept.

My Question:
1. Is the range argument always pass to first or second argument ?

the range argument is passed as the only argument to the predicate
which expect one argument. so there is no second argument.

3. Do you have any reference book exercise on this topic ?

I do have a reference book.
The C++ Programming Language by Bjarne Stroustrup
But if you're better with the experiment rather than technical words,
I think this book can wait.

Okay. bye

[Andreas Masur]

The following article may help....

• Function Objects (STL)

[Peter_APIIT]

My Question:
1. Is the range argument always pass to first or second argument ?
the range argument is passed as the only argument to the predicate
which expect one argument. so there is no second argument.

Does the predicate is the unary functor created by bind1st() ?

I understand that the bind1st(functor, value), value is bind to first parameter of the functor.

bind1st()
This function constructs an unary function object from the binary function object op by binding its first parameter to the fixed value x.

AFAIK, the bind1st is convert the binary functor to unary functor with the value bind to first parameter of binary functor.

I wonder is the range argument is passes to the unary functor created by bind1st().

Thanks for your help.

[monarch_dodra]

The only thing that is missing from this tutorial is why does the STL insist on using functors rather than functions to begin with???

The answer to that is that functors are usually templates, and if not, they can at least be defined as inlineable (ie, source code is always included), when called by other templates.

Thus, the difference between passing a functor or a function to an stl algorithm is 2-fold:

1 - The functor type passed to the algorithm is known at compile time.
2 - Since this data is known at compile time, it can be inlined, GREATLY increasing speed.

This is especially true with "dumb" functors like "less", "greater" etc. Which are completely optimized away at compile time.

A real world example of this is C's qsort vs C++'s sort. Not only is sort type-safe, but it can inline any function, whereas qsort will always make a function call every iteration, making it much slower.

Thanks to templates and inlining, there are C++ constructs (especially) in algorithm, that will literally anyhilate (generic) C constructs in terms of speed. (under some circumstances, sort is several orders of magnitude faster than qsort).

Why this does not explain how I hope you will at least appreciate the why.

PS: There are other advantages to functors, like typedef-ing, or functor organization (I'm thinking "unary_function" etc.)

PS2: In 99% of the cases, the inline cost is actually free, because the functor is nothing more than a wrapper to "operator<".

PS3: Functors are at worst just as good as functions, and at best, faster.

[Peter_APIIT]

PS: There are other advantages to functors, like typedef-ing, or functor organization (I'm thinking "unary_function" etc.)

PS2: In 99&#37; of the cases, the inline cost is actually free, because the functor is nothing more than a wrapper to "operator<".

What is the advantage of functor organization in the case of a class is derived from unary_function ?

In my opinion, functor not just "is nothing more than a wrapper to "operator<". " but normally it is designed as a predicate for looping construct.

Why you say functor is a wrapper for operator< ?

Please comment.

[Lindley]

std::less is the default functor for most algorithms requiring a binary predicate.

[monarch_dodra]

std::less is the default functor for most algorithms requiring a binary predicate.

Actually I had a question about that, because std::less is actually NOT the default argument.

Almost every algorithm that takes a predicate argument has two signatures:
1 - A signature taking no predicate.
2 - A signature taking a predicate (but that does not default to std::less)

(For example, sort)

The implementation for all algorithms are written twice: Once using operator< (and not less), and the other using pred.

This seems pretty **** (EDIT, What? you can't say the D-word?) redundant to me. Why didn't they just make the algorithms take a predicate that defaults to std::less. If the answer is because a user can overload std::less, then they could have banned that and been done with it.

This confuses me especially since sorted sequence containers (maps etc) DO take predicates that default to std::less.

Is there any explanation for this behavior?

What is the advantage of functor organization in the case of a class is derived from unary_function ?

In my opinion, functor not just "is nothing more than a wrapper to "operator<". " but normally it is designed as a predicate for looping construct.

Why you say functor is a wrapper for operator< ?

Please comment.

The advantage of unary/binary_function is the ability to use the bind functors. Bind requires the typedefs argument_type and the like to work correctly.

When I said "is nothing more than a wrapper to "operator<", I meant that most of the time, they just wrap 1 liners, usually operators.

"normally it is designed as a predicate for looping construct." Yes, I was commenting on the cost of a functor, which is usually free (given inlining), given the size of what it wraps.

For example:

binary_search(itBeg, itEnd)                  (1)
binary_search(itBeg, itEnd, std::less())     (2)

(1) calls a piece of code that was hand written using operator<. (2) calls a piece of different piece of code that does the compare operation using std::less.
Yet once compiled, these two lines will generate the EXACT SAME ASSEMBLY CODE. This is what I was trying to explain

[superbonzo]

Actually I had a question about that, because std::less is actually NOT the default argument.

Almost every algorithm that takes a predicate argument has two signatures:
1 - A signature taking no predicate.
2 - A signature taking a predicate (but that does not default to std::less)

(For example, sort)

The implementation for all algorithms are written twice: Once using operator< (and not less), and the other using pred.

that's because default arguments don't take part in the type deduction process. For example,

template <class T,class V>
void f( T t, V v = 0 );

int main() { f(0); }

won't compile because V is not deduced to be int. In order to use defaults their types must be deducible somewhere else.

[monarch_dodra]

that's because default arguments don't take part in the type deduction process. For example,

template <class T,class V>
void f( T t, V v = 0 );

int main() { f(0); }

won't compile because V is not deduced to be int. In order to use defaults their types must be deducible somewhere else.

I guess that makes sense actually.

But why would the implementors take the time to write the algorithm twice, literally copy pasting them, when they could just:

template <class T>
void f(T t)
{
    f(t, std::less<T>());
}

template <class T, class V>
void f( T t, V v)
{
    ...
}

?