c++ - 元组中类型的编译时重新排列

Question

定义 typedef template <typename...> struct order;如下例所示:

order<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>::type

是

std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>

因为原始类型是从左到右逐行排列成二叉树的，如下图:

             A
         /       \
        /         \
       B           C
    /    \       /    \
   D      E     F      G
  / \    / \   / \    / \
 H   I  J   K L   M  N   O

某个类型的剩余类型在排序中应位于该类型之前。某个类型的正确类型应在排序中遵循该类型。 所以我们可以看到 H 列在最前面，O 列在最后。结果类型是 std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>如前所述。

如何在编译时构建此排序(对于任何长度的元组，即使最后一行尚未完成)？任何帮助将不胜感激。

我最新的想法是使用递归: D,H,I订购为 H,D,I 。 E,J,K订购为 J,E,K 。然后B,D,E,H,I,J,K订购为 H,D,I, B, J,E,K,也就是说，我们使用前两个排序来构建大一代的树的排序，将“根”B 放在中间。然后我们可以对 A 的右子树执行此操作，然后可以类似地连接示例中的整个树(A 在中间)。类似的东西，但现在弄清楚如何将其转换为代码是问题所在。大致如下(在细化和概括之前):

template <typename... Packs> struct concat;

template <template <typename...> class P, typename... Ts, typename... Us>
struct concat<P<Ts...>, P<Us...>> {
    using type = P<Ts..., Us...>;
};

template <typename Pack1, typename Pack2, typename... Packs>
struct concat<Pack1, Pack2, Packs...> : concat<Pack1, typename concat<Pack2, Packs...>::type> {};

template <typename...> struct order;

template <typename T>
struct order<T> {
    using type = std::tuple<T>;
};

template <typename A, typename B, typename C>
struct order<A,B,C> :
    concat<typename order<B>::type, std::tuple<A>, typename order<C>::type> {};

template <typename A, typename B, typename C, typename D, typename E, typename F, typename G>
struct order<A,B,C,D,E,F,G> :
    concat<typename order<B,D,E>::type, std::tuple<A>, typename order<C,F,G>::type> {};

Answer 1

连接三个 std::index_sequence (概括起来很简单，但我在这里只需要三个):

template<size_t... Seq1, size_t... Seq2, size_t... Seq3>
auto concat3_impl(std::index_sequence<Seq1...>, 
                  std::index_sequence<Seq2...>,
                  std::index_sequence<Seq3...>)
  -> std::index_sequence<Seq1..., Seq2..., Seq3...>;

template<class...Ts>
using concat3 = decltype(concat3_impl(Ts{}...));

完全二叉树的中序遍历，其层序遍历为0, 1, ..., (max - 1):

template<size_t start, size_t max, bool = (start < max) >
struct in_order;

template<size_t start, size_t max>
using in_order_t = typename in_order<start, max>::type;

template<size_t start, size_t max, bool >
struct in_order {
    using type = concat3<in_order_t<2*start + 1, max>, 
                         std::index_sequence<start>,
                         in_order_t<2*start + 2, max>>;
};

template<size_t start, size_t max >
struct in_order<start, max, false> {
    using type = std::index_sequence<>;
};

根据索引列表对元组重新排序:

template<class Tuple, size_t...Is>
auto reorder_by_index_impl(std::index_sequence<Is...>)
    -> std::tuple<std::tuple_element_t<Is, Tuple>...>;

template<class Tuple, class Index>
using reorder_by_index = decltype(reorder_by_index_impl<Tuple>(Index{}));

最后:

template<class Tuple>
using reorder_tuple = reorder_by_index<Tuple, in_order_t<0, std::tuple_size<Tuple>{}>>;

Demo :

struct A{}; struct B{}; struct C{}; struct D{}; struct E{};
struct F{}; struct G{}; struct H{}; struct I{}; struct J{};
struct K{}; struct L{}; struct M{}; struct N{}; struct O{};

using t = reorder_tuple<std::tuple<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>>;
using t = std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>; // OK, same type.