Shortcut for creating a comparator based on a member field or function

Question

I often find myself wanting to create a comparator objects for a struct or class which simply extracts one member of the class and does the usual < comparison on that.

For example:

struct student {
   int id;
   std::string name;
};

// sort by ID
std::sort(students.begin(), students.end(), [](const student& l, const student& r){ return l.id < r.id; });

There's a lot of boilerplate there, in particular because we have to repeat the declaration for l and r. Is there a way in the standard library to create a comparator based on an "extractor" function which returns an object to compare on?

Something like:

std::sort(students.begin(), students.end(), compare_on([](const student& s){ return s.id; });

I'm using C++11, but also interested if there are solutions in later standards that don't apply in C++11 (so I can add something to my "reasons to upgrade" list).

I'm asking here about using a single member as the comprand, and also the default comparison "less than", but bonus points for techniques that compose easily, e.g. that allow you use two fields in lexicographic order, or to change the comparison operator.

Answer 1

What you're effectively looking for is to allow projections to be passed into algorithms. N4128 proposed this for the standard library, and C++20 will have these for many of the algorithms.

But until then, we can do this ourselves. Write a new overload of sort:

struct identity {
    template <typename T>
    T&& operator()(T&& t) const noexcept { return std::forward<T>(t); }
};

// because no std::less<> in C++11 yet
struct less {
    template <typename T, typename U>
    constexpr bool operator()(T const& lhs, U const& rhs) const {
        return lhs < rhs;
    }
};

template <typename Range, typename Comp=less, typename Proj=identity>
void sort_proj(Range& range, Comp comp={}, Proj proj={}) {
    using std::begin;
    using std::end;
    auto first = begin(range), last = end(range);
    using reference = typename std::iterator_traits<decltype(first)>::reference;

    std::sort(first, last,
        [&](reference lhs, reference rhs) {
            return comp(std::ref(proj)(lhs), std::ref(proj)(rhs));
        });
}

std::ref(f)(x) is a trick to get INVOKE functionality in C++11. It basically allows you to pass pointers to members as the projection. This implementation would let you write:

sort_proj(students, less{}, &student::id);

Note that the projection is independent of the ordering. So I could do all kinds of things pretty easily:

sort_proj(students);                            // sort on students, if they're ordered
sort_proj(students, greater{}, &student::name); // decreasing, by name
sort_proj(students, less{},                     // by name, then id
    [](student const& s) {
        return std::tie(s.name, s.id);
    });

---

This kind of approach is super useful at eliminating a lot of boilerplate from algorithms in general. I have a header that's just full of projection-based overloads of many of the commonly used standard algorithms.

Answer 2

You can define a utility class

template <class Fct> class compare_on {
  public:
    compare_on(Fct&& get) : get(std::forward<Fct>(get)) {}

    template <class T> bool operator()(const T& lhs, const T& rhs)
    {
       return get(lhs) < get(rhs);
    }

  private:
    Fct get;
};

and then pass it to std::sort just like you depicted it (using C++17 class template argument deduction)

std::sort(students.begin(), students.end(),
    compare_on([](const student& s){ return s.id; }));

As of C++17, @Justin pointed out int the comments that the actual comparison can be improved (with #include <functional>) such that

return std::invoke(get, lhs) < std::invoke(get, rhs);

which allows for an instantiation with data member references:

std::sort(students.begin(), students.end(), compare_on(&student::id));

When bound to C++11, forget about std::invoke and go with an explicit instantiation of compare_on. The latter isn't suitable for lambdas, hence the usual argument-deduction make_* helper:

template <class Fct> auto make_compare_on(Fct&& get)
    -> decltype(compare_on<Fct>(std::forward<Fct>(get)))
{
    return compare_on<Fct>(std::forward<Fct>(get));
}

Note that you can remove the trailing return type in C++14.

As a final note, the naming here should be improved: compare_on is misleading, as it hides what the function object really does - comparing by operator <. Maybe compare_less_then or something similar would be better, or adding another template parameter that can be specified as one of the standard predicates (std::less etc.).

Answer 3

range-v3 implements projection:

// sort by ID
ranges::sort(students, std::less<>{}, &student::id);