2

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)
Community
  • 1
  • 1
PHcoDer
  • 1,166
  • 10
  • 23
  • I don't think you want to compare pointers? Do you? Even if the arrays contain pointers to objects thant i think you probably want to compare the actual instances of the objects right? – Luca Angioloni Oct 16 '16 at 00:30
  • _"I am also trying to understand fundamentals of C++, as I am very new to C++."_ Which book are you using? – Lightness Races in Orbit Oct 16 '16 at 00:33
  • Hi, have you made it clear about the two options, it seems the first option (`(const ClassType*& ptr1, const ClassType*& ptr2)`) does not work, right? – kz28 May 05 '22 at 02:07

5 Answers5

3

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.

Galik
  • 47,303
  • 4
  • 80
  • 117
  • Could you elaborate on why don't we need `const` like `bool cmp(const ClassType* ptr1, const ClassType* ptr2)`? – Louis Go May 05 '22 at 02:46
  • 1
    @LouisGo You make a good point. I think I was probably just following the OP's code, but it is important that they should be `const` as sorting functions should not modify the values they are sorting. – Galik May 05 '22 at 06:46
1
(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.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • Thanks!. But what should be done with case of vector of pointers? There is not problem of copying. Also does use of const make sense with pointers? – PHcoDer Oct 16 '16 at 00:38
  • "In most situations this signature will also work," not when the type isn't copyable. – xaxxon Oct 16 '16 at 00:47
  • In the case of simple pointers, it makes very little difference. A good compiler will likely end up compiling the same, inlined code. – Sam Varshavchik Oct 16 '16 at 00:48
0

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.

xaxxon
  • 19,189
  • 5
  • 50
  • 80
  • I figued you'd be using sometihng like std::sort http://en.cppreference.com/w/cpp/algorithm/sort You don't "pass" a reference. The reference is automatically made if the thing you're calling takes a reference. – xaxxon Oct 16 '16 at 00:32
  • So what should be signature like? type (1) or type (2) in question. – PHcoDer Oct 16 '16 at 00:36
  • "It should look like your first example" – xaxxon Oct 16 '16 at 00:38
  • yes so my question is. In case of vector of pointers? There is no problem of copying of elements. here only pointer will be copied in case of pass by value too. Also does use of const make sense with pointers? – PHcoDer Oct 16 '16 at 00:40
  • Whatever the type is in your vector is the type you put in the comparator. Just literally copy/past it out. – xaxxon Oct 16 '16 at 00:46
0

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.

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18
0

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.

kz28
  • 781
  • 8
  • 23