11

私はこのような構造を持っています:

template<typename... Ts>
struct List {}

typedef List<char,List<int,float,List<int,unsigned char>>,List<unsigned,short>> MyList;

そして、基本的にそれを1つのリストにフラットにしたいと考えています。最善の方法は何ですか？十分に長くいじれば、再帰で何かを作ることができると思いますが、もっと良い方法があるはずだと何かが教えてくれます。

上記のツリーの結果として必要なものは、次のようになります。

typedef List<char,int,float,int,unsigned char,unsigned,short> FlattenedList;

これが私の最初の試みです：

template<typename... Ts>
struct List{};

template<typename... Ts>
struct FlattenTree{
    typedef List<Ts...> Type;
};
template<typename... Ts, typename... Us, typename... Vs>
struct FlattenTree<Ts...,List<Us...>,Vs...>{
    typedef typename FlattenTree<Ts..., Us..., Vs...>::Type Type;
};

しかし、次のエラーが発生します。error C3515: if an argument for a class template partial specialization is a pack expansion it shall be the last argument

rici はここでMSVC2013 が不満を言っていることを指摘したので、ここにはコンパイラのバグはありません:

§ 14.8.2.5 (型からのテンプレート引数の推定) パラグラフ 5 には、テンプレート引数を推定できないコンテキストがリストされています。関連するものは、リストの最後のものです。

— A function parameter pack that does not occur at the end of the parameter-declaration-clause.

アップデート：

一番最後にダミーパラメーターを入れて、最初の引数を最後に移動し続けるか、リストの場合は前に展開し、最初のパラメーターがダミーであることに特化して再帰を停止できると思います。ただし、リストをフラット化するだけでも、コンパイラにとっては大変な作業のようです。

namespace Detail{
    struct MyMagicType {};
    template<typename T, typename... Ts>
    struct FlattenTree{
        typedef typename FlattenTree<Ts..., T>::Type Type;
    };
    template<typename... Ts>
    struct FlattenTree<MyMagicType,Ts...>{      //termination case
        typedef List<Ts...> Type;
    };
    template<typename... Ts, typename... Us>
    struct FlattenTree<List<Ts...>, Us...>{
        typedef typename FlattenTree<Ts..., Us...>::Type Type;
    };              //expand Ts to front because they may hold more nested Lists
}

template<typename... Ts>
struct FlattenTree{
    typedef typename Detail::FlattenTree<Ts...,Detail::MyMagicType>::Type Type;
};

これは MSVC2013 で動作しますが、ダミーの型が必要であり、コンパイラに多くの負荷がかかるため、これが最善の方法だとは思いません。500 以上の要素を含むリストで使用したい。

4

3 に答える 3

0

一般的な「Meta-Tree-Traversal」を使用した私のソリューションは次のとおりです。

#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 leaf 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
}
于 2015-04-04T18:34:54.883 に答える