Is this a minor error in the documentation or am I missing something?

Question

I know this is a minor thing but I want to be precise on my understanding of std::sort().

Given the function template

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

one can read the following here (my emphasis):

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than the second.

But in the example right below one can see that neither the std::greater<int>() nor the lambda-expression [](int a, int b) { return b < a; } satisfy this requirement for the Compare function object.

Answer 1

It is somewhat confusing at first read but if you look a the Type requirements section it says:

Compare must meet the requirements of Compare.

which points to C++ concepts: Compare which says (emphasis mine):

The return value of the function call operation applied to an object of type Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this Compare type, and false otherwise.

and goes on to establish the requirements for comp(a, b) which is that it establishes strict weak ordering relation with the following properties:

• For all a, comp(a,a)==false
• If comp(a,b)==true then comp(b,a)==false
• if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

Answer 2

That is correct if you read that along with this (taken from the same doc):

Sorts the elements in the range [first, last) in ascending order.

That is, to sort the range in increasing order, the cmp must return true if first argument is less than second, else the range will be sorted in decreasing order. Both the examples which use std::greater<int> and lambda are used to sort the range in decreasing order!

Answer 3

It's supposed to compare less in terms of sorting objects from smaller to greater, i.e. ascending order, according to the definition of the sorting comparator.

The interface between std::sort and the comparator is defined it terms of "compare two objects and tell me which one appear earlier in the output". Less is just what the std::sort docs define as "earlier in the output", not less than.

For greater, "compares-greater-than" are to appear earlier in the output, so it tells the sorter that these are of "less" value, so that the sorting algorithm gets right according to what we tell them.

It's all about separating the algorithm (sorting according to some order) and the actual comparison. These two need an interface.

If you think in terms of Rhubarb Pies (my favourite "abstract" object), they can be compared for radius (then we need to return true if Pie A if it's radius is less than Pie B). We might also want to sort from tastiest to healthiest, thus returning true if Pie A has more calories than Pie B.

Less means ordered below/earlier in the ascending order.

(Having a fourth arg bool reversed to std::sort is just unnecessary, since we can supply a lambda with an inversed operator/comparison.)

Answer 4

Less than something is relative to what you wants. What is really needed, is in fact a strict ordering.