How do I iterate (recurse) backwards through a variadic list of template parameters?

Question

Forward iteration (using recursion) is pretty clear to me:

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

What if I wanted to start at the last item and work backward so I find the last occurrence first?

My Attempt:

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

This fails on MSVC2013 with error C3515: if an argument for a class template partial specialization is a pack expansion it shall be the last argument and I think the compiler is right and I can't do it that way (correct me please if I am wrong).

I could implement a TypeAt Meta function which would give me the type of the parameter at a specific index (using recursion) but it would be linear complexity and if I called it every time from my ReverseFind that would result in exponential complexity.

Is there a way to implement ReverseFind with linear complexity like Find has?

Update: A better attempt:

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> {}

This is technically linear complexity but still probably not as efficient as one could get.

possible duplicate of [How can I pull variadic template arguments off from the tail instead of the head?](http://stackoverflow.com/q/6632533/341970) — Ali, Nov 11 '13 at 15:29
Possibly related: [How to reverse the order of arguments of a variadic template function?](http://stackoverflow.com/q/15904288/341970) — Ali, Nov 11 '13 at 15:31

score 1 · Accepted Answer · answered Nov 11 '13 at 15:31

This is simple enough to do with an alteration to your Find structure to return the largest matching index instead of the first such (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...>{};

Yes this is probably less complex than my better attempt. – odinthenerd Nov 11 '13 at 15:46 — odinthenerd, Nov 11 '13 at 15:46

How do I iterate (recurse) backwards through a variadic list of template parameters?

1 Answers1