7
\$\begingroup\$

This code is predicated on the notion that when sorting (or using a sorted collection of items, such as with std::lower_bound) you're usually comparing a single field in each object being sorted/searched.

So a typical sort might look something like:

// Sort by age
std::sort(people.begin(), people.end(), 
    [](Person const &a, Person const &b) { return a.age < b.age; });

Or:

// sort by height, descending:
std::sort(people.begin(), people.end(), 
    [](Person const &a, Person const &b) { return b.height < a.height; });

Although the lambda is cleaner than C++98 code, I'd really rather be able to specify something like by(height, descending). I haven't (yet) figured out a way to (quite) get to that ideal, but I think this gets us quite a bit closer:

#ifndef SORT_MEMBERS_H_
#define SORT_MEMBERS_H_

namespace sort {
    namespace detail {
        template <class FieldType, class RecordType>
        struct Desc {
            FieldType RecordType::*fn;
        public:
            Desc(FieldType RecordType::*fn) : fn(fn) {}

            bool operator()(RecordType const &a, RecordType const &b) {
                return b.*fn < a.*fn;
            }
        };

        template <class FieldType, class RecordType>
        struct Asc {
            FieldType RecordType::*fn;
        public:
            Asc(FieldType RecordType::*fn) : fn(fn) {}

            bool operator()(RecordType const &a, RecordType const &b) {
                return a.*fn < b.*fn;
            }
        };
    }

    template <class FieldType, class RecordType>
    detail::Asc<FieldType, RecordType> ascending(FieldType RecordType::*b) {
        return detail::Asc<FieldType, RecordType>(b);
    }

    template <class FieldType, class RecordType>
    detail::Desc<FieldType, RecordType> descending(FieldType RecordType::*b) {
        return detail::Desc<FieldType, RecordType>(b);
    }
}

#endif

Example usage would be something like this:

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include "sort_members.h"

struct Person
{
    std::string first_name;
    std::string last_name;
    int age;

    friend std::ostream &operator<<(std::ostream &os, Person const &person) {
        return os << person.first_name << " " << person.last_name << ", " << person.age;
    }
};

int main() {
    std::vector<Person> people = { 
        { "John", "Rambo", 42 }, 
        { "Joffrey", "Baratheon", 14 }, 
        { "Kyle", "Reese", 25 } 
    };

    std::sort(people.begin(), people.end(), sort::descending(&Person::age));

    std::cout << "Sorted by age, descending:\n";
    for (const auto& person : people)
        std::cout << person << "\n";

    std::cout << "\nSorted by last name:\n";
    std::sort(people.begin(), people.end(), sort::ascending(&Person::last_name));
    for (const auto& person : people)
        std::cout << person << "\n";
}

I'd welcome any comments--but I'm mostly interested in the part in the header; the file using it is just a demo, not anything very interesting in itself, beyond the fact that it demonstrates how the preceding code is used.

\$\endgroup\$
  • 3
    \$\begingroup\$ Use cppsort::sort(people, &Person::last_name) of course :p \$\endgroup\$ – Morwenn Jul 22 '17 at 15:43
4
\$\begingroup\$

This might be a bit nitpicky, but Asc and Desc aren't that good of names for classes. Granted, they are in your detail namespace, so it should be fine, but why not just write out the names Ascending and Descending?

I do find Asc more ambiguous than Desc, because I see "desc" as shorthand for "descending" more often.


Both Desc and Asc are structs, which means that your public: is redundant. You probably want to make them classes, as it seems you want to hide the fn member variable.


Why restrict the sort-by function to being by member variables? You could easily let it work for any callable object:

template <class F>
class Asc {
    F fn;
public:
    Asc(F fn) : fn(std::move(fn)) {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        // by separating the types like this, we gain a little bit
        // of generality. Not that it matters if we are using it
        // with std::sort only. However, really what the overall
        // utility is doing is defining a comparator, so you might
        // want to keep it more general
        return fn(std::forward<Lhs>(a)) < fn(std::forward<Rhs>(b));
    }
};

I know that, at this point, this removes the ability to use member functions at all, but we can use std::invoke to remedy that:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::invoke(fn, std::forward<Lhs>(a)) < std::invoke(fn, std::forward<Rhs>(b));
    }

Although std::invoke does require C++17. If you don't want to require C++17, this Stack Overflow question discusses how to get the behavior of std::invoke in C++11. In particular, you can use std::ref:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::ref(fn)(std::forward<Lhs>(a)) < std::ref(fn)(std::forward<Rhs>(b));
    }

Although you may want to wrap the std::ref(callable)(args...) into a utility function to make the code more self-documenting


There's also a small problem, where if the field we are sorting by is a pointer, you can have undefined behavior. Comparing pointers with operator< is only allowed if the pointers are from the same array. So it would be better to use std::less:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::less<>()(std::ref(fn)(std::forward<Lhs>(a)), std::ref(fn)(std::forward<Rhs>(b)));
    }

But if you don't have C++14, you'd have to write something like this instead:

    template <typename T>
    bool operator()(T const& a, T const& b) {
        auto cmp = std::less<
            std::decay_t<decltype(std::ref(fn)(a))>
        >();
        return cmp(std::ref(fn)(a), std::ref(fn)(b));
    }

Also, we can actually combine both Asc and Desc. Currently, the only difference is that you call operator< with the arguments in the other order.

Instead, what we can do is take a comparator in our class:

template <class F, class Compare = std::less<>>
class SortBy {
    F fn;
    Compare cmp;
public:
    SortBy(F fn, Compare cmp = {})
        : fn(std::move(fn))
        , cmp(std::move(cmp))
    {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return cmp(
            std::invoke(fn, std::forward<Lhs>(a)),
            std::invoke(fn, std::forward<Rhs>(b))
        );
    }
};

Then, you can reduce your ascending and descending functions down to a single function:

template<typename F, typename Compare = std::less<>>
SortBy<F, Compare> sort_by(F fn, Compare cmp = {}) {
    // by using uniform initialization, we don't have to repeat the
    // type of SortBy<...>
    return { std::move(fn), std::move(cmp) };
}

If the user wanted to sort descending, they'd have to use sort_by(..., std::greater<>). That does require that an operator> is defined for their type, but they can always define their own comparator that defines a greater-than by using operator<


Orthogonally, splitting the Lhs and Rhs arguments for the operator() makes our SortBy a transparent comparator, so we should indicate this by adding a is_transparent typedef:

template <class F, class Compare = std::less<>>
class SortBy {
    F fn;
    Compare cmp;
public:
    using is_transparent = void;

    SortBy(F fn, Compare cmp = {})
        : fn(std::move(fn))
        , cmp(std::move(cmp))
    {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return cmp(
            std::invoke(fn, std::forward<Lhs>(a)),
            std::invoke(fn, std::forward<Rhs>(b))
        );
    }
};
\$\endgroup\$
  • \$\begingroup\$ Excellent comments/suggestions. Thank you! \$\endgroup\$ – Jerry Coffin Jul 21 '17 at 23:01
  • \$\begingroup\$ std::common_type might help for your remark \$\endgroup\$ – Jarod42 Sep 7 '18 at 17:53
  • \$\begingroup\$ @Jarod42 That part was supposed to be a brief mention. I'm trying to decide if it's worth complicating it rather than leaving it as an "exercise for the reader" like the comment does \$\endgroup\$ – Justin Sep 7 '18 at 17:56
  • \$\begingroup\$ Other possibility is to not provide transparent comparer neither (template LHS, template RHS -> template T) (BTW is_transparent typedef is missing). \$\endgroup\$ – Jarod42 Sep 7 '18 at 18:03
2
\$\begingroup\$

The other reviews are good, but it's possible to create something much closer to the pleasant looking syntax you propose by using a macro.

#define byAscending(field, collection) std::sort(\
        collection.begin(), \
        collection.end(), \
        [](decltype(*collection.begin()) &a, decltype(*collection.begin()) &b){\
           return a.field < b.field;\
        })

It's a macro, and as such it won't win any beauty contests, but it does make the calling code easy to read and understand:

byAscending(age, people);

If desired, the macro could be made to encapsulate only the lambda. That might look like this:

#define byAscending(object, field) [](object &a, object &b){\
                                      return a.field < b.field;}

Usage of that version looks like this:

std::sort(people.begin(), people.end(), byAscending(Person, age));

I'm undecided as to whether this is better or worse than the original, but it seemed like a not unreasonable use of a macro.

\$\endgroup\$
1
\$\begingroup\$

This utility might have a small performance problem. It is harder for current optimizers to optimize this style of object, with a pointer to member function (PMF) as a data member.

I know this sounds a bit like black magic, but Stephan T. Lavavej claims that using std::mem_fn is bad because of poor optimizability in this CppCon talk. Basically, the optimizer can have difficulty seeing that a PMF stored as a data member is actually constant, making it difficult to inline.

However, if you don't store the PMF as a data member, the optimizer has a better time. Thus, it would be more optimizable in general to instead write a sort_by function with std::invoke:

namespace sort {
    template <typename Iter, typename F, typename Compare = std::less<>>
    void sort_by(Iter begin, Iter end, F fn, Compare cmp = {}) {
        std::sort(begin, end, [&](auto&& lhs, auto&& rhs) {
            return cmp(
                std::invoke(fn, std::forward<decltype(lhs)>(lhs)),
                std::invoke(fn, std::forward<decltype(rhs)>(rhs))
            );
        });
    }
}

By taking Compare as a parameter, we make it so that we don't need two separate utilities for sorting ascending vs descending. The user can specify they want to sort descending by passing in std::greater<>.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.