11
\$\begingroup\$

Motivation

Quite often, I find myself creating types that must be compared memberwise. For example, consider this simple Person:

#include <string>

struct Person
{
    // Pretend that the falsehoods programmers believe about names are
    // all actually true.
    std::string first_name;
    std::string last_name;
    std::string birthdate;  // e.g. "1985-07-03"
};

Suppose we want these to sort by last name, tie-breaking with first name, and then by age. The standard idiom is to create a tuple, and compare that:

bool operator<(const Person& other) const {
    return std::tie(last_name, first_name, other.birthdate)
        <  std::tie(other.last_name, other.first_name, birthdate)
}

This is a bit tedious and error-prone - it's easy to mess up the swapping of birthdate and other.birthdate, for example.

So I've created a builder for memberwise comparison. It's easy to use: start with an empty comparator and add or subtract pointers to member fields or functions. Adding will append an ascending ordering, and subtracting will append a descending ordering:

std::sort(std::begin(people), std::end(people),
          sorting::compare{} + &Person::last_name + &Person::first_name
                             - &Person::birthdate);

The code

#include <functional>
#include <tuple>

namespace sorting {

    namespace implementation {

        template<typename T>
        concept bool Comparator = requires {
            typename T::comparable_type;
        };

        template<Comparator Sort>
        struct reverse {
            using comparable_type = typename Sort::comparable_type;
            const Sort sort;

            bool operator()(const comparable_type& a,
                            const comparable_type& b) const
            {
                return sort(b, a);
            }

            auto&& operator-() && { return sort; }
        };

        template<Comparator First, Comparator Second>
        struct sequence {
            using comparable_type = typename First::comparable_type;
            const First first;
            const Second second;

            bool operator()(const comparable_type& a,
                            const comparable_type& b) const
            {
                return first(a, b) || !first(b,a) && second(a, b);
            }

            sequence operator-() const { return {-first, -second}; }
        };

        template<typename T, typename V>
        struct by_member
        {
            using comparable_type = T;
            V T::*const member;

            bool operator()(const comparable_type& a,
                            const comparable_type& b) const
            {
                return std::invoke(member, a) < std::invoke(member, b);
            }

            auto operator-() const { return reverse<by_member>{*this}; }
        };

        template<typename T, typename V>
        constexpr auto sort_by(V T::*m) { return by_member<T,V>{m}; }
        template<Comparator T>
        constexpr const T& sort_by(const T& t) { return t; }

        // Functions for combining comparators
        template<Comparator A, Comparator B>
        requires std::is_same_v<typename A::comparable_type,
                                typename B::comparable_type>
        constexpr auto operator+(const A& a, const B& b) -> sequence<A, B>
        {
            return { a, b };
        }

        template<Comparator A, Comparator B>
        requires !std::is_same_v<typename A::comparable_type,
                                 typename B::comparable_type>
        constexpr auto operator+(const A& a, const B& b) = delete;

        template<typename A, typename B>
        constexpr auto operator+(const A& a, const B& b)
        {
            return sort_by(a) + sort_by(b);
        }

        template<typename A, typename B>
        constexpr auto operator-(const A& a, const B& b)
        {
            return sort_by(a) + -sort_by(b);
        }

        // Empty object that's a public starting point for combining comparers.
        // This allows ADL to find all the necessary implementation classes.
        struct compare
        {
            template<typename T>
            auto operator+(T&& t) { return sort_by(t); }
            template<typename T>
            auto operator-(T&& t) { return -sort_by(t); }
        };
    }

    // Here's the entirety of the public interface:

    using implementation::compare;
}

// Test program:

#include <string>

struct Person
{
    std::string first_name;
    std::string last_name;
    std::string birthdate;

    static auto const& default_compare() {
        static auto const default_compare
            = sorting::compare{} + &Person::last_name
                                 + &Person::first_name - &Person::birthdate;
        return default_compare;
    }

    bool operator<(const Person& other) const {
        return default_compare()(*this, other);
    }
};

#include <algorithm>
#include <iostream>

template<std::size_t N>
std::ostream& operator<<(std::ostream& os, const Person (&people)[N])
{
    for (auto p: people)
        os << "  " << p.first_name << ' ' << p.last_name << '\n';
    return os;
}

