index_tuple idiom

勉強会のスライドなんかでこの名前で見かけます。 非常によく知られたidiomですが、メモ程度に簡単にまとめ直します。

index_tuple idiomはindex_tuple<0,1,2,3,4>のように連番の整数値を型リストとして持つオブジェクト(index_tuple)を生成する為のidiomです。 index_tuple<N, N+1, ..., M-1>をindex_range<N, M>::typeで得る事が出来ます。

理解のしやすいように最もシンプルな、O(N)のコードを掲載しておきます。

また、より優れた実装として対数オーダーで実装する方法があります。 効率の良い実装については次の記事を参照して下さい。http://d.hatena.ne.jp/boleros/20120406/1333682532
この差というのは実際かなり大きく、以下の実装だと256要素程度で再帰上限回数を迎えてそれ以上の要素数のindex_tupleを生成出来ませんが、上の方法だと100万要素でも生成出来ます。

#include <type_traits>

template<std::size_t... indexes>
struct index_tuple;

template<std::size_t first, std::size_t last, class result = index_tuple<>, bool flag = first >= last>
struct index_range
{
    using type = result;
};

template<std::size_t step, std::size_t last, std::size_t... indexes>
struct index_range<step, last, index_tuple<indexes...>, false>
: index_range<step + 1, last, index_tuple<indexes..., step>>
{};

int main()
{
    static_assert(std::is_same<
                  index_tuple<0,1,2,3,4>,
                  index_range<0, 5>::type>
                  ::value, "");
}

利用例としては、index_range<0, N>::typeをtemplate<std::size_t... indexes>に渡してやり、indexes...を展開すると0,1,...,N-1を順に得る事が出来るので、タプルの展開や、コンパイル時に配列の要素を順番に処理するといった事に使えます。 このidiomはC++14ではindex_sequenceとして標準ライブラリに入るみたいです。