C++ functor - unexpected behaviour?

Question

I have written this program, which sorts some ints using a functor:

#include<iostream>
#include<list>
#include<set>

using namespace std;

struct IntSorter
{
    unsigned int comparisons;
    IntSorter()
    {
        std::cout << "new intsorter" << std::endl;
        comparisons = 0;
    }

    bool operator() (const int &a, const int &b)
    {
        std::cout << "c is " << comparisons << std::endl;
        ++comparisons;
        std::cout << "c is now " << comparisons << std::endl;
        return a<b;
    }
};

int main(int argc, char *argv[])
{    
    list<int> my_list;
    my_list.push_back(4);
    my_list.push_back(3);
    my_list.push_back(5);
    my_list.push_back(1);

    IntSorter s;
    my_list.sort(s);

    for (list<int>::iterator it=my_list.begin(); it!=my_list.end(); it++)
    {
        std::cout << *it << std::endl;
    }

    return 0;

}

The sorting works fine, but the part counting the number of comparisons gives a result I didn't expect:

./prog -a -b -c -d
new intsorter
c is 0
c is now 1
c is 0
c is now 1
c is 0
c is now 1
c is 1
c is now 2
c is 2
c is now 3
1
3
4
5

I was thinking the structure would be reused, counting and storing the number of comparisons. However, it appears to copy it, or some other behaviour as the numbers printed out go 1,1,1,2,3, instead of 1,2,3,4,5. What am I doing wrong?

Answer 1

You're not really doing anything wrong. The problem lies entirely in your expectation -- the sorter is passed by value, so there's a bare minimum of one copy made as you pass it. The sort function is free to make more copies as well (e.g. a recursive sort will probably pass a copy to each recursive invocation).

There's a simple lesson here: any such object should be cheap to create and/or copy.

Answer 2

You're on the right track. std::list::sort takes the function object by value. As it does its work, it passes a copy of your function object around which means that the comparisons member data is getting copied, too.

You're not doing anything wrong, it's just that you can't use a functor like this.

The easiest way to make std::list::sort do what you want is to embed a reference to an external counter object in your functor. On each comparison, forward a call to that counter object. After std::list::sort returns, you'll have the total in there.

Answer 3

As mention it is passed by value: A simple solution is:

struct IntSorter
{
    unsigned int& comparisons;
    IntSorter(unsigned int& c)
        :comparisons(c)
    {}
    // Other Stuff
};

// In main:
unsigned int  count = 0;
my_list.sort(IntSorter(count));