前向迭代(使用递归)对我来说很清楚:
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
,我认为编译器是正确的,我不能那样做(如果我错了,请纠正我)。
我可以实现一个TypeAt
Meta 函数,它会给我特定索引处的参数类型(使用递归),但这将是线性复杂性,如果我每次都从我的 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> {}
这在技术上是线性的复杂性,但仍然可能没有人们能得到的那么有效。