c++ - 如何通过模板参数的可变列表向后迭代(递归)？

Question

前向迭代(使用递归)对我来说非常清楚:

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 上失败，错误 C3515:如果类模板部分特化的参数是包扩展，它应该是最后一个参数，我认为编译器是正确的，我不能这样做就是这样(如果我错了请纠正我)。

我可以实现一个 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> {}

这在技术上是线性复杂度，但可能仍然没有达到人们所能达到的那样高效。

Answer 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...>{};