Different types for `std::sort` comparator in C++

Question

When we provide a comparator function for std::sort, we use the following overload:

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

in which the comparator function for std::sort should have the following syntax:

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

But as you can see a and b may have different types. cppreference says:

The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them. ​

But I still cannot understand exactly how we can have 2 different types in a single array when we try to sort it.

Is it possible for someone to provide a small example with different types for std::sort's comparator function?

Answer 1

Its not about what is stored in the array, only one type can ever be stored. It is about what the comparator function is. Take for example this:

struct Animal {}; struct Cat : Animal {}; struct Dog : Animal {}; struct Hound : Dog {};  bool cmp(const Animal &a, const Animal &b); 

Even if you have a list of Dogs, Cats or Hounds you can still sort them with the function cmp because they are all implicitly convertible. ie.

std::vector<Hound> hounds; ... // fill hounds std::sort(hounds.begin(), hounds.end(), cmp); 

And you can even imagine cases where Type1 and Type2 are not the same, eg.:

bool cmp(const Animal &a, const Dog &b); etc ... 

Although this would be exceedingly rare.

The types Type1 (Animal) and Type2 (Dog) must be such that an object of type RandomIt (Hound) can be dereferenced and then implicitly converted to both of them. ​Which is true.

The point is that a restriction on the types that a cmp function can take to the same, precludes generality. In some cases this is a good idea, but in this case it would be unreasonably strict and may force problems for edge case implementations. Furthermore, the cmp function used instd::sort is bound by the requirements set out for Compare (probably for simplicity). Compare requirements are used for all sorts of other things, like std::max.