在編譯時對整型常量的元組進行排序

Question

以下所有內容T爲std::integral_constant<int, X>。

如何設計一個結構和一個函數，將一個整型常量列表作爲輸入，並返回一個常量已被排序的std::tuple<std::integral_constant<int, X>...>？

template <class... T> 
struct ordered_tuple; 

template <class... T> 
constexpr typename ordered_tuple<T...>::type make_ordered_tuple(T&&...); 

的用途是：

std::integral_constant<int, 5> i5; 
std::integral_constant<int, 4> i4; 
std::integral_constant<int, 9> i9; 
std::integral_constant<int, 1> i1; 
auto tuple = make_ordered_tuple(i5, i4, i9, i1); 

Answer 1

下面是做到這一點的方法之一。我實現了合併排序，這非常適合函數式編程。它不到200行。它大部分基於我在an earlier answer中使用的元函數。這是基於許多其他人在SO問題中使用過的東西，與類型列表等基本操作有關...

一種改進方法是減少所需的模板遞歸深度，目前它是O(n)。我想這可能是O(log n)，但我並不確定，這取決於你是否可以找到一種方法來重寫merge元函數。 （類似於Yakk在另一個問題中指出的那樣）。

#include <type_traits> 

template <class... T> 
struct TypeList { 
    static constexpr const std::size_t size = sizeof...(T); 
}; 

/*** 
* Concat metafunction 
*/ 

template <typename A, typename B> 
struct Concat; 

template <class... As, class... Bs> 
struct Concat<TypeList<As...>, TypeList<Bs...>> { 
    typedef TypeList<As..., Bs...> type; 
}; 

template <typename A, typename B> 
using Concat_t = typename Concat<A, B>::type; 

/*** 
* Split metafunction 
*/ 

template <int i, typename TL> 
struct Split; 

template <int k, typename... TL> 
struct Split<k, TypeList<TL...>> { 
private: 
    typedef Split<k/2, TypeList<TL...>> FirstSplit; 
    typedef Split<k - k/2, typename FirstSplit::R> SecondSplit; 

public: 
    typedef Concat_t<typename FirstSplit::L, typename SecondSplit::L> L; 
    typedef typename SecondSplit::R R; 
}; 

template <typename T, typename... TL> 
struct Split<0, TypeList<T, TL...>> { 
    typedef TypeList<> L; 
    typedef TypeList<T, TL...> R; 
}; 

template <typename T, typename... TL> 
struct Split<1, TypeList<T, TL...>> { 
    typedef TypeList<T> L; 
    typedef TypeList<TL...> R; 
}; 

template <int k> 
struct Split<k, TypeList<>> { 
    typedef TypeList<> L; 
    typedef TypeList<> R; 
}; 

// Metafunction Subdivide: Split a typelist into two roughly equal typelists 
template <typename TL> 
struct Subdivide : Split<TL::size/2, TL> {}; 

/*** 
* Ordered tuple 
*/ 

template <int X> 
using int_t = std::integral_constant<int, X>; 

template <class... T> 
struct Ordered_List : TypeList<T...> {}; 

template <class... As, class... Bs> 
struct Concat<Ordered_List<As...>, Ordered_List<Bs...>> { 
    typedef Ordered_List<As..., Bs...> type; 
}; 

/*** 
* Merge metafunction 
*/ 

template <typename A, typename B> 
struct Merge; 

template <typename B> 
struct Merge<Ordered_List<>, B> { 
    typedef B type; 
}; 

template <int a, class... As> 
struct Merge<Ordered_List<int_t<a>, As...>, Ordered_List<>> { 
    typedef Ordered_List<int_t<a>, As...> type; 
}; 

template <int a, class... As, int b, class... Bs> 
struct Merge<Ordered_List<int_t<a>, As...>, Ordered_List<int_t<b>, Bs...>> { 
    typedef Ordered_List<int_t<a>, As...> A; 
    typedef Ordered_List<int_t<b>, Bs...> B; 

    typedef typename std::conditional<a <= b, 
            Concat_t<Ordered_List<int_t<a>>, typename Merge<Ordered_List<As...>, B>::type>, 
            Concat_t<Ordered_List<int_t<b>>, typename Merge<A, Ordered_List<Bs...>>::type> 
            >::type type; 
}; 

template <typename A, typename B> 
using Merge_t = typename Merge<A, B>::type; 

/*** 
* Mergesort metafunction 
*/ 

template <typename TL> 
struct MergeSort; 

// Boilerplate base-cases 
template <> 
struct MergeSort<TypeList<>> { 
    typedef Ordered_List<> type; 
}; 

template <int X> 
struct MergeSort<TypeList<int_t<X>>> { 
    typedef Ordered_List<int_t<X>> type; 
}; 

// Inductive step 
template <int X, class... Xs> 
struct MergeSort<TypeList<int_t<X>, Xs...>> { 
    typedef TypeList<int_t<X>, Xs...> input_t; 
    typedef Subdivide<input_t> subdivide_t; 
    typedef typename MergeSort<typename subdivide_t::L>::type left_sort_t; 
    typedef typename MergeSort<typename subdivide_t::R>::type right_sort_t; 
    typedef Merge_t<left_sort_t, right_sort_t> type; 
}; 

template <typename T> 
using MergeSort_t = typename MergeSort<T>::type; 

/*** 
* Make ordered tuple impl 
*/ 

#include <tuple> 

template <typename T> 
struct MakeStdTuple; 

template <class... Ts> 
struct MakeStdTuple<Ordered_List<Ts...>> { 
    typedef std::tuple<Ts...> type; 
}; 

template <typename T> 
using MakeStdTuple_t = typename MakeStdTuple<T>::type; 

template <class... T> 
constexpr MakeStdTuple_t<MergeSort_t<TypeList<T...>>> make_ordered_tuple(T&&...) { 
    return {}; 
} 

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>, 
          MergeSort_t<TypeList<int_t<1>, int_t<2>, int_t<3>>>>::value, "Failed a unit test"); 

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>, 
          MergeSort_t<TypeList<int_t<2>, int_t<1>, int_t<3>>>>::value, "Failed a unit test"); 

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>, 
          MergeSort_t<TypeList<int_t<3>, int_t<2>, int_t<1>>>>::value, "Failed a unit test"); 

int main() {}