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,我认为编译器是正确的,我不能那样做(如果我错了,请纠正我)。

我可以实现一个TypeAtMeta 函数,它会给我特定索引处的参数类型(使用递归),但这将是线性复杂性,如果我每次都从我的 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 回答