can a std::tuple be sorted at compilte-time/run-time depending on its values

Question

I am wondering if a constexpr std::tuple can be sorted at compile-time:

template<typename T>
struct A{ T val; }; // a constexpr-enabled class

constexpr auto t = std::make_tuple( A<int>{3}, A<float>{1.f}, A<double>{2.0});
constexpr auto s = sort(t, [](auto&& v){return v.val; });

static_assert(std::is_same_v<std::tuple<A<float>,
                                        A<double>, 
                                        A<int>>,decltype(s)>, "Wups");

Is that possible, which building blocks are needed here (std::sort is constexpr) ?

It is (as far as I know) impossible to do that at run-time, since one cannot determine the type of the sorted tuple at runtime. I cannot see a way also if one would build a type-map of all permutations, the actual permutation is still only known at runtime.

Answer https://stackoverflow.com/a/46006026/293195 gives some hints and it should work in compile-time, but how?

Answer 1

Here's an ok solution using Boost.Mp11:

template <auto F>
struct quote {
    template <typename... T>
    using fn = decltype(F(T{}...));
};

constexpr auto sort_t() {
    // predicate used for sorting
    using pred = quote<[](auto I, auto J){
        return mp_bool<(std::get<I>(t).val < std::get<J>(t).val)>{};
    }>;

    // this gives us an mp_list of the indices into 't', sorted
    using indices = mp_sort<
        mp_iota<mp_int<std::tuple_size_v<decltype(t)>>>,
        pred::fn>;

    // turn those indices into a new tuple
    return []<typename... Ts>(mp_list<Ts...>){
        return std::tuple(std::get<Ts::value>(t)...);
    }(indices{});
}

constexpr auto s = sort_t();

The last step might be cleaned up a bit.

---

Note that ideally this takes t as a non-type template parameter, but we won't be able to do that until probably C++23:

template <auto Tuple>
constexpr auto sort_tuple() { /* ... */ }

constexpr auto s = sort_tuple<t>();

---

Although actually it can take an auto const& non-type template parameter, which is good enough here:

template <auto const& in>
constexpr auto sort_tuple() {
    using pred = quote<[](auto I, auto J){
        return mp_bool<(std::get<I>(in).val < std::get<J>(in).val)>{};
    }>;
    using indices = mp_sort_q<
        mp_iota_c<std::tuple_size_v<std::decay_t<decltype(in)>>>,
        pred>;

    return []<typename... Ts>(mp_list<Ts...>){
        return std::tuple(std::get<Ts::value>(in)...);
    }(indices{});
}
constexpr auto s = sort_tuple<t>();