STL Function objects

• Download demo project - 3 Kb

Introduction

This article describes a simple STL function object. A function object is a way to create a function that maintains state. This is especially useful in sorting situations where a simple less-than or greater-than comparison just won't do.

std::sort

Like C's ancient qsort function, the STL std::sort function can accept a comparison function as one of its parameters. This comparison function is called by the sort function when it needs to compare two values from the array. A typical STL comparison function is:

bool compare_myObjects(const CMyObject &a, const CMyObject &b) 
{
    return a.x < b.x;
}

You can use this function to sort a vector (array) of CMyObjects like this:

// declare the vector
vector <CMyObject> myArray;

... initialize the vector
.
.
.
// sort it
std::sort(myArray.begin(), myArray.end(), compare_myObjects);

This works fine in 99% of the situations you're likely to run into.

The other 1%

What if you need to sort the array based on information that isn't in either of the two objects, as might happen if the comparison needs access to some other non-global variable; or what if you want to sort one array based on the contents of another array? You could, of course, do this with global variables, but that's not nice. A function object, of course, can help you do it in a nice OO/C++ manner.

binary_function

A binary_function is a template that, in effect, allows you to define a class that can act as a binary operator - it accepts two inputs of type A and B and returns a single output of type C. It acts as a class, but also as a function, when used in functions such as std::sort. So, you can store things in the class, and use it to perform comparisons (or any binary operation, really) like the compare_myObjects function above.

Sorting one array based on another

For the following example, we have two vectors: one vector is an array of employee objects; the other is an array of integers. The array of integers is an array of indexes into the first array and we'll sort these based on the objects in the employee array. Assume there's some good reason why we can't just sort the employee array itself, like maybe it's been sorted already and we don't want to destroy its current order.

First, an employee:

class employee
{
public:
   int m_salary;
   string m_name;
};

Second, a binary function:

// this is our function object class.
// it holds a reference to a vector of employees.
class employeecomp : public std::binary_function<int,int,bool> 
{
   // the vector reference
   const vector<employee>	&m_employees;

public:
   // constructor which takes a reference to a vector of employees
   employeecomp( const vector<employee> & employees ) : m_employees(employees) {}

   // comparison operator. this will be called by std::sort with two
   // integers. we'll perform a comparison operation on the inputs and
   // return the result of the comparison.
   bool operator()(int a, int b) const
   {
      // a typical comparison operator compares the two input parameters.
      // this one uses the two input parameters as indexes into the m_employees vector.
      return (m_employees.at(a).m_salary) < (m_employees.at(b).m_salary);
   }
};

Using these things:

First, initialize the two vectors:

// index array. this is what we'll sort
vector<int> indexVector;

// employees. this is what the sorting of indexVector is based on
vector<employee> employeeVector;

// initialize indexVector
for (int i=0; i < 4; i++)
{
   indexVector.push_back(i);
}

// initialize some employees
employee h;

h.m_salary = 0;
h.m_name = "fred";
employeeVector.push_back(h);

h.m_salary = 99;
h.m_name = "ethel";
employeeVector.push_back(h);

h.m_salary = 32;
h.m_name = "ricky";
employeeVector.push_back(h);

h.m_salary = 23;
h.m_name = "lucy";
employeeVector.push_back(h);

pre-sort:

// show the index vector before sorting
printf("Before sorting\n");
vector<int>::iterator it;
i = 0;
for (it = indexVector.begin(); it != indexVector.end(); it++)
{
   printf("indexVector[%d] = %d\n", i, (*it));
   i++;
}

Sort! This is where it all comes together. The first two parameters are the start and end of the vector we wish to sort. The third parameter is known as the 'predicate'. In this case, the predicate is an employeecomp object that we're initializing with the employee vector. For every comparison that std::sort needs to do, it will call Pr(x,y), where Pr is the comparison function. In this case the comparison function is the "()" operator of the employeecomp object; x and y are two items from indexVector.

std::sort(indexVector.begin(), 
         indexVector.end(), 
         employeecomp(employeeVector)); // initialize our functor

post-sort:

// show the index vector after sorting
printf("After sorting\n");
i = 0;
for (it = indexVector.begin(); it != indexVector.end(); it++)
{
   printf("indexVector[%d] = %d\n", i, (*it));
   i++;
}

...the results:

Before sorting
indexVector[0] = 0
indexVector[1] = 1
indexVector[2] = 2
indexVector[3] = 3

After sorting
indexVector[0] = 0
indexVector[1] = 3
indexVector[2] = 2
indexVector[3] = 1

As you can see, the indexVector has changed. But what did it change to? The values in indexVector now show the indexes of the items in employeeVector, sorted by increasing salary. And, though I didn't show it here, the employeeVector was not modified at all.

This is a very basic example of what a function operator can do. Still, it's a technique that can be extremely useful in some situations. Because the binary_function template creates a fully functional class, there is no limit to the amount of complexity you can add to it (sort a vector of function objects, for example). Also, this technique isn't limited to std::sort; you can use it in many of the STL algorithms.

Enjoy responsibly.