那些遇到过的问题

Traversing a tree during compile time, with visiting actions

pre*_*eys 30 c++ templates c++11

To make a preorder traversal of a nested pack of types (i.e. a tree of types), and then carry out an action at each leaf, I've worked out an algorithm already (and tested to work correctly):

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...>> {};
Run Code Online (Sandbox Code Playgroud)

My "leaf action" here is simply storing the type of each leaf visited, as my test shows:

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
}
Run Code Online (Sandbox Code Playgroud)

But my problem now is: What if there is to be an action carried out at each non-leaf, and such "non-leaf action" is carried out AFTER the children are visited? How to remember the non-leaf?

Here is an example task which would require this: Referring to my Visit program above, after each child of a node is visited (but not before), append the first type in the non-leaf pack to the P<Visited...> pack. If a leaf is visited, append its type to the P<Visited...> pack, as in the original program. Due to this specific order, Visit<Pack<Types...>>::type will have a specific order as well. Solve this, and the original question is solved.

Here is the simple solution if that non-leaf action is carried out BEFORE visiting its children:

#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
}
Run Code Online (Sandbox Code Playgroud)

Now what is the solution if that non-leaf action is to be carried out AFTER visiting the children? In this case, the output would be different, namely:

Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, int, char, char, double, long>
Run Code Online (Sandbox Code Playgroud)

想法: 从First获得最后一个孩子.存储最后一个孩子和第一个某处(但在哪里???).当访问最后一个孩子时,在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>> {};
Run Code Online (Sandbox Code Playgroud)

现在最困难的部分就是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
}
Run Code Online (Sandbox Code Playgroud)

如果你想知道,这是我的动机:考虑这个循环(显然在运行时执行):

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.
}
Run Code Online (Sandbox Code Playgroud)

这里有2个"非叶子动作".visited[v] = true;在访问孩子之前进行,所以这没有问题(只是改变继承),但真正的问题是stack.push(v);,在孩子被访问后进行.最后,我想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...>>
Run Code Online (Sandbox Code Playgroud)

并不唯一地标识最后一个子节点的位置,因为树中可能存在其他类型的叶子First.这表明:

  1. 必须使用每个节点的唯一序列号重新设计原始树(最后的手段,因为这会强制客户端代码更改),或者

  2. 该算法应在树遍历时为树中的每个节点分配唯一的序列ID.第二个想法是理想的,因为原始树不需要重新设计,但它更具挑战性.例如,已知存在但尚未在遍历中访问过的孩子的ID号是多少？看起来分支号码必须用于ID每个节点.

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

It uses the pattern being worked out in this thread, and I'm lucky that every vertex has unique node values. But I still want to know the general solution in the event that the nodes of the tree do not have unique values, without adjoining unique serial IDs to each node of the original tree (which seriously uglifies the design of the original tree), i.e. carry out solution #2 described above, or something like that).

Update (after some days of thought). Now working on a new idea, which may inspire anyone who is interested in this problem:

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...>> {};
Run Code Online (Sandbox Code Playgroud)

It doesn't give the correct results yet though, but if it works in the end, it seems much more elegant than the ideas I've sketched already.

pre*_*eys 8

完成!

#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
}
Run Code Online (Sandbox Code Playgroud)

我来到这里的思维练习很多.当然欢迎其他解决方案(任何提供替代解决方案的人仍可获得赏金).

这个解决方案也让我意识到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
}
Run Code Online (Sandbox Code Playgroud)

在访问节点的子节点之前访问节点上的操作:

#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
}
Run Code Online (Sandbox Code Playgroud)

最后,我们将这三个行动结合在一起完成本章.

在访问孩子之前在叶子,节点处以及在访问孩子之后的节点处的动作:

#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
}
Run Code Online (Sandbox Code Playgroud)

最后,我想分享我的解决方案,以解决使用这种新方法得到编译时拓扑类型的有向无环图的原始问题(这是首先激发所有这一切的原因):http: //ideone.com/U1bbRM

归档时间：

查看次数：

1144 次

最近记录：

10 年，6 月 前
相关归档
与C语言相比,C++的局限性是什么？ 116
C++编译错误？ 74
Web-Developer的项目模板目录 16
为什么用g ++编译该代码会花费这么长时间？ 11
C++ 11访问具有合格名称的无范围枚举器 10
tr1 :: function可以吞下返回值吗？ 9
Move Semantics C++ 11(Bjarne Stroustrup book,pg75) 7
嵌套模板与移位运算符 6
将C++ 11枚举类作为模板传递,同时自动推断其类型 6
功能专门用于模板 5
难疑归档
不同浏览器中URL的最大长度是多少？ 4676
如何在Ruby中编写switch语句 2026
Python中的静态方法？ 1639
插入...值(SELECT ... FROM ...) 1340
除了XHTML自包含标记之外,RegEx匹配开放标记 1323
如何获取Android应用程序的构建版本号？ 1198
如何通过对象中的属性对List <T>进行排序 1146
为特定提交生成git补丁 1144
什么是首选的Bash shebang？ 1051
#Hibernate hbm2ddl.auto配置的可能值是什么,它们做了什么 1046