c++ - 在编译时遍历一棵树,使用访问操作

标签 c++ templates c++11

为了对嵌套的类型包(即类型树)进行预序遍历,然后在每个叶子上执行一个操作,我已经制定了一个算法(并经过测试可以正常工作):

template <typename T>
struct HasChildren : std::false_type {};

template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};

template <typename, typename> struct Merge;

template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
    using type = P1<Ts..., Us...>;
};

template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;

template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
    VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};

template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every leaf in the tree visited.
    using result = P2<Visited...>;
};

template <typename, typename> struct LeafAction;

// As a simple example, the leaf action is appending its type to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};  // Having visited First, now visit Rest...

// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> : Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited...>> {};

// Here First has no children, so the "leaf action" is carried out. 
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};

我的“叶子 Action ”只是存储访问的每个叶子的类型,如我的测试所示:
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};

int main() {
    std::cout << std::boolalpha << std::is_same<
        Visit<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>, Pack<>>::type,
        Pack<int, Object, double, bool, char, int, double, char, char, long, short, int, Object, char, double, long>
    >::value << std::endl;  // true
}

但是我现在的问题是:如果在每个非叶子上执行一个 Action ,并且在访问 child 之后执行这种“非叶子 Action ”怎么办?如何记住非叶子?

这是一个需要这个的示例任务:
引用我的 Visit上面的程序,在访问节点的每个子节点之后(但不是之前),将非叶包中的第一个类型附加到 P<Visited...>盒。如果访问了叶子,则将其类型附加到 P<Visited...>打包,就像在原始程序中一样。由于此特定订单,Visit<Pack<Types...>>::type也会有特定的顺序。解决这个问题,原来的问题就解决了。

如果在访问其 child 之前执行非叶操作,则这是简单的解决方案:
#include <iostream>
#include <type_traits>
#include <typeinfo>

template <typename T>
struct HasChildren : std::false_type {};

template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};

template <typename, typename> struct Merge;

template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
    using type = P1<Ts..., Us...>;
};

template <typename> struct FirstType;

template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
    using type = First;
};

template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;

template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
    VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};

template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every leaf in the tree visited.
    using result = P2<Visited...>;
};

template <typename, typename> struct LeafAction;

template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};

template <typename, typename> struct NonLeafActionPrevisit;

template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> :
    Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited..., typename FirstType<First>::type>> {};

// Here First has children, so visit its children, after which visit Rest..., but before doing so carry out the non-leaf action in the inherited struct.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
    NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> {};  // *** The simple solution here.

// Here First has no children, so the "leaf action" is carried out.  In this case, it is appended to P<Visited...> as a simple example. 
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};

template <typename> struct VisitTree;

template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};

// ---------------------------- Testing ----------------------------
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};

int main() {
    std::cout << std::boolalpha << std::is_same<
        VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
        Pack<int, int, Object, double, bool, char, char, int, int, double, char, char, char, char, long, short, int, Object, char, double, long>
    >::value << std::endl;  // true
}

现在如果在探望 child 后进行非叶行动,有什么解决方案?
在这种情况下,输出会有所不同,即:
Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, int, char, char, double, long>

想法:从 First 获取最后一个 child 。将最后一个 child 和第一个存储在某个地方(但在哪里???)。当访问最后一个 child 时,对 First 执行非叶操作。就像是:
template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;

template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>> :
    VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};

template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... ChildAndParent, typename... Visited>
struct Visit<P1<>, P2<ChildAndParent...>, P3<Visited...>> {  // End of recursion.  Every leaf in the tree visited.
    using type = P3<Visited...>;
};

// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, true> :
    Visit<typename Merge<First, P2<Rest...>>::type, P2<ChildAndParent...,
    typename LastType<First>::type, First>, P3<Visited...>> {};
// Idea:  Get the last child from First.  Store that last child and First here.  When that last child is visited, carry out the non-leaf action on First.

// Here First has no children, so the "leaf action" is carried out.  In this case, it is appended to P<Visited...> as a simple example. 
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, false> :
    Visit<P1<Rest...>, P2<ChildAndParent...>, P3<Visited..., First>> {};

现在困难的部分是利用 P2<ChildAndParent...>正确地,假设这个想法会奏效。

更新(12 小时后):嗯,我尽力了。这是我想出的,它可以编译,但它使我无法理解为什么我仍然得到错误的结果。也许有人可以对此有所了解。
#include <iostream>
#include <type_traits>
#include <typeinfo>

template <typename T>
struct HasChildren : std::false_type {};

template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};

template <typename, typename> struct Merge;

template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
    using type = P1<Ts..., Us...>;
};

