std::make_index_sequence<N>は、std::index_sequence<0, 1, 2, ..., N-1>に展開される、メタプログラミングを行う場合や最適化に便利なエイリアステンプレートです。
しかし、以下の問題点があります。
C++の新しい機能を使えば簡単に実装できます。 しかし、自分で実装するのは、C++11環境で使いたいため自分で実装する必要がある、という状況でしょう。 したがって、C++の新しい機能を使わない、かつ簡潔な実装が必要とされます。
コンパイル時空間計算量がΩ(N2)となる、非常に簡潔な実装
#include <cstddef>
template<std::size_t...> struct index_sequence {};
template<std::size_t I, std::size_t... Is> struct S : S<I-1, I-1, Is...> {};
template<std::size_t... Is> struct S<0, Is...> { index_sequence<Is...> f(); };
template<std::size_t N> using make_index_sequence = decltype(S<N>{}.f());
make_index_sequenceは、たったこれだけで定義可能です。
このコードを作るにあたって考慮した点は、以下のような感じです。
using type = typename S<N>::type;などとやってしまうと長くなるため、関数とdecltypeを使う- ただし、テンプレートの再帰の終端ケースであるかの分岐が必要であるため、必ず構造体を作る必要がある*3
- 継承を使うと構造体テンプレートの末尾再帰を簡潔に書ける
コンパイル時空間計算量がΩ(N)となる、工夫した実装
#include <cstddef>
template<std::size_t...> struct index_sequence {};
template<std::size_t N, bool> struct S { template<std::size_t... Is> index_sequence<Is..., (Is+N)...> f(index_sequence<Is...>); };
template<std::size_t N> struct S<N, true> { template<std::size_t... Is> index_sequence<Is..., (Is+N)..., N*2> f(index_sequence<Is...>); };
template<std::size_t N> struct Q { decltype(S<N/2, N%2>{}.f(Q<N/2>{}.g())) g(); };
template<> struct Q<0> { index_sequence<> g(); };
template<std::size_t N> using make_index_sequence = decltype(Q<N>{}.g());
再帰深度を対数回に抑えたバージョンです。
この形式の場合、普通は末尾再帰になりません*4。
そのため継承を使った方法は使えませんが、Nの偶奇によって分岐が発生するため、構造体にする必要はあります。
テンプレートを分解する場合は関数引数が最も簡単です。
よってこのような形になりました。
