comparator for sorting a vector contatining pointers to objects of custom class

Question

By this question I am also trying to understand fundamentals of C++, as I am very new to C++. There are many good answers to problem of sorting a vector/list of custom classes, like this. In all of the examples the signature of comparator functions passed to sort are like this:

(const ClassType& obj1, const ClassType& obj2)

Is this signature mandatory for comparator functions? Or we can give some thing like this also:

(ClassType obj1, ClassType obj2)

Assuming I will modify the body of comparator accordingly.

If the first signature is mandatory, then why? I want to understand reasons behind using const and reference'&'. What I can think is const is because you don't want the comparator function to be able to modify the element. And reference is so that no multiple copies are created.

How should my signature be if I want to sort a vector which contains pointers to objects of custom class? Like (1) or (2) (see below) or both will work? vertor to be sorted is of type vector

(1)

(const ClassType*& ptr1, const ClassType*& ptr2)

(2)

(ClassType* ptr1, ClassType* ptr2)

Answer 1

I recommend looking through This Documentation.

It explains that the signature of the compare function must be equivalent to:

bool cmp(const Type1& a, const Type2& b);

Being more precise it then goes on to explain that each parameter needs to be a type that is implicitly convertable from an object that is obtained by dereferencing an iterator to the sort function.

So if your iterator is std::vector<ClassType*>::iterator then your arguments need to be implicitly convertable to ClassType*.

If you are using something relatively small like an int or a pointer then I would accept them by value:

bool cmp(const ClassType* ptr1, const ClassType* ptr2) // this is more efficient

NOTE: I made them pointers to const because a sort function should not modify the values it is sorting.

Answer 2

(ClassType obj1, ClassType obj2)

In most situations this signature will also work, for comparators. The reason it is not used is because you have to realize that this is passing the objects by value, which requires the objects to be copied.

This will be a complete waste. The comparator function does not need to have its own copies of its parameters. All it needs are references to two objects it needs to compare, that's it. Additionally, a comparator function does not need to modify the objects it is comparing. It should not do that. Hence, explicitly using a const reference forces the compiler to issue a compilation error, if the comparator function is coded, in error, to modify the object.

And one situation where this will definitely not work is for classes that have deleted copy constructors. Instances of those classes cannot be copied, at all. You can still emplace them into the containers, but they cannot be copied. But they still can be compared.

Answer 3

const is so you know not to change the values while you're comparing them. Reference is because you don't want to make a copy of the value while you're trying to compare them -- they may not even be copyable.

It should look like your first example -- it's always a reference to the const type of the elements of the vector.

If you have vector, it's always:

T const & left, T const & right

So, if T is a pointer, then the signature for the comparison includes the comparison.

Answer 4

There's nothing really special about the STL. I use it for two main reasons, as a slightly more convenient array (std::vector) and because a balanced binary search tree is a hassle to implement. STL has a standard signature for comparators, so all the algorithms are written to operate on the '<' operation (so they test for equality with if(!( a < b || b < a)) ). They could just as easily have chosen the '>' operation or the C qsort() convention, and you can write your own templated sort routines to do that if you want. However it's easier to use C++ if everything uses the same conventions.

The comparators take const references because a comparator shouldn't modify what it is comparing, and because references are more efficient for objects than passing by value. If you just want to sort integers (rarely you need to sort just raw integers in a real program, though it's often done as an exercise) you can quite possibly write your own sort that passes by value and is a tiny bit faster than the STL sort as a consequence.

Answer 5

You can define the comparator with the following signature:

bool com(ClassType* const & lhs, ClassType* const & rhs);

Note the difference from your first option. (What is needed is a const reference to a ClassType* instead of a reference to a const ClassType*)

The second option should also be good.