読者です 読者をやめる 読者になる 読者になる

altebute.hatenablog.com

犬も歩けば規格にあたる

再帰テンプレートを用いた std::tuple の展開と処理

C++ programming

本記事では、std::tupleに対するstd::for_each的な処理を行うためのコードについて記述する。

以下のコードは、規定クラスのポインタの配列に派生クラスのアドレスを代入し、range-based forを用いてメンバ仮想関数をコールしている。

struct Base
{
    virtual void operator()() = 0;
};

#include <iostream>

template<int num>
struct Derived final : public Base
{
    void operator()() override final
    {
        std::cout << num << std::endl;
    }
};

#include <array>
#include <memory>

int main()
{
    using namespace std;
    
    array<unique_ptr<Base>, 3> a;
    
    a[0].reset(new Derived<128>);
    a[1].reset(new Derived<256>);
    a[2].reset(new Derived<512>);
    
    for (auto & p : a)
    {
        p->operator()();
    }
    
    return 0;
}

配列のサイズがコンパイル時定数であれば、一般にstd::vectorを使うよりもstd::arrayを使ったほうが良い*1

更に、上記のコードについて、配列に対する任意の添字について、代入される派生クラスの型が固定なのであれば、わざわざ継承を用いると仮想関数テーブルの分メモリを消費するし、ポインタを介して関数を呼ぶ分処理負荷が増える。

継承を行わないように変更したコードが以下のコードである。

#include <iostream>

template<int num>
struct Test final
{
    void operator()()
    {
        std::cout << num << std::endl;
    }
};

int main()
{
    using namespace std;
    
    Test<128> test1;
    Test<256> test2;
    Test<512> test3;
    
    test1();
    test2();
    test3();
    
    return 0;
}

継承を行っていないので、型が異なるため配列による管理は行えない。ポインタで扱う必要もなくなったので、ローカル変数として宣言している。当然、まとめて扱うことは出来ない。そこで、異なる型をまとめて扱うために、std::tupleを用いる。

#include <tuple>

int main()
{
    using namespace std;
    
    auto tpl = make_tuple(Test<128>(), Test<256>(), Test<512>());
    
    get<0>(tpl)();
    get<1>(tpl)();
    get<2>(tpl)();
    
    return 0;
}

std::make_tupleによって、新しく型が生成され、まとめて扱えている。ただし、要素に対するアクセスはコンパイル時定数で行う必要があるため、一般的に繰り返しに用いられるfor Statementwhile Statemanetでは扱うことが出来ない。各要素に対して同じ操作*2を行うためには、再帰テンプレートを用いる必要がある。

#include <tuple>
#include <iostream>

using namespace std;

template<size_t begin, size_t end, bool terminate = begin + 1 == end>
struct ExecutePart;

template<size_t begin, size_t end>
struct ExecutePart<begin, end, true>
{
    template<typename Tuple, typename Function>
    static void Execute(Tuple && tuple, Function && function)
    {
        function(get<begin>(tuple));
    }
};

template<size_t begin, size_t end>
struct ExecutePart<begin, end, false>
{
    template<typename Tuple, typename Function>
    static void Execute(Tuple && tuple, Function && function)
    {
        // execute first half
        ExecutePart<begin, (begin + end) / 2>::Execute
            (forward<Tuple>(tuple), forward<Function>(function));
        
        // execute latter half
        ExecutePart<(begin + end) / 2, end>::Execute
            (forward<Tuple>(tuple), forward<Function>(function));
    }
};

// pass all element of tuple to function
template<typename Tuple, typename Function>
void ExecuteAll(Tuple && tuple, Function && function)
{
    using namespace std;
    
    static const size_t end =
        tuple_size<typename remove_reference<Tuple>::type>::value;
    
    ExecutePart<0, end>::Execute(
        forward<Tuple>(tuple),
        forward<Function>(function));
}

// function object
// output template argument
template<int num>
struct Test final
{
    void operator()()
    {
        std::cout << num << std::endl;
    }
};

// function object
// call operator() of any type argument
struct Function
{
    template<typename T> inline void operator()(T && arg)
    {
        arg();
    }
};

int main()
{
    using namespace std;
    
    auto tpl = make_tuple(Test<128>(), Test<256>(),Test<512>());
    
    ExecuteAll(tpl, Function());
    
    return 0;
}

右辺値参照やらなんやらかんやらでややこしいが、要は分割統治法を用いてstd::tupleを各々の要素に分割し、それを関数オブジェクトに対して渡している。各々の要素の型が異なるため、std::functionalや、関数ポインタ、ラムダ式は使えない*3

ちなみに再帰テンプレートの再帰深度が O(log(n)) になるように組んでいる。

テンプレート関数は部分特殊化出来ないため、再帰呼び出しによってstd::tupleの展開を行うための関数はテンプレートクラスのメンバ関数になっている。

*1:そうでない状況があるかも知れないが、私には分からない

*2:とは言うものの、実際にはダックタイピングである。

*3:たぶん。