C++ STL - How does the third argument of the STL sort() work?

Question

I wish to sort an array of objects of class Person on the basis of its data member 'age'. I store the objects in a vector<Person> v.

As far I have understood, there can be at least 4 ways to perform this action and I have the following questions based on the methods written below.

1. How does operator() defined inside a class work? Should I not overload the '<' operator here as well? Why '()' ?

2. I sent an object as the 3rd parameter in method 1. But, in method 2, I sent the name of a function. Why is it like that?

3. Which of the four methods is the best? I felt that method 3 was the easiest.

Method 1

class cmp
{
public:
    bool operator() (  Person const &a,  Person const &b )
    {
        return a.age < b.age ;
    }
};

sort( v.begin(), v.end(), cmp());

Method 2

bool cmp( const Person a, const Person b ) 
{
    return a.age < b.age ;
}

sort( v.begin(), v.end(), cmp );

Method 3

bool operator < ( const Person a, const Person b )
{
    return a.age < b.age ;
}

sort( v.begin(), v.end());

Method 4

//using lambda expression
sort( v.begin(), v.end(), [](const Person &a, const Person &b){return a.age < b.age;});

Answer 1

To sort a range using std::sort (or any function for that matter), it needs to know how two elements from the range are compared, in order to determine less than (or greater than) relationship.

The Standard Library function std::sort comes in two flavors: one uses operator<, the other uses a compare function/functor. You've used both of them in your code — in particular, the third one in your example uses < and the rest use compare function/functor.

As for which one is the best approach?

Well, it depends. The one which uses operator< is less flexible since it is fixed but requires you less typing as well. Use it when it suffices.

The other one is more flexible as you can pass any compare function and get your elements sorted accordingly. Use it when operator< doesn't suffice. Also, when you choose this flavor, you have other choices as well : the comparer could be a function, a functor, or a lambda — if you use function or functor (defined at namespace level), then you can reuse them; on the other hand, lambda is usually defined in a function scope, so it is not that reusable, unless you define it at namespace scope, in which case it is almost same as function.

Example, suppose you want to sort a vector of int in increasing order:

 std::vector<int>  v{10, 3, 12, -26};
 std::sort(v.begin(), v.end());
 print(v);

Output: -26,3,10,12. So operator< does do the job.

But what if you want the elements sorted considering only magnitude (i.e ignore signs), then you have to use the other flavor:

 std::vector<int>  v{10, 3, 12, -26};
 auto abs_cmp = [](int a, int b) { return std::abs(a) < std::abs(b); };
 std::sort(v.begin(), v.end(), abs_cmp);
 print(v);

Output : 3,10,12,-26. That is the output you would expect in this case.

Hope that helps.

Answer 2

The sort function has two overloads

i. void sort( RandomIt first, RandomIt last ); It doesn't accept compare function, it expects the items have operator< defined. You'r method 3 uses this overload.

template< class RandomIt >
void sort( RandomIt first, RandomIt last )
{
    ...

    if (*i < *j)
      ....

    ...
}

 

ii. void sort( RandomIt first, RandomIt last, Compare comp ); it accepts a compare function, it's useful when your items don't have operator< defined.

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

    if (comp(*i, *j))
      ....

    ...
}

Methods 1,2,4 use this overload. All the passed third arguments can be called by (). Method 1, sends an object by cmp(), this object has overloaded operator() and above code invokes it. Method 2 and 4, sends pointer to functions and a pointer to a function can be invoked by ().

Answer 3

How does operator() defined inside a class work? Should I not overload the '<' operator here as well? Why '()' ?

operator() is the function call operator. Instances of your class cmp are callable in the same way that a function is callable. The call is required by sort to perform the necessary comparison.

I sent an object as the 3rd parameter in method 1. But, in method 2, I sent the name of a function. Why is it like that?

Instances of cmp are callable. Function names are callable.

Which of the four methods is the best? I felt that method 3 was the easiest.

The main disadvantage of 3 is that you have defined that one Person is less than or greater than another Person according to their ages. What if you want to sort them by name elsewhere? You've already defined operator< for Person, so you can't do the same trick again. All three of the other methods define a comparison for use in a specific sort, rather than defining what it means in general to compare Person.

The main disadvantage of 2 is that it's somewhat harder for the compiler to inline than 1 or 4. It doesn't really have any advantages over 1, but for completeness it's nice that sort can take a function pointer.

The main advantage of 4 is that if you only use the comparison once, it's often nicer to have it right there in the same line of code that calls sort, instead of being off somewhere else in the file.

The main advantage of 1 is that it works in C++03 (unlike 4). 4 is more-or-less a new syntax for 1. 1 also has the advantage that it makes the comparator available for other code to use with the same name. You could achieve that with a lambda too if you wanted (you name a lambda by assigning it to an auto variable).