You can make use of the standard library's std::sort algorithm (if it is constexpr as it should be in C++20), even if it expects homogeneous types by by wrapping only the indices of the tuple as distinct types in an array of std::variants and sorting on those.
You can then provide any predicate that you want, as long as comparing each pair of types in the tuple is possible with the predicate and it satisfies the usual requirements for comparators to std::sort.
In particular there is a std::less<void> specialization that accepts two arbitrary types for comparison with <, so I use that as default, similar to what std::sort does.
As mentioned by @Barry, you will however need to take the tuple as non-type template argument to access its values inside the function. If you want to access state of the predicate as well inside the sort algorithm, then you will need to pass it as reference non-type template argument as well.
Also note that this will probably take quadratic compilation time in the size of the tuple, because of the number of instantiations and visits for the comparator that will be required. For large tuples you can probably implement your own algorithm that doesn't need quadratically many instantiations using template metaprogramming that will only instantiate the required comparisons, instead.
Alternatively, the number of required instantiations can be reduced by copying the values (or std::refs to the values) contained in the tuple into the std::variants instead, after removing duplicate types, reducing the number of required instantiations and visits to quadratically many in the number of distinct types. See history of this answer for an incomplete implementation that did not actually deduplicate types and was therefore probably still quadratic in size of the tuple.
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>{});
}
Tests (slightly corrected from the question and including some duplicate types):
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)>);
Tested on GCC trunk in this godbolt. It doesn't work on Clang trunk with libstdc++ or libc++. From the error message produced, I assume it is because it doesn't implement constexpr std::sort yet with either.
