C++11 sort using function objects

If you’re working on some C++ code and you need to sort the elements in a container which provides random access, like a std::vector, the simplest and quickest option is using the function std::sort from the <algorithm> functions.

In this post I’m showing an example of how to use std::sort with std::function objects in C++11 code.

Basic sorting

The function std::sort requires 2 parameters which are 2 random access iterators pointing to the initial and final positions of the sequence in your container which will be sorted. All the elements in such sequence will be sorted, but the final one.

An example code of a simple sort is the following:

#include <algorithm>
#include <vector>

const int array[] = { 10, 20, 5, 15, 0 };
std::vector<int> vec(array, array + 5);

std::sort(vec.begin(), vec.end());

Printing the elements of the vector after that will give us the ordered sequence as expected:

0 5 10 15 20

More complex sorting

A simple ascending sort on numeric values is fine in some occasions, but sometimes you need something else, like ordering complex objects according to some specific parameter or in descending order.

For such needs std::sort takes a third parameter to pass a Compare object which basically is a binary function which takes 2 elements of your sequence as arguments and returns a value which can be implicitly converted to bool. The value returned is true if the element passed as first argument has to precede the second one (or elem1 < elem2), false otherwise (elem2 < elem1).

A basic example of what I’ve just described is the following:

#include <algorithm>
#include <vector>

bool DescOrderInt(int a, int b);

...

const int array[] = { 10, 20, 5, 15, 0 };
std::vector<int> vec(array, array + 5);

std::sort(vec.begin(), vec.end(), DescOrderInt);

DescOrderInt is implemented as follow, which basically means the elements of the vector will be sorted in descending order:

bool DescOrderInt(int a, int b)
{
    return a > b;
}

Printing the elements of the vector now will show the sequence ordered in descending order as expected:

20 15 10 5 0

C++11 sort using function objects

Many examples on std::sort you’ll find online use a std::binary_function to define the Compare object used to control the order of the elements to sort, but unfortunately std::binary_function has been deprecated in C++11 and will be removed in C++17, so it’s better not to use it when writing new C++ code.

An alternative to a simple function pointer is using a std::function introduced in C++11, which basically is a general-purpose polymorphic function wrapper.

A basic example of that is the following, where sorter is the std::function which stores the operator() defined in StrDescOrderInt:

#include <algorithm>
#include <functional>
#include <vector>

struct StrDescOrderInt
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

...

const int array[] = { 10, 20, 5, 15, 0 };
std::vector<int> vec(array, array + 5);

std::function<bool(int, int)> sorter = StrDescOrderInt();

std::sort(vec.begin(), vec.end(), sorter);

Printing the elements of the vector will show the sequence ordered in descending order as in the previous example:

20 15 10 5 0

A real-life example: providing multiple sorting options

Let’s imagine we have a list of football players and we want to provide users a way to sort them according to their attributes. Let’s say there’s a graphical interface with several buttons to control the order. Each button has an index assigned which corresponds to a different sorting order.

The Player class is something like this:

// -- Player.h --
#include <string>
    
class Player
{   
public:
    Player(const char * name, int caps, int goals);
    
    const std::string & GetName() const;
    
    int GetCaps() const;
    int GetGoals() const; 

private:
    std::string mName;
    
    int mCaps;
    int mGoals;
};  

We can now create a class or struct where we can keep all the Compare functions, which basically are just a struct with an operator() which takes 2 pointers to a Player as parameters and returns a boolean value:

// -- PlayerSorting.h --

class Player;
    
class PlayerSorting
{   
public:
    // -- NAME --
    struct SortPlayerByNameAsc { bool operator()(Player * p1, Player * p2) const; };
    struct SortPlayerByNameDes { bool operator()(Player * p1, Player * p2) const; };
    
    // -- CAPS --
    struct SortPlayerByCapsAsc { bool operator()(Player * p1, Player * p2) const; };
    struct SortPlayerByCapsDes { bool operator()(Player * p1, Player * p2) const; };
    
    // -- GOALS --
    struct SortPlayerByGoalsAsc { bool operator()(Player * p1, Player * p2) const; };
    struct SortPlayerByGoalsDes { bool operator()(Player * p1, Player * p2) const; };
};

Then, somewhere in the client code, we can store all the std::function objects in a std::vector to be able to access them using an index (in this case, the index assigned to the button of our interface).

std::vector< std::function<bool(Player *, Player *)> > sorters;
sorters.push_back(PlayerSorting::SortPlayerByNameAsc());
sorters.push_back(PlayerSorting::SortPlayerByCapsAsc());
sorters.push_back(PlayerSorting::SortPlayerByGoalsAsc());
sorters.push_back(PlayerSorting::SortPlayerByNameDes());
sorters.push_back(PlayerSorting::SortPlayerByCapsDes());
sorters.push_back(PlayerSorting::SortPlayerByGoalsDes());

For example the following code will order the Players by goals in descending order:

std::vector<Player *> players;

// ...init players...

std::sort(players.begin(), players.end(), sorters[5]);

and printing the content of the vector players will produce the following result:

NAME                     CAPS  GOALS 
Lionel Messi             21    20    
David Villa              13    16    
Asamoah Gyan             22    15    
Arjen Robben             11    12    
Mesut Oezil              19    10    
Diego Forlan             20    10    
Andres Iniesta           15    9     
Wesley Sneijder          24    6     
Xavi                     17    5     
Bastian Schweinsteiger   23    4

whereas changing the index of the vector and then the Compare object like below will give us a different order:

std::sort(players.begin(), players.end(), sorters[0]);

in this case we will get the Players sorted in alphabetical order:

NAME                     CAPS  GOALS 
Andres Iniesta           15    9     
Arjen Robben             11    12    
Asamoah Gyan             22    15    
Bastian Schweinsteiger   23    4     
David Villa              13    16    
Diego Forlan             20    10    
Lionel Messi             21    20    
Mesut Oezil              19    10    
Wesley Sneijder          24    6     
Xavi                     17    5

Implementing new ways to sort the table of Players is just a matter of adding new functions to the PlayerSorting class and then storing them into the sorters vector.

Source code

In case you wanted to play with the code I used in this post you can download this zip file which contains all the files and a simple building script for Linux.

You’re free to use the code included as you prefer, but be aware that this is just a quick example I wrote for this post so it’s definitely not something you want to use in any production code or which should be used as example of coding standards. For example I used few magic numbers (numeric values used instead of named constants), which are bad bad bad, but, once again, this is just a quick example I wrote to show a single concept, so keep the good bits and move on.

Leave a Comment

Your email address will not be published. Required fields are marked *