Sorting a vector of pointers to objects using STL and C++11 lambdas

One year ago I posted about how to sort a vector of pointers to objects using STL and functors
As I said then, in C++11 we don't need to use functors, we can use lambdas instead. To show how, we'll use the example from that post again.

We have a stl::vector container that contains pointers to objects of some class, and we'd like to sort them based on the value of some member variable using a STL algorithm.
Let's use the Chocolate class again:

#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__ */

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.

We'll use the version of the sort algorithm that 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."

The only difference is that, this time, instead of sorting our chocolates vector using functors, we'll use C++11 lambdas or anonymous functions (one for each sorting criterion).
According to wikipedia:

"...an anonymous function (also function constant, function literal, or lambda function) is a function (or a subroutine) defined, and possibly called, without being bound to an identifier."

So now we just need to pass a lambda function (the sorting criterion) to the sort function as its third parameter.

Let's see the sorting in action:

#include "Chocolate.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(), 
    [] (Chocolate *a, Chocolate *b) {
        return a->getPrice() < b->getPrice();
  });
  showChocolates(chocolates);
  
  cout<<endl<<"Sorted by cocoa percentage:"<<endl;
  sort(chocolates.begin(), chocolates.end(), 
    [] (Chocolate *a, Chocolate *b) {
        return a->getCocoaPercentage() < b->getCocoaPercentage();
  });
  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;
  } 
}

We compile it by doing:

$ g++ -std=c++11 Chocolate.h main.cpp -o sorters

And this is the output we get:

$ ./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%

That's how we can sort a vector of pointers to objects using STL and C++11 lambdas.

Interesting Talk: "Stephan T. Lavavej - Standard Template Library (STL), 6"

I've resumed watching Stephan T. Lavavej's Standard Template Library series at Channel 9.
This talk is an introduction to STL algorithms:

• Stephan T. Lavavej - Standard Template Library (STL), 6 of n

I like watching this while I have gedit and a console open to test things.

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

Watched at work: "STL with Stephan T. Lavavej"

Lately I've been very busy after work because I had some assignments to submit to the UOC (what I'm doing there), so I haven't posted the links of the last three videos we've watched at work.

We're currently watching a series of talks about the STL library published in Microsoft's Channel 9 by Stephan T. Lavavej who is a software engineer that works developing and maintaining Microsoft's STL version. I like his talks very much.
These are the ones we've watched so far:

1. Sequence Containers.
2. Associative Containers. 
3. Smart Pointers.

There are a lot of videos about C++ in C9.