[C++]テンプレート再帰回数の限界、再帰回数を減らす実装方法。

　テンプレートメタプログラミングなどをしていると多用することになる、テンプレートの再帰。実はこの再帰回数には制限がある。C++11ではこの再帰回数は1024回が推奨されており十分に大きい。実際の回数制限はコンパイラによって異なるが、それなりに大きな数字になっている。そのため小さな利用に留まる限りは問題ではない。ただし、私のようにメタプログラミングを使い倒していると稀にこの制限に引っかかることがある。

　例えばstd::tuple_elementのように、可変長引数テンプレートで与えられた型のリストからN番目の型を取得するようなクラステンプレートを考えてみる。

#include <iostream>
#include <vector>

template <size_t N, class ...Types>
class GetType;
template <size_t N, class TypeHead, class ...TypeBody>
class GetType<N, TypeHead, TypeBody...> : public GetType<N - 1, TypeBody...>
{};
template <class TypeHead, class ...TypeBody>
class GetType<0, TypeHead, TypeBody...>
{
public:
    using Type = TypeHead;
};
int main()
{
    std::cout << typeid(GetType<3, int, double, float, char, std::vector<double>>::Type).name() << std::endl;
    return 0;
}

　非常に素直な実装だ。再帰するごとに可変長引数テンプレートを一個ずつ剥がしていくだけの簡単なお仕事。環境によるかもしれないが、Visual Studioのstd::tuple_elementはこれとほぼ同様の実装である。
　ただしもしGetTypeに与える型リストが制限を超えていて、かつNに制限以上の数字を与えてしまった場合、その時点でコンパイルエラーとなる。この単純な実装では再帰回数がO(N)なので、制限超過を招きやすいのだ。普通はそんな事は起きないのだろうが、私はやらかしてしまった。

　ではこのO(N)をもっと減らす方法はないのだろうか？　……ある。私の思いつく限りでは、O(log(N))に削減することが可能だ。

#include <iostream>
#include <vector>

template <class...>
struct TypeList {};
namespace detail
{
template <size_t Index, class Type>
struct GetType_impl_s
{
    friend Type Get(const GetType_impl_s&, std::integral_constant<size_t, Index>);
};
template <class, class>
struct GetType_impl;
template <size_t ...Indices, class ...Types>
struct GetType_impl<std::index_sequence<Indices...>, TypeList<Types...>>
    : public GetType_impl_s<Indices, Types>...
{};
}
template <size_t Index, class ...Types>
struct GetType
{
    using Type = decltype(Get(detail::GetType_impl<
                                std::make_index_sequence<sizeof...(Types)>,
                                TypeList<Types...>>(),
                              std::integral_constant<size_t, Index>()));
};
int main()
{
    std::cout << typeid(GetType<3, int, double, float, char, std::vector<double>>::Type).name() << std::endl;
    return 0;
}

　意外と短く纏まった。
　上の実装の肝は、Get関数のオーバーロードを解決させることで要求された型を判定しているところだ。GetTypeに与えられたTypes...一つ一つにIndexを割り当て、ある特定のIndexを用いて呼び出すことのできるGet関数を探し、その戻り値の型を取得している。関数オーバーロードの解決に長大な再帰は必要ないので、std::make_index_sequenceのみが制限を受けている状態。従って、std::make_index_sequenceの再帰回数が制限を超過しない限り問題とはならない。std::make_index_sequenceは実装に依存するが、原理的にO(log(N))である。したがって、改良型GetTypeもO(log(N))となる。
　ただし、もし利用しているコンパイラがstd::make_index_sequenceを上のGetTypeのようにO(N)の単純な再帰を用いて実装している場合、まずこちらの改良版を自ら作成しなければならないだろう。MSVC2015以上では問題ないようだったが。まあ別に、これは特に難しくない。

　これを少し応用すると可変長引数テンプレートのリストの中から特定の型のindexを検索するクラステンプレートなども設計できる。実装は割愛。上のGetTypeをちょっとこねくり回すだけで十分だ。