Sorting a vector of pointers to objects using STL and functors

Imagine you have a stl::vector container that contains pointers to objects of some class, and that you'd like to sort them based on the value of some member variable using a STL algorithm. The approach of overloading the < operator of the class wouldn't work in this case. It works only in case the vector contains objects.

What can we do then?

We can solve this problem using functors or function objects.

Quoting the link above:

"Functors are functions with a state. In C++ you can realize them as a class with one or more private members to store the state and with an overloaded operator () to execute the function."

Let's see a simple example using functors to sort a vector of pointer to objects. As I cannot show examples from the code I write at work ( it's top secret ;) ), I've just made up an example using my favorite food: chocolate.

This is the Chocolate class:

#ifndef __CHOCOLATE_H__
#define __CHOCOLATE_H__

#include <string>

class Chocolate {
  public:
    Chocolate(std::string name, double cocoaPercentage, double price)
    {
      this->cocoaPercentage = cocoaPercentage;
      this->price = price;
      this->name = name;
    };
    ~Chocolate();

    double getCocoaPercentage() { return this->cocoaPercentage; };
    double getPrice() { return this->price; };
    std::string getName() { return this->name; };

  private:
    double cocoaPercentage; 
    double price;
    std::string name;
};
#endif /* __CHOCOLATE_H__ */

Imagine we'd like to sort the following vector:

vector<Chocolate*> chocolates;

using the STL sort algorithm and two different sorting criteria: by price and by cocoa percentage. 

There are two versions of STL sort. The first one takes two parameters, first and last, which are iterators to the initial and final positions of the sequence to be sorted, the range [first, last). This version uses the operator< to compare the elements of the class. As I said above, this version will not work.
The second version accepts, besides first and last, a third parameter, comp, which according to sort's C++ reference is a:

"Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise."

So, to sort our chocolates vector, we'll first have to create two functors: one for each sorting criteria.
I called them ComparatorByPrice and ComparatorByCocoaPercentage:

#ifndef CHOCOLATE_COMPARATORS
#define CHOCOLATE_COMPARATORS

#include "Chocolate.h"

class ComparatorByPrice {
  public:
    bool operator() (Chocolate *a, Chocolate *b) {
      return a->getPrice() < b->getPrice();
    }
};

class ComparatorByCocoaPercentage {
  public:
    bool operator() (Chocolate *a, Chocolate *b) {
      return a->getCocoaPercentage() < b->getCocoaPercentage();
    }
};

#endif /* CHOCOLATE_COMPARATORS */

Notice how we've implemented the () operator for both classes.

Once we have the functors, we just need to pass them to the sort function as its third parameter.

sort(chocolates.begin(), chocolates.end(), ComparatorByPrice());

Notice how we needed to add the () after ComparatorByPrice in order for it to work.

Ok, now that we finally have all the required ingredients to sort our chocolates, let's see the sorting in action:

#include "Chocolate.h"
#include "ChocolateComparators.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

void showChocolates(vector<Chocolate*> & chocolates);

int main(int argc, char **argv)
{
  vector<Chocolate*> chocolates;
  chocolates.push_back(new Chocolate("ChocoKoko", 80., 20.));
  chocolates.push_back(new Chocolate("ChocoLolo", 70., 30.));
  chocolates.push_back(new Chocolate("ChocoBebo", 25., 10.));
  chocolates.push_back(new Chocolate("ChocoBrian", 24., 15.));
  chocolates.push_back(new Chocolate("ChocoMiko", 30., 45.));
  
  cout<<"Sorted by price:"<<endl;
  sort(chocolates.begin(), chocolates.end(), ComparatorByPrice());
  showChocolates(chocolates);
  
  cout<<endl<<"Sorted by cocoa percentage:"<<endl;
  sort(chocolates.begin(), chocolates.end(), 
               ComparatorByCocoaPercentage());
  showChocolates(chocolates);
  
  for(unsigned int i=0; i<chocolates.size(); ++i) {
    delete chocolates[i];
  }
  return 0;
}

void showChocolates(vector<Chocolate*> & chocolates) {
  for(unsigned int i=0; i<chocolates.size(); ++i) {
    cout<<chocolates[i]->getName()<< " " 
      <<chocolates[i]->getPrice()<<" "
      <<chocolates[i]->getCocoaPercentage()
      <<"%"<<endl;
  } 
}

This is the output we get:

$ g++ main.cpp ChocolateComparators.h Chocolate.h -o sorters
$ ./sorters
Sorted by price:
ChocoBebo 10 25%
ChocoBrian 15 24%
ChocoKoko 20 80%
ChocoLolo 30 70%
ChocoMiko 45 30%

Sorted by cocoa percentage:
ChocoBrian 15 24%
ChocoBebo 10 25%
ChocoMiko 45 30%
ChocoLolo 30 70%
ChocoKoko 20 80%

In C++11 we could use lambdas instead of functors, but that will be material for a future post.

Update:
See how to do it using lambdas in this newer post: Sorting a vector of pointers to objects using STL and C++11 lambdas