std::tuple 能否根据其值在 compilte-time/run-time 处排序

Question

我想知道是否可以在编译时对 constexpr std::tuple 进行排序：

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");

可以吗，这里需要哪些积木（std::sort是constexpr）？

（据我所知）不可能在运行时间做到这一点，因为在运行时间无法确定已排序元组的类型。如果要构建所有排列的类型图，我也看不到一种方法，实际排列仍然只在运行时间知道。

回答给出了一些提示，它应该在编译时工作，但是如何呢？

Answer 1

这是一个使用 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();

最后一步可能会稍微清理一下。

请注意，理想情况下，这会将 t 作为非类型模板参数，但我们可能要等到 C++23 才能做到这一点：

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

constexpr auto s = sort_tuple<t>();

虽然实际上它可以接受一个 auto const& 非类型模板参数，这在这里就足够了：

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>();

Answer 2

您可以使用标准库的 std::sort 算法（如果它是 constexpr，因为它应该在 C++20 中），即使它通过仅包装期望同类类型元组的索引作为 std::variant 数组中的不同类型并对其进行排序。

然后您可以提供您想要的任何谓词，只要可以将元组中的每对类型与谓词进行比较并且它满足比较器 std::sort.[=24= 的通常要求]

特别是有一个 std::less<void> 专业化接受两种任意类型与 < 进行比较，所以我使用它作为默认值，类似于 std::sort 所做的。

正如@Barry 所提到的，您需要将元组作为非类型模板参数来访问函数内部的值。如果您还想在排序算法内部访问谓词的状态，那么您还需要将其作为引用非类型模板参数传递。

另请注意，这可能需要元组大小的二次编译时间，因为需要比较器的实例化和访问次数。对于大型元组，您可能可以实现自己的算法，该算法不需要使用模板元编程进行二次实例化，而模板元编程只会实例化所需的比较。

或者，可以通过将元组中包含的值（或 std::refs 到值）复制到 std::variants 来减少所需实例化的数量，而不是在删除重复类型之后，将所需实例化和访问的数量减少到 distinct 类型数量的二次方。请参阅此答案的历史记录，了解一个不完整的实现，该实现实际上并未对类型进行重复数据删除，因此可能仍然是元组大小的二次方。

namespace detail {
    template<auto& t, typename Pred, auto... Is>
    constexpr auto sort(Pred&& pred, std::index_sequence<Is...>) {
        constexpr auto sorted_indices = [&]{
            using var_t = std::variant<std::integral_constant<std::size_t, Is>...>;

            std::array indices{var_t{std::in_place_index<Is>}...};

            std::sort(indices.begin(), indices.end(), [&](auto x, auto y){
                return std::visit([&](auto a, auto b) {
                    return pred(std::get<decltype(a)::value>(t), std::get<decltype(b)::value>(t));
                }, x, y);
            });

            return indices;
        }();

        using old_tuple_t = std::remove_cvref_t<decltype(t)>;
        using new_tuple_t = std::tuple<std::tuple_element_t<sorted_indices[Is].index(), old_tuple_t>...>;
        return new_tuple_t{std::get<sorted_indices[Is].index()>(t)...};
    }
}

template<auto& t, typename Pred = std::less<void>>
constexpr auto sort(Pred&& pred = {}) {
    using size = std::tuple_size<std::remove_cvref_t<decltype(t)>>;
    return detail::sort<t>(std::forward<Pred>(pred), std::make_index_sequence<size::value>{});
}

测试（从问题中稍微更正并包括一些重复的类型）：

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

// Test case 1 comparing A's val members as predicate
constexpr auto t = std::make_tuple( A<int>{10}, A<float>{1.f}, A<double>{5.0}, A<int>{3});
constexpr auto s = sort<t>([](auto&& v, auto&& w){ return v.val < w.val; });
static_assert(std::is_same_v<const std::tuple<A<float>, A<int>, A<double>, A<int>>, decltype(s)>);

// Test case 2 using default `std::less<void>` for comparison
constexpr auto t2 = std::make_tuple(10, 1.f, 5.0, 3);
constexpr auto s2 = sort<t2>();
static_assert(std::is_same_v<const std::tuple<float, int, double, int>, decltype(s2)>);

在 this godbolt 中的 GCC 主干上进行了测试。它不适用于带有 libstdc++ 或 libc++ 的 Clang 主干。从产生的错误消息来看，我认为这是因为它没有实现 constexpr std::sort 中的任何一个。

Answer 3

这里（为了完整起见）基于 and

的优秀答案的混合清理解决方案

使用圆滑 https://ericniebler.github.io/meta/index.html
使用 gcc 9.2.1
无法使用 clang 9.0.1，因为缺少 "template non-type classes" 功能（我认为）

Live on Wandbox

#include <type_traits>
#include <tuple>
#include "meta.hpp"

namespace details
{
    template<auto F>
    struct lambdaQuote
    {
        template<typename... T>
        using invoke = decltype(F(T{}...));
    };
}

template<auto& tuple, auto pred, bool doForward = false>
constexpr auto sort()
{
    using namespace meta;
    using namespace details;
    using Tuple = std::remove_cvref_t<decltype(tuple)>;

    using Pred = lambdaQuote<
        [](auto I, auto J) {
        return bool_<pred(std::get<I>(tuple), std::get<J>(tuple))>{};
    }>;

    using Indices       = as_list<make_index_sequence<std::tuple_size_v<Tuple>>>;
    using SortedIndices = meta::sort<Indices, Pred>;
    auto createTuple    = []<typename... Ts>(list<Ts...>)
    {
        if constexpr(doForward)
        {
            return std::forward_as_tuple(std::get<Ts::value>(tuple)...);
        }
        else
        {
            return std::make_tuple(std::get<Ts::value>(tuple)...);
        }
    };

    return createTuple(SortedIndices{});
}

template<typename T>
struct A
{
    constexpr A(T t) : val(t){};
    T val;
private:
    constexpr A() = default;
};


int main()
{
    static constexpr auto t = std::make_tuple(A{10.0},A{9},A{8.0f},A{7.0},A{6.0},A{5});
    constexpr auto p        = [](auto&& a, auto&& b) { return a.val < b.val; };
    constexpr auto s        = sort<t, p>();

    constexpr auto tRes = std::make_tuple(A{5},A{6.0},A{7.0},A{8.0f},A{9},A{10.0});
    static_assert(std::is_same_v<decltype(s), decltype(tRes)>, "not correct");
    static_assert(std::get<0>(tRes).val == std::get<0>(s).val, "not correct");
}

std::tuple 能否根据其值在 compilte-time/run-time 处排序

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

c++

sorting

constexpr

stdtuple

c++20