Is it legal for a standard algorithm comparator to accept objects of different types?

Question

An answer recently posted on Stack Overflow showed code that provides, to a standard algorithm, a comparator taking operands of different types:

2. Use a comparator with templated operator().

Instead of using a lambda, define a functor with a templated operator().

struct comparator
{
    template<typename T, typename U>
    bool operator()(T const& lhs, U const& rhs) const {
        return lhs.mCommonField < rhs.mCommonField;
    }
};

Then, it's as easy as:

std::sort(aStructs.begin(), aStructs.end(), comparator{});
std::sort(bStructs.begin(), bStructs.end(), comparator{});
// ...
std::set_intersection(aStructs.begin(), aStructs.end(),
                      bStructs.begin(), bStructs.end(),
                      std::back_inserter(intersection),
                      comparator{}
                      );

Just note that as there is a template in the comparator, it must be declared outside of function scope. Live example on Coliru Viewer.

Apparently this at least works in practice, as evidenced by the working live demo.

But is it strictly allowed by the standard?

Answer 1

The corresponding section in the standard is §25.4. The only requirements on the type of the Compare parameter are in §25.4/2:

Compare is a function object type. The return value of the function call operation applied to an object of type Compare, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

In other words, when called, it can't change the values pointed at by the iterators and should yield a strict weak ordering on the values. Since that comparator satisfies both of these requirements, yes, it's legal!

In fact, this kind of comparison functor is exactly what is proposed in N3421 - Making Operator Functors greater<>, now part of the C++14 standard. It provides void specializations for the standard library functors that perfect forward comparisons to the corresponding operator, if any. For example (taken from the proposal paper):

namespace std
{
    template <> struct greater<void> {
      template <class T, class U> auto operator()(T&& t, U&& u) const
        -> decltype(std::forward<T>(t) > std::forward<U>(u))
           { return std::forward<T>(t) > std::forward<U>(u); }
    };
}