template <typename> struct FirstType;

template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
    using type = First;
};

template <typename> struct LastType;

template <template <typename...> class P, typename Last>
struct LastType<P<Last>> {
    using type = Last;
};

template <template <typename...> class P, typename First, typename... Rest>
struct LastType<P<First, Rest...>> : LastType<P<Rest...>> {};

template <typename, typename...> struct ExistsInPack;

template <typename T, typename First, typename... Rest>
struct ExistsInPack<T, First, Rest...> : ExistsInPack<T, Rest...> {};

template <typename T, typename... Rest>
struct ExistsInPack<T, T, Rest...> : std::true_type {};

template <typename T>
struct ExistsInPack<T> : std::false_type {};

template <typename Child, typename First, typename Second, typename... Rest>
struct GetParent : GetParent<Child, Rest...> {};

template <typename Child, typename Parent, typename... Rest>
struct GetParent<Child, Child, Parent, Rest...> {
    using type = Parent;
};

template <typename, typename, typename> struct RemoveChildAndParentHelper;

template <template <typename...> class P, typename Child, typename First, typename Second, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<First, Second, Rest...>, P<Accumulated...>> : RemoveChildAndParentHelper<Child, P<Rest...>, P<Accumulated..., First, Second>> {};

template <template <typename...> class P, typename Child, typename Parent, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<Child, Parent, Rest...>, P<Accumulated...>> {
    using type = P<Accumulated..., Rest...>;
};

template <template <typename...> class P, typename Child, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<>, P<Accumulated...>> {
    using type = P<Accumulated...>;
};

template <typename, typename> struct RemoveChildAndParent;

template <template <typename...> class P, typename Child, typename... LastChildAndParent>
struct RemoveChildAndParent<Child, P<LastChildAndParent...>> : RemoveChildAndParentHelper<Child, P<LastChildAndParent...>, P<>> {};

template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;
template <typename, typename, typename, bool> struct CheckIfLastChild;

template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>> :
    VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};

template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<>, P2<LastChildAndParent...>, P3<Visited...>> {  // End of recursion.  Every leaf in the tree visited.
    using result = P3<Visited...>;
    using storage = P2<LastChildAndParent...>;  // just for checking (remove later)
};

// Here First has children, so visit its children, after which visit Rest...
// Get the last child from First.  Store that last child and First here.  When that last child is visited later on, carry out the non-leaf action on First.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
    Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>> {};

// Here First has no children, so the "leaf action" is carried out.  In this case, it is appended to P<Visited...>.
// Check if First is a last child.  If so the non-leaf action of its parent is to be carried out immediately after First's action is carried out.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> :
    CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, ExistsInPack<First, LastChildAndParent...>::value> {};

// First is a last child (and is a leaf), so append First to P3<Visited...> (the leaf action), and then append the first type of its parent to P3<Visited...> after it (the non-leaf action).
// First and its parent must be removed from P2<LastChildAndParent...> at this point.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
    Visit<P1<Rest...>, typename RemoveChildAndParent<First, P2<LastChildAndParent...>>::type, P3<Visited..., First, typename FirstType<typename GetParent<First, LastChildAndParent...>::type>::type>> {};

// First is not a last child (but is a leaf), so append First to P3<Visited...> (the leaf action) and proceed with visiting the next type in P1<Rest...>.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> : Visit<P1<Rest...>, P2<LastChildAndParent...>, P3<Visited..., First>> {};

template <typename> struct VisitTree;

template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>, P<>> {};

// ---------------------------- Testing ----------------------------
template <typename...> struct Pack;

template <typename Last>
struct Pack<Last> {
    static void print() {std::cout << typeid(Last).name() << std::endl;}
};

template <typename First, typename... Rest>
struct Pack<First, Rest...> {
    static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
};

template <>
struct Pack<> {
    static void print() {std::cout << "empty" << std::endl;}
};

template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};

int main() {
    using Tree = VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>;
    Tree::result::print();  // int Object double int bool char int double char char int char long short int Object char char double long
    Tree::storage::print();  // empty
    std::cout << std::boolalpha << std::is_same<
        Tree::result,
        Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, char, char, int, char, double, long>
    >::value << std::endl;  // false
}

如果您想知道,这是我的动机:
考虑这个循环(显然是在运行时执行的):
template <int N>
void Graph<N>::topologicalSortHelper (int v, std::array<bool, N>& visited, std::stack<int>& stack) {
    visited[v] = true;  // Mark the current node as visited.
    for (int x : adjacentVertices[v])  // Repeat for all the vertices adjacent to this vertex.
        if (!visited[x])
            topologicalSortHelper (x, visited, stack);
    stack.push(v);  // Push current vertex to 'stack' which stores the result.
}

