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

The requirements for a comparator are far looser than you think:

1. It must accept two dereferenced iterators into the sequence as arguments.
   Using an implicit conversion-sequence is fine.
2. The return-value must be contextually-convertible to bool.
   An explicit conversion-operator works just fine.
3. It must be a copyable and nothrow-destructible complete type.
4. It must not modify the arguments, so it doesn't interfere with the calling algorithm.
   That does not in any way imply the use of constant references if references are used at all.
5. It must induce a full weak order (cmp(a, b) implies !cmp(b, a), cmp(a, b) && cmp(b, c) implies cmp(a, c)).

So, a valid but fairly useless comparator would be:

template <class... X>
auto useless(X&&...) { return nullptr; }

Answer 2

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.

Answer 3

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

You can't.

But the requirements of Compare are not just for sorting arrays, or just for sorting at all!

They're for any time you want to compare one thing to another thing.

Is minutes(42) less than hours(1)? Yes! You may find useful a comparator for such occasions.

Compare is a more general concept that finds uses throughout the language.

Is ti possible that someone provide a small example with different types for std::sort's comparator function

Others have shown examples that indicate how silly you have to get to find a "useful" example to use against std::sort specifically.

But it's not "std::sort's comparator function". It's a comparator function, which you just so happen to be using with std::sort.

It's true that, when doing so, you probably want the particular comparator that you pick to accept operands of the same type.

Answer 4

The type requirements on Compare are not saying much about the elements of the sequence you are sorting, but instead they are allowing all comps for which

if (comp(*first, *other))

is valid.

Most of the time, Type1 will be equal to Type2, but they are not required to be equal.

Answer 5

But I still cannot get it exactly how we can have 2 different types in a single array

You cannot have two different types in a single array.

An array can have objects of only single type. But that single type must be implicitly convertible to both argument types of cmp.

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

Here you go:

int arr[] = {1, 2, 3, 0};
auto cmp = [](const int &a, const long &b) {
    return a < b;
};
std::sort(std::begin(arr), std::end(arr), cmp);

Note the two different arguments of cmp. This is just a minimal example, which is technically correct, but admittedly nonsensical. Frankly, I've never encountered a case where it would be useful to have different types for the arguments of a comparison function.

Answer 6

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

You can't have two different types in an array. The comparator doesn't suggest it's possible. It's specified like that simply because:

1. The code can be well formed when the types are not the same.
2. Demanding the same type is a restriction that serves little to no purpose.

So the specification offers a looser contract than is "obvious", in order to help our code be more flexible if needed. As a toy example, say we have this comparator laying around:

auto cmp(int a, long b) -> bool { return a < b; }

Why prevent us from using this perfectly legal (albeit silly) function to sort an array of integers?