2

前方反復 (再帰を使用) は、私にはかなり明確です。

template<typename... Ts>
struct List{
    typedef List<Ts...> Type;
    enum {
        size = sizeof...(Ts)
    };
};

template<int I>
using IntType = std::integral_constant<int, I>;

namespace Detail{
    template<int I, typename T, typename... Ts>
    struct Find : IntType<-1>{};
    template<int I, typename T, typename U, typename... Ts>
    struct Find<I, T, U, Ts...> : Find<I + 1, T, Ts...>{};
    template<int I, typename T, typename... Ts>
    struct Find<I, T, T, Ts...> : IntType<I>{};
}

template<typename T, typename U>
struct Find;
template<typename T, typename... Ts>
struct Find<T, List<Ts...>> : Detail::Find<0, T, Ts...>{};

最後の項目から開始して逆方向に作業し、最後に出現した項目を最初に見つけたい場合はどうすればよいでしょうか?

私の試み：

namespace Detail{
    template<int I, typename T, typename... Ts>
    struct ReverseFind : IntType<-1>{};
    template<int I, typename T, typename U, typename... Ts>
    struct ReverseFind<I, T, Ts..., U> : ReverseFind<I + 1, T, Ts...>{};
    template<int I, typename T, typename... Ts>
    struct ReverseFind<I, T, Ts..., T> : IntType<I>{};
}
template<typename T, typename U>
struct ReverseFind;
template<typename T, typename... Ts>
struct ReverseFind<T, List<Ts...>> : Detail::ReverseFind<sizeof...(Ts), T, Ts...>{};

これは MSVC2013 で失敗しerror C3515: if an argument for a class template partial specialization is a pack expansion it shall be the last argument、コンパイラは正しいと思いますが、そのようにはできません (間違っている場合は修正してください)。

(再帰を使用して) 特定のインデックスでパラメーターの型を取得する Meta 関数を実装できTypeAtますが、それは線形の複雑さであり、ReverseFind から毎回呼び出すと指数関数的な複雑さになります。

Find のような線形の複雑さで ReverseFind を実装する方法はありますか?

更新: より良い試み:

namespace Detail {
    template<typename T, typename U>
    struct Reverse;
    template<typename... Us>
    struct Reverse<List<>, List<Us...>> : List<Us...>{};
    template<typename T, typename... Ts, typename... Us>
    struct Reverse<List<T, Ts...>, List<Us...>> : Reverse<List<Ts...>, List<T, Us...>>{};

}

template<typename T>
struct Reverse : Detail::Reverse<T, List<>> {};

template<typename T, typename U>
struct ReverseFind : Find<T, typename Reverse<U>::Type> {}

これは技術的には線形の複雑さですが、それでもおそらく得られるほど効率的ではありません。

4

1 に答える 1

1

Findこれは、最初のインデックスではなく最大の一致インデックスを返すように構造を変更するだけで簡単です( Live at Coliru )。

template<typename... Ts>
struct List{
    typedef List<Ts...> Type;
    enum {
        size = sizeof...(Ts)
    };
};

template<int I>
using IntType = std::integral_constant<int, I>;

namespace Detail {
    template <typename T, typename U>
    struct Max : IntType<(U::value > T::value) ? U::value : T::value> {};
    template<int I, typename T, typename... Ts>
    struct FindLast : IntType<-1>{};
    template<int I, typename T, typename U, typename... Ts>
    struct FindLast<I, T, U, Ts...> : FindLast<I + 1, T, Ts...>{};
    template<int I, typename T, typename... Ts>
    struct FindLast<I, T, T, Ts...> : Max<IntType<I>, FindLast<I + 1, T, Ts...>> {};
}

template<typename T, typename U>
struct FindLast;
template<typename T, typename... Ts>
struct FindLast<T, List<Ts...>> : Detail::FindLast<0, T, Ts...>{};
于 2013-11-11T15:31:38.510 に答える