这里有 2 个“非叶操作”。 visited[v] = true;是在访问 child 之前进行的,所以没有问题(只需在继承中进行更改),但真正的问题是stack.push(v); ,这是在访问 child 之后进行的。归根结底,我要Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>::topological_sort成为编译时结果 index_sequence<5,4,2,3,1,0> ,其中 6 是顶点数,而 5,2, 5,0, 4,0, 4,1, 2,3, 3,1描述图的边。那是我正在做的真正项目,我快完成了。解决上面的通用问题,我就会解决这个问题。

更新:我在我的逻辑中发现了错误。线路:
Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>>

不唯一标识最后一个 child 在哪里,因为可能有 其他 树中的叶子类型为 First .这表明:
  • 必须使用每个节点的唯一序列号重新设计原始树(最后的手段,因为这会强制更改客户端代码),或者
  • 该算法应在遍历树中的每个节点时为其分配唯一的序列 ID。这第二个想法是理想的,因为不需要重新设计原始树,但它更具挑战性。例如,已知存在但尚未在遍历中访问过的 child 的 ID 号是多少?看起来分支编号必须用于识别每个节点。

  • 顺便说一句,我设法解决了图形的编译时拓扑排序的原始问题:
    http://ideone.com/9DKh4s

    它使用在这个线程中制定的模式,我很幸运每个顶点都有唯一的节点值。但是我还是想知道在树的节点没有唯一值的情况下的通用解决方案,而不是在原始树的每个节点上邻接唯一的序列ID(这严重丑化了原始树的设计),即携带解决上面描述的解决方案#2,或类似的东西)。

    更新 (经过几天的思考)。现在正在研究一个新想法,这可能会激发对这个问题感兴趣的任何人:
    template <typename, typename, typename> struct NonLeafActionPostvisit;
    
    // As a simple example, the postvisit non-leaf action is appending the first type of the pack to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename ChildrenVisits, typename First, typename... Rest, typename... Visited>
    struct NonLeafActionPostvisit<ChildrenVisits, P1<First, Rest...>, P2<Visited...>> :
        Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};
    
    // Postvisit:
    // Here First has children, so visit its children, after which carry out the postvisit non-leaf action, and then visit Rest...
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
        NonLeafActionPostvisit<Visit<First, P2<Visited...>>, P1<First, Rest...>, P2<Visited...>> {};
    
    // Here First has no children, so the "leaf action" is carried out.  In this case, it is appended to P<Visited...> as a simple example. 
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> :
        LeafAction<P1<First, Rest...>, P2<Visited...>> {};
    

    虽然它还没有给出正确的结果,但如果它最终有效,它似乎比我已经勾勒的想法优雅得多。

    最佳答案

    完毕!

    #include <iostream>
    #include <type_traits>
    #include <typeinfo>
    
    template <typename T>
    struct HasChildren : std::false_type {};
    
    template <template <typename...> class P, typename... Types>
    struct HasChildren<P<Types...>> : std::true_type {};
    
    template <typename> struct FirstType;
    
    template <template <typename...> class P, typename First, typename... Rest>
    struct FirstType<P<First, Rest...>> {
        using type = First;
    };
    
    template <typename, typename> struct Visit;
    template <typename, typename, bool> struct VisitHelper;
    template <typename, typename> struct LeafAction;
    template <typename, typename> struct NonLeafActionPostVisit;
    
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct Visit<P1<First, Rest...>, P2<Visited...>> :
        VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
    
    template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
    struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every node in the tree visited.
        using result = P2<Visited...>;
    };
    
    // Here First has children, so visit its children now, then carry out the "post-visit non-leaf action", and then visit Rest...
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
        NonLeafActionPostVisit<P1<First, Rest...>, typename Visit<First, P2<Visited...>>::result> {};
    // *** The key!  Pass typename Visit<First, P2<Visited...>>::result into NonLeafActionPostVisit.
    
    // Here First has no children, so the "leaf action" is carried out.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
    
    // As a simple example, the leaf action shall simply be appending its type to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};
    
    // As a simple example, the post-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct NonLeafActionPostVisit<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};
    
    template <typename> struct VisitTree;
    
    template <template <typename...> class P, typename... Types>
    struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
    
    // ---------------------------- Testing ----------------------------
    template <typename...> struct Pack;
    
    template <typename Last>
    struct Pack<Last> {
        static void print() {std::cout << typeid(Last).name() << std::endl;}
    };
    
    template <typename First, typename... Rest>
    struct Pack<First, Rest...> {
        static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
    };
    
    template <typename...> struct Group;
    template <typename...> struct Wrap;
    struct Object {};
    
    int main() {
        VisitTree<
            Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>
        >::result::print();  // i Object d i b c i d c c l s c i Object c c i d c l
    
        std::cout << std::boolalpha << std::is_same<
            VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
            Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, char, char, int, double, char, long>
        >::value << std::endl;  // true
    }
    

    我在这里进行了大量的思考练习。当然也欢迎其他解决方案(任何提供替代解决方案的人仍然可以获得赏金)。

    这个解决方案也让我意识到 Merge甚至不再需要。所以我现在更好地修改我对其他情况的解决方案:

    仅在叶子处访问操作:
    #include <iostream>
    #include <type_traits>
    #include <typeinfo>
    
    template <typename T>
    struct HasChildren : std::false_type {};
    
    template <template <typename...> class P, typename... Types>
    struct HasChildren<P<Types...>> : std::true_type {};
    
    template <typename, typename> struct Visit;
    template <typename, typename, bool> struct VisitHelper;
    template <typename, typename> struct LeafAction;
    
    // Here the role of P2<Visited...> is simply to allow LeafAction to carry out its function.  It is not native to the tree structure itself.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct Visit<P1<First, Rest...>, P2<Visited...>> :
        VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
    
    template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
    struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every node in the tree visited.
        using result = P2<Visited...>;
    };
    
    // Here First has children, so visit its children, after which visit Rest...
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> : Visit<P1<Rest...>, typename Visit<First, P2<Visited...>>::result> {};  // Visit the "subtree" First, and then after that visit Rest...  Need to use ::result so that when visiting Rest..., the latest value of the P2<Visited...> pack is used.
    
    // Here First has no children, so the "leaf action" is carried out. 
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
    
    // As a simple example, the leaf action shall simply be appending its type to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};  // Having visited First, now visit Rest...
    
    template <typename> struct VisitTree;
    
    template <template <typename...> class P, typename... Types>
    struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
    
    // ---------------------------- Testing ----------------------------
    template <typename...> struct Pack;
    
    template <typename Last>
    struct Pack<Last> {
        static void print() {std::cout << typeid(Last).name() << std::endl;}
    };
    
    template <typename First, typename... Rest>
    struct Pack<First, Rest...> {
        static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
    };
    
    template <typename...> struct Group;
    template <typename...> struct Wrap;
    struct Object {};
    
    int main() {
        VisitTree<
            Pack<Pack<int, Object, double>, bool, Pack<char, Pack<int, double, Pack<char, Pack<char, long, short>, int, Object>, char>, double>, long>
        >::result::print();  // int Object double bool char int double char char long short int Object char double long
    
        std::cout << std::boolalpha << std::is_same<
            VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
            Pack<int, Object, double, bool, char, int, double, char, char, long, short, int, Object, char, double, long>
        >::value << std::endl;  // true
    }
    

    在访问节点的子节点之前访问节点上的操作:
    #include <iostream>
    #include <type_traits>
    #include <typeinfo>
    
    template <typename T>
    struct HasChildren : std::false_type {};
    
    template <template <typename...> class P, typename... Types>
    struct HasChildren<P<Types...>> : std::true_type {};
    
    template <typename> struct FirstType;
    
    template <template <typename...> class P, typename First, typename... Rest>
    struct FirstType<P<First, Rest...>> {
        using type = First;
    };
    
    template <typename, typename> struct Visit;
    template <typename, typename, bool> struct VisitHelper;
    template <typename, typename> struct LeafAction;
    template <typename, typename> struct NonLeafActionPreVisit;
    
    // Here the role of P2<Visited...> is simply to allow LeafAction to carry out its function.  It is not native to the tree structure itself.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct Visit<P1<First, Rest...>, P2<Visited...>> :
        VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
    
    template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
    struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every node in the tree visited.
        using result = P2<Visited...>;
    };
    
    // Here First has children, so carry out the "non-leaf pre-visit action", then visit the children, and then visit Rest...
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> : NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> {};
    
    // Here First has no children, so the "leaf action" is carried out.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
    
    // As a simple example, the leaf action shall simply be appending its type to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};
    
    // As a simple example, the non-leaf pre-visit action shall simply be appending the first type of the pack to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> :
        Visit<P1<Rest...>, typename Visit<First, P2<Visited..., typename FirstType<First>::type>>::result> {};  // typename FirstType<First>::type is appended to P2<Visited...> (the non-leaf pre-visit action), then Visit<First, P2<Visited..., typename FirstType<First>::type>> is carried out (which is visiting all the children), and then Rest... is visited using ::result of that visiting of the children. 
    
    template <typename> struct VisitTree;
    
    template <template <typename...> class P, typename... Types>
    struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
    
    // ---------------------------- Testing ----------------------------
    template <typename...> struct Pack;
    template <typename...> struct Group;
    template <typename...> struct Wrap;
    struct Object;
    
    int main() {
        std::cout << std::boolalpha << std::is_same<
            VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
            Pack<int, int, Object, double, bool, char, char, int, int, double, char, char, char, char, long, short, int, Object, char, double, long>
        >::value << std::endl;  // true
    }
    

    最后,我们以所有三个 Action 一起结束本章。

    在叶子节点、访问子节点之前的节点和访问子节点之后的节点的 Action :
    #include <iostream>
    #include <type_traits>
    #include <typeinfo>
    
    template <typename T>
    struct HasChildren : std::false_type {};
    
    template <template <typename...> class P, typename... Types>
    struct HasChildren<P<Types...>> : std::true_type {};
    
    template <typename> struct FirstType;
    
    template <template <typename...> class P, typename First, typename... Rest>
    struct FirstType<P<First, Rest...>> {
        using type = First;
    };
    
    template <typename, typename> struct Visit;
    template <typename, typename, bool> struct VisitHelper;
    template <typename, typename> struct LeafAction;
    template <typename, typename> struct NonLeafActionPreVisit;
    template <typename, typename> struct NonLeafActionPostVisit;
    
    // Here the role of P2<Visited...> is simply to allow LeafAction, NonLeafActionPreVisit, and NonLeafActionPostVisit to carry out their functions.  It is not native to the tree structure itself.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct Visit<P1<First, Rest...>, P2<Visited...>> :
        VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
    
    template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
    struct Visit<P1<>, P2<Visited...>> {  // End of recursion.  Every node in the tree visited.
        using result = P2<Visited...>;
    };
    
    // Here First has children, so carry out the pre-visit non-leaf action, then visit its children, then carry out the post-visit non-leaf action, and then visit Rest...
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
        NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> {};
    
    // Here First has no children, so the "leaf action" is carried out.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
    
    // As a simple example, the leaf action shall simply be appending its type to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};
    
    // As a simple example, the pre-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> :
        NonLeafActionPostVisit<P1<First, Rest...>, typename Visit<First, P2<Visited..., typename FirstType<First>::type>>::result> {};
    
    // As a simple example, the post-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
    template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
    struct NonLeafActionPostVisit<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};
    
    template <typename> struct VisitTree;
    
    template <template <typename...> class P, typename... Types>
    struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
    
    // ---------------------------- Testing ----------------------------
    template <typename...> struct Pack;
    
    template <typename Last>
    struct Pack<Last> {
        static void print() {std::cout << typeid(Last).name() << std::endl;}
    };
    
    template <typename First, typename... Rest>
    struct Pack<First, Rest...> {
        static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
    };
    
    template <typename...> struct Group {};
    template <typename...> struct Wrap {};
    struct Object {};
    
    int main() {
        VisitTree<
            Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>
        >::result::print();  // i i Object d i b c c i i d c c c c l s c i Object c c i d c l
    
        std::cout << std::boolalpha << std::is_same<
            VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
            Pack<int, int, Object, double, int, bool, char, char, int, int, double, char, char, char, char, long, short, char, int, Object, char, char, int, double, char, long>
        >::value << std::endl;  // true
    }
    

    最后,我想分享我对使用这种新方法获得编译时拓扑类型的有向无环图的原始问题的解决方案(这就是所有这些的最初动机):
    http://ideone.com/U1bbRM

    关于c++ - 在编译时遍历一棵树,使用访问操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29452269/

    相关文章:

    c++ - 引用枚举时 C++ 2003 和 C++ 2011 之间代码不兼容的原因

    c++ - 如何在不显式设置、不显式删除和不使用静态函数的情况下使对象指针为 NULL?

    c++ - 编译时生成应在构造函数中创建的非 constexpr 对象的数组

    c++ - 访问 vector 字段的键 - 命名空间中的枚举类或枚举?

    c++ - 我什么时候应该使用模板化参数而不是构造参数?

    c++ - 隐藏 typedef 实现

    c++ - boost::lambda::var 嵌套在 boost::bind 中不等同于 boost::lambda::var 本身

    c++ - 如何使用模板模板参数为该方法不需要通用接口(interface)的 STL 容器实现通用方法

    c++ - SFINAE 在类型和非类型模板参数的情况下工作方式不同

    C++11 中的 Unicode 标识符和源代码?