C++ STL sort() function, binary predicate

Question

I have a piece of code that confuses me:

   sort(data, data+count, greater<int>() );

it is a sort function in the C standard library. I am having trouble figuring out the meaning of the third argument. I have read that it is called a binary predicate. What does that mean and how can I make my own such predicate?

Answer 1

The third argument is called a predicate. You can think of a predicate as a function that takes a number of arguments and returns true or false.

So for example, here is a predicate that tells you whether an integer is odd:

bool isOdd(int n) {
    return n & 1;
}

The function above takes one argument, so you could call it a unary predicate. If it took two arguments instead, you would call it a binary predicate. Here is a binary predicate that tells you if its first argument is greater than the second:

bool isFirstGreater(int x, int y) {
    return x > y;
}

Predicates are commonly used by very general-use functions to allow the caller of the function to specify how the function should behave by writing their own code (when used in this manner, a predicate is a specialized form of callback). For example, consider the sort function when it has to sort a list of integers. What if we wanted it to sort all odd numbers before all even ones? We don't want to be forced to write a new sort function each time that we want to change the sort order, because the mechanics (the algorithm) of the sort is clearly not related to the specifics (in what order we want it to sort).

So let's give sort a predicate of our own to make it sort in reverse:

// As per the documentation of sort, this needs to return true
// if x "goes before" y. So it ends up sorting in reverse.
bool isLarger(int x, int y) {
    return x > y;
}

Now this would sort in reverse order:

sort(data, data+count, isLarger);

The way this works is that sort internally compares pairs of integers to decide which one should go before the other. For such a pair x and y, it does this by calling isLarger(x, y).

So at this point you know what a predicate is, where you might use it, and how to create your own. But what does greater<int> mean?

greater<T> is a binary predicate that tells if its first argument is greater than the second. It is also a templated struct, which means it has many different forms based on the type of its arguments. This type needs to be specified, so greater<int> is the template specialization for type int (read more on C++ templates if you feel the need).

So if greater<T> is a struct, how can it also be a predicate? Didn't we say that predicates are functions?

Well, greater<T> is a function in the sense that it is callable: it defines the operator bool operator()(const T& x, const T& y) const;, which makes writing this legal:

std::greater<int> predicate;
bool isGreater = predicate(1, 2); // isGreater == false

Objects of class type (or structs, which is pretty much the same in C++) which are callable are called function objects or functors.

Answer 2

There is a class template called greater which needs a type argument. So you provide int as one. It became greater<int> and you create an instance of this class and pass it to the function as third argument.

Such an object is called function object or simply functor in C++, as the class overloads () operator. It's a callable entity. Its like this:

template<typename T>
struct greater
{
   bool operator()(const T &a, const T &b)
   {
      //compare a and b and return either true or false.
      return a > b;
   }
};

If you create an instance of greater<int> and, say, the object is g, then you can write g(100,200) which evaluates to a boolean value, as the expression g(100,200) calls operator(), passing 100 as first argument and 200 as second argument, and operator() compares them and return either true or false.

       std::cout << g(100,200) << std::endl;
       std::cout << g(200,100) << std::endl;

Output:

0
1

Online demo : http://ideone.com/1HKfC