Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C++
Article

STL Function objects

Rate me:
Please Sign up or sign in to vote.
4.85/5 (11 votes)
24 Sep 20013 min read 158.3K   769   27   23
Using STL function objects in std::sort

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Software Developer
United States United States
Chris Losinger was the president of Smaller Animals Software, Inc. (which no longer exists).

Comments and Discussions

 
GeneralLet stl for work Pin
liaohaiwen27-Sep-08 4:15
liaohaiwen27-Sep-08 4:15 
GeneralRe: Let stl for work Pin
Chris Losinger27-Sep-08 4:19
professionalChris Losinger27-Sep-08 4:19 
Generalslooooooooow std::sort in Debug builds Pin
Bartosz Bien5-Dec-06 8:43
Bartosz Bien5-Dec-06 8:43 
GeneralPerfect! Exactly what I needed Pin
Paul Katz30-Dec-05 8:33
Paul Katz30-Dec-05 8:33 
GeneralSTL function Pin
Anonymous9-Apr-05 15:01
Anonymous9-Apr-05 15:01 
GeneralYou save my day, Thank you! Pin
dido2k13-Mar-05 10:58
dido2k13-Mar-05 10:58 
GeneralSort the employee list Pin
wilson woon19-Jun-04 17:40
wilson woon19-Jun-04 17:40 
GeneralRe: Sort the employee list Pin
Bob Ciora7-Nov-05 9:50
Bob Ciora7-Nov-05 9:50 
Generalsorting pointers on a list Pin
yenrab26-Feb-03 9:36
yenrab26-Feb-03 9:36 
GeneralRe: sorting pointers on a list Pin
Chris Losinger26-Feb-03 9:39
professionalChris Losinger26-Feb-03 9:39 
GeneralRe: sorting pointers on a list Pin
yenrab26-Feb-03 9:43
yenrab26-Feb-03 9:43 
GeneralRe: sorting pointers on a list Pin
Chris Losinger26-Feb-03 9:49
professionalChris Losinger26-Feb-03 9:49 
GeneralRe: sorting pointers on a list Pin
yenrab26-Feb-03 9:51
yenrab26-Feb-03 9:51 
GeneralWhere is the function Pin
Anonymous13-Feb-03 17:14
Anonymous13-Feb-03 17:14 
GeneralRe: Where is the function Pin
Chris Losinger13-Feb-03 17:22
professionalChris Losinger13-Feb-03 17:22 
GeneralAnother solution Pin
Gabriel Hanotaux27-May-02 0:53
Gabriel Hanotaux27-May-02 0:53 
Generalsample project Pin
5-Oct-01 4:24
suss5-Oct-01 4:24 
GeneralRe: sample project Pin
Chris Losinger5-Oct-01 4:38
professionalChris Losinger5-Oct-01 4:38 
GeneralRe: sample project Pin
Chris Maunder5-Oct-01 13:09
cofounderChris Maunder5-Oct-01 13:09 
GeneralNot a function adaptor Pin
William E. Kempf25-Sep-01 11:38
William E. Kempf25-Sep-01 11:38 
Generaloops Pin
Chris Losinger25-Sep-01 11:44
professionalChris Losinger25-Sep-01 11:44 
GeneralRe: oops Pin
William E. Kempf25-Sep-01 12:20
William E. Kempf25-Sep-01 12:20 
GeneralNice... Pin
Nemanja Trifunovic25-Sep-01 6:43
Nemanja Trifunovic25-Sep-01 6:43 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.