コンパイル時zip関数の書き方、並びに京都C++勉強会の案内

江添とボレロ村上の京都C++勉強会が、12月16日に行われる。これを書いている時点では、まだ空きがあるので、最新のC++14の新機能と、コンパイル時レイトレーシングを勉強したければ、ATNDで参加申し込みをせよ。

江添とボレロ村上の京都C++勉強会 | 集客ならイベントアテンド

さて、昨日は、コンパイル時zip関数を書いた。ただし、コードだけで解説が欠けていた。今日は、解説をしようと思う。

zip

本の虫: 久しぶりにメタプログラミングらしいメタプログラミングをした

以下のような関数

template<std::size_t N, typename... T>
auto zip(const std::array<T, N>&... containers)
    -> std::array < std::tuple < T ... > , N >

が、以下のように動く。

std::array<int, 5> a = {1, 2, 3, 4, 5}; std::array<char, 5> b = {'a', 'b', 'c', 'd', 'e'}; zip<5>(a, b); // -> std::array<std::tuple<int, char>, 5> : (1, 'a'); (2, 'b'); ...; (5, 'e') std::array<int, 4> c = {1, 2, 3, 4}; zip<4>(a, c) // -> compile time error std::vector<int> d = {1, 2, 3, 4, 5} zip<5>(a, d) // -> complie time error

これ自体は、実行時関数ならば、以下のように書ける。

template < std::size_t N, typename ... Types >
auto zip_runtime( std::array< Types, N > const & ... containers )
    -> std::array< std::tuple< Types... >, N >
{
    std::array< std::tuple< Types... >, N > result ;

    for ( std::size_t i = 0 ; i != N ; ++i )
    {
        result[i] = std::make_tuple( containers[i] ... ) ;
    }

    return result ;
}

と、このように簡単なコードなのだが、これはconstexpr関数にできない。無駄なループがある。このようなコードは、リスト初期化を使えば、以下のように書ける。

std::array< std::tuple< Types... >, N >{
    { std::make_tuple( containers_0[0], containers_1[0]) },
    { std::make_tuple( containers_0[1], containers_1[1]) },
// ...
} ;

こういう形に落としこんでしまえば、最初から初期化としてarrayを構築できるし、constexpr関数にできる。

containersは、パック展開でいくらでも展開できるが、添字をどうにかしたい。これにはInteger Sequenceと呼ばれているテクニックを用いることができる。原理はN3493で解説されていて、C++14の標準ライブラリに入るのだが、残念ながら、C++11で実装しなければならないので、これを実装しなければならない。この論文と実装例は、すでに簡易レビューで紹介している。

本の虫: C++ 2013-01 mailingの簡易レビュー

template< std::size_t ... >
struct index_seq { } ;

template < std::size_t N, typename T >
struct make_index_seq_impl ;

template < std::size_t N, std::size_t ... I  >
struct make_index_seq_impl< N, index_seq< I ... > >
{
    using type = typename make_index_seq_impl< N-1, index_seq< N-1, I... > >::type ;
} ;

template < std::size_t ... I  > 
struct make_index_seq_impl< 0, index_seq< I ... > >
{
    using type = index_seq< I... > ;
} ;

template< std::size_t N >
using make_index_seq = typename make_index_seq_impl< N , index_seq< > >::type ;

これは、単にNを指定すると、0,1,2,3... Nまで整数型の非型テンプレートパラメーターパックを生成するための、簡単なメタ関数だ。この実装は簡易的なもので、テンプレートの再帰深度が線形に増えていくが、今回は特に問題としない。

ここまではいい。ではさっそく、これを使ってリスト初期化に展開されるコードを書こう。

template < std::size_t N, std::size_t ... I, typename ... Types >
constexpr auto zip_aux( index_seq< I ... >, std::array< Types, N > const & ... containers )
    -> std::array< std::tuple< Types... >, N >
{
    return std::array< std::tuple< Types ... >, N >{ { 
        // エラー
        std::make_tuple<I>( containers[I]... )...
    } } ;
} 

template < std::size_t N, typename ... Types >
constexpr auto zip( std::array< Types, N > const & ... containers )
    -> std::array< std::tuple< Types... >, N >
{
    return zip_aux( make_index_seq< N >(), containers ... ) ;
}

残念ながら、これエラーになる、なぜなら、パラメーターパックが2つもあって、その数も同じではないからだ。そのため、パック展開に失敗する

C++ Templates Metaprogrammingに書いてあるように、問題があるときは、もう一段階の参照を挟んでやるとよい。ここでは、パック展開されたコンテナーをパラメーターパクで、添字を非パラメーターパックで受け取ってtupleを返す関数を追加する。

template < std::size_t I, std::size_t N, typename ... Types >
constexpr auto make_unpacked_tuple( std::array< Types, N > const & ... containers )
    -> std::tuple< Types ... >
{
    return std::make_tuple( containers[I]... ) ;
}

このもう一段階の参照を使えば、以下のように書ける。

template < std::size_t N, std::size_t ... I, typename ... Types >
constexpr auto zip_aux( index_seq< I ... >, std::array< Types, N > const & ... containers )
    -> std::array< std::tuple< Types... >, N >
{
    return std::array< std::tuple< Types ... >, N >{ { make_unpacked_tuple<I>( containers... )... } } ;
} 

template < std::size_t N, typename ... Types >
constexpr auto zip( std::array< Types, N > const & ... containers )
    -> std::array< std::tuple< Types... >, N >
{
    return zip_aux( make_index_seq< N >(), containers ... ) ;
}

このように書けば、constexpr関数にできるzip関数の出来上がりだ。わざわざループで代入しなくても、構築時のリスト初期化で済ますことができる。

さて、冒頭でも書いたように、江添とボレロ村上の京都C++勉強会が、12月16日に行われる。これを書いている時点では、まだ空きがあるので、最新のC++14の新機能や、コンパイル時レイトレーシングを勉強したければ、ATNDで参加申し込みをせよ。

江添とボレロ村上の京都C++勉強会 | 集客ならイベントアテンド