int main()
{
    Person people[] = {
        { "Emmett",    "Brown", "1925-07-03" },
        { "Marty",     "McFly", "1968-07-03" },
        { "Jennifer", "Parker", "1968-07-03" },
        { "George",    "McFly", "1938-07-03" },
        { "Lorraine",  "McFly", "1938-04-03" },
        { "Biff",     "Tannen", "1938-07-03" },
    };

    std::sort(std::begin(people), std::end(people));
    std::clog << "Default order:\n"
              << people << "\n";

    std::sort(std::begin(people), std::end(people),
              sorting::compare{} - &Person::birthdate
                  + Person::default_compare());
    std::clog << "Youngest first:\n"
              << people << "\n";

    std::sort(std::begin(people), std::end(people),
              sorting::compare{} + &Person::last_name
                  + &Person::birthdate + &Person::first_name);
    std::clog << "By family, then birthdate:\n"
              << people;
}

Because I use C++ Concepts Lite, that will need to be enabled in your compiler, if you're reading this before that is standard. I used g++ -std=c++17 -fconcepts, but newer standards should work, too.


Concerns

Obviously I'd like to make my code better in any way.

I did attempt to change the sequence type to a variadic template. Although I was successful in constructing these, I couldn't work out how to call the next function inside operator(). And I doubt that it's any better for compilation or for the generated code. But it might improve the error messages when the programmer makes a mistake.

\$\endgroup\$
  • 2
    \$\begingroup\$ Looks interesting -- I look forward to reviewing this later. \$\endgroup\$ – Edward Apr 19 '18 at 17:01
  • \$\begingroup\$ Interesting, but I fear inefficient... \$\endgroup\$ – Deduplicator Apr 19 '18 at 19:25
  • \$\begingroup\$ @Deduplicator, if you can identify places that are inefficient (do you mean at run-time, or during compilation?), please do write an answer, however short. Thanks! \$\endgroup\$ – Toby Speight Apr 20 '18 at 7:37
  • \$\begingroup\$ Well, the relative inefficiency is caused by having and using data (member-pointers) instead of only code. Of course, if it is all inlined, that will disappear. \$\endgroup\$ – Deduplicator Apr 24 '18 at 21:02
5
\$\begingroup\$

You forgot to include <type_traits>.

auto&& operator-() && { return sort; }

The && qualification seems questionable, and the decision to return an lvalue reference from a && qualified function even more so.

sequence operator-() const { return {-first, -second}; }

This function appears to have been untested. Based on what you have here, the chance that -first has the same type as first seems to be vanishingly low.

    template<Comparator A, Comparator B>
    requires std::is_same_v<typename A::comparable_type,
                            typename B::comparable_type>
    constexpr auto operator+(const A& a, const B& b) -> sequence<A, B>

Pinning down to a single common comparable_type seems unnecessary, not the least because the type of member pointers can be surprising in the presence of inheritance:

struct MiddleNamedPerson : Person { std::string middle_name; };

&MiddleNamedPerson::first_name is of the type std::string Person::*, while &MiddleNamedPerson::middle_name is of the type std::string MiddleNamedPerson::*, so attempts to compose them will fail under your scheme.

Here's an (untested) sketch of variadic sequence:

template<class... Ts>
struct sequence {
    // other stuff
    const std::tuple<Ts...> tup;
    template<class T, class U>
    bool operator()(const T& t, const U& u) const {
        return std::apply([&](const auto&... comps) {
            bool result = false, stop = false;
            ((stop || (comps(t, u) ? stop = true, result = true :
                       comps(u, t) ? stop = true, result = false : false )),
              ...);
            return result;
        }, tup);
     }
};

And another variant that's perhaps easier to follow:

template<class... Ts>
struct sequence {
    // other stuff
    const std::tuple<Ts...> tup;

    template<std::size_t N> 
    using size_constant = std::integral_constant<std::size_t, N>;

    template<class T, class U>
    bool operator()(const T& t, const U& u) const {
        return compare(t, u, size_constant<0>());
    }
    template<class T, class U, std::size_t N>
    bool compare(const T& t, const U& u, size_constant<N>) const {
       if(std::get<N>(tup)(t, u)) return true;
       if(std::get<N>(tup)(u, t)) return false;
       return compare(t, u, size_constant<N+1>());
    }
    template<class T, class U>
    bool compare(const T& t, const U& u, 
                 size_constant<sizeof...(Ts)>) const {
        return false;
    }
};
\$\endgroup\$
  • \$\begingroup\$ Yes, the sequence - operator missed testing. It was just supposed to be an optimization, and I don't think it's a worthwhile one. It won't get used unless you use the class non-idiomatically, so not worth keeping. Other points all good - though I'll have to do some thinking about whether/how to keep comparable_type. I did start off with it in the compare{} (factory) object, to dictate what it could combine with. Thanks for the good advice! \$\endgroup\$ – Toby Speight Apr 25 '18 at 9:28

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.