Click here to Skip to main content
Click here to Skip to main content

STL Function objects

, 24 Sep 2001
Rate this:
Please Sign up or sign in to vote.
Using STL function objects in std::sort
<!-- Download Links --> <!-- Add the rest of your HTML here -->

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

About the Author

Chris Losinger
Software Developer
United States United States
Chris Losinger is the president of Smaller Animals Software, Inc..

Comments and Discussions

 
GeneralLet stl for work Pinmemberliaohaiwen27-Sep-08 4:15 
GeneralRe: Let stl for work PinmemberChris Losinger27-Sep-08 4:19 
Generalslooooooooow std::sort in Debug builds PinmemberBartosz Bien5-Dec-06 8:43 
GeneralPerfect! Exactly what I needed PinmemberPaul Katz30-Dec-05 8:33 
GeneralSTL function PinsussAnonymous9-Apr-05 15:01 
GeneralYou save my day, Thank you! Pinmemberdido2k13-Mar-05 10:58 
GeneralSort the employee list Pinmemberwilson woon19-Jun-04 17:40 
GeneralRe: Sort the employee list PinmemberBob Ciora7-Nov-05 9:50 
Generalsorting pointers on a list Pinmemberyenrab26-Feb-03 9:36 
GeneralRe: sorting pointers on a list PinmemberChris Losinger26-Feb-03 9:39 
GeneralRe: sorting pointers on a list Pinmemberyenrab26-Feb-03 9:43 
GeneralRe: sorting pointers on a list PinmemberChris Losinger26-Feb-03 9:49 
GeneralRe: sorting pointers on a list Pinmemberyenrab26-Feb-03 9:51 
GeneralWhere is the function PinsussAnonymous13-Feb-03 17:14 
GeneralRe: Where is the function PinmemberChris Losinger13-Feb-03 17:22 
GeneralAnother solution PinmemberGabriel Hanotaux27-May-02 0:53 
Generalsample project PinmemberWill Rothwell5-Oct-01 4:24 
GeneralRe: sample project PinmemberChris Losinger5-Oct-01 4:38 
GeneralRe: sample project PinmemberChris Maunder5-Oct-01 13:09 
GeneralNot a function adaptor PinmemberWilliam E. Kempf25-Sep-01 11:38 
Generaloops PinmemberChris Losinger25-Sep-01 11:44 
yep, you're right. guess my brain was off this AM.
 
-c
 
------------------------------
Smaller Animals Software, Inc.
http://www.smalleranimals.com
GeneralRe: oops PinmemberWilliam E. Kempf25-Sep-01 12:20 
GeneralNice... PinmemberNemanja Trifunovic25-Sep-01 6:43 

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 25 Sep 2001
Article Copyright 2001 by Chris Losinger
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid