元组中类型的编译时重排

Question

使用以下示例定义 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, 即我们使用前两个排序来构建更大一代的树的排序，将 "root" 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.

Answer 2

这里是 T.C. 的解决方案推广到 N-ary 树的任何类型的遍历，其中 reorder<std::tuple, 2, 1, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> 是原始问题（二叉树中序遍历）的特例，因为 2 表示二叉树，而 1 表示与第一个 child 递归后的动作。 2 和 1 可以取任何其他值。

#include <type_traits>
#include <utility>
#include <tuple>

// Concatenating std::index_sequences.
template <typename... Packs> struct concat;

template <typename Pack>
struct concat<Pack> {
    using type = Pack;
};

template <std::size_t... Is, std::size_t... Js>
struct concat<std::index_sequence<Is...>, std::index_sequence<Js...>> {
    using type = std::index_sequence<Is..., Js...>;
};

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

// In-order traversal for a complete binary tree whose level-order traversal is 0,1,2, ..., max-1.
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename = void>
struct traversal {
    using type = std::index_sequence<>;  // So that concatenating changes nothing and ends the recursion.
};

// General recursion.
template <std::size_t Count, std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack, bool ActionJustTookPlace = false>
struct concat_traversals_impl : concat_traversals_impl<Count + 1, NumChildren, ActionPoint, Start, Max,
        typename concat<Pack, typename traversal<NumChildren, ActionPoint, NumChildren * Start + Count + 1, Max>::type>::type> {};

//             0
//         /   |   \
//        /    |    \
//       1     2     3
//    /  |  \
//   4   5  6
// Above we see that the three children of node K is 3*K+1, 3*K+2, 3*K+3.  In general, it is N*K+1, N*K+2, ..., N*K+N, where N is the number of children. 

// If Count == ActionPoint (and ActionJustTookPlace == false), then concat the action, which is std::index_sequence<Start> in this case, but then let ActionJustTookPlace == true so that this does not happen infinitely (as Count still remains equal to ActionPoint) on the next template instantiation, and the primary template is used instead.
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<ActionPoint, NumChildren, ActionPoint, Start, Max, Pack, false> : concat_traversals_impl<ActionPoint, NumChildren, ActionPoint, Start, Max,
        typename concat<Pack, std::index_sequence<Start>>::type, true> {};

// End the recursion when Count == NumChildren. 
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<NumChildren, NumChildren, ActionPoint, Start, Max, Pack> {
    using type = Pack;
};

// Special case of when Count == NumChildren and ActionPoint == NumChildren as well (this partial specialization is needed else there will be ambiguity compilng error).
template <std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<ActionPoint, ActionPoint, ActionPoint, Start, Max, Pack, false> : concat<Pack, std::index_sequence<Start>> {};

template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max>
using concat_traversals = typename concat_traversals_impl<0, NumChildren, ActionPoint, Start, Max, std::index_sequence<>>::type;

template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max>  // Recursive call.
struct traversal<NumChildren, ActionPoint, Start, Max, std::enable_if_t<(Start < Max)>> {
    using type = concat_traversals<NumChildren, ActionPoint, Start, Max>;
};

// Now the actual reordering.
template <typename Pack, typename Sequence> struct reorder_helper;

template <template <typename...> class P, typename... Ts, std::size_t... Is>
struct reorder_helper<P<Ts...>, std::index_sequence<Is...>> {
    using type = P<std::tuple_element_t<Is, std::tuple<Ts...>>...>;
};

template <template <typename...> class P, std::size_t NumChildren, std::size_t ActionPoint, typename... Ts>
using reorder = typename reorder_helper<P<Ts...>, typename traversal<NumChildren, ActionPoint, 0, sizeof...(Ts)>::type>::type;

// Special syntax for reordering a pack.
template <std::size_t NumChildren, std::size_t ActionPoint, typename Pack> struct reorder_pack;

template <std::size_t NumChildren, std::size_t ActionPoint, template <typename...> class P, typename... Ts>
struct reorder_pack<NumChildren, ActionPoint, P<Ts...>> {
    using type = reorder<P, NumChildren, ActionPoint, Ts...>;
};

// Testing
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{};

int main() {
    static_assert (std::is_same<
        reorder<std::tuple, 2, 1, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 1 means that we do left traversal, then the node action, then right traversal (i.e. inorder traversal).
        std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>
    >::value, "");

    static_assert (std::is_same<
        reorder<std::tuple, 2, 0, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 0 means that we do the node action, then left traversal, and then right traversal (i.e. preorder traversal).
        std::tuple<A,B,D,H,I,E,J,K,C,F,L,M,G,N,O>
    >::value, "");

    static_assert (std::is_same<
        reorder<std::tuple, 2, 2, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 2 means that we do left traversal, then right traversal, then the node action (i.e. postorder traversal).
        std::tuple<H,I,D,J,K,E,B,L,M,F,N,O,G,C,A>
    >::value, "");

    static_assert (std::is_same<    
        reorder_pack<3, 2, std::tuple<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>>::type,  // 3 children per node.  Do first child, second child, then node action, then do third child recursively. 
        std::tuple<N,O,E,F,B,G,H,I,C,J,A,K,L,D,M>
    >::value, "");      
}

元组中类型的编译时重排

Compile-time rearrangement of types in a tuple

c++

tuples

template-meta-programming

variadic-templates

c++11