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

私のひらめき日記

もっと自由に、流暢にプログラミングする

コンパイル時階乗計算まとめ

まずは、関数テンプレートの明示的特殊化バージョンから。*1

template<int N>
int factorial()
{
    return factorial<N-1>() * N;
}

template<>
int factorial<0>()
{
    return 1;
}

int main(void)
{
    cout << factorial<4>() << endl;
    return 0;
}

関数テンプレートのコンパイル時計算には、もう一つ問題があって、部分特殊化ができない:

#include <iostream>
using namespace std;

//template<typename T, int size>
//T factorial()
//{
//    return factorial<T, size-1>*size;
//}

//関数テンプレート、の部分特殊化はできない
//template<typename T>
//T factorial<0>()
//{
//    return 1;
//}

template<typename T, int size>
struct factorial
{
    static T func()
    {
        return factorial<T, size-1>::func() * size;
    }
};

//クラステンプレート、クラステンプレート内テンプレートの部分特殊化は可能
template<typename T>
struct factorial<T, 0>
{
    static T func()
    {
        return 1;
    }
};

int main(void)
{   
    cout << factorial<int, 5>::func();
    return 0;
}

なので、メタプログラミングするんだったら、structを用いてテンプレート化するのが普通。

注)関数のオーバーロードを有効活用すれば、関数の部分特殊化っぽいことは表現可能。
*2

#include <iostream>
using namespace std;


template<int v>
struct Int2Type
{
    //enum { value = v};
    static const int value = v;
};

//実際の実装は、ここらにかく。
template<typename T>
void DoSth_impl(T* pObj, Int2Type<true>)
{
    T* pNewObj = pObj->Clone();
}

template<typename T>
void DoSth_impl(T* pObj, Int2Type<false>)
{
    T* pNewObj = new T(*pObj);
    cout << *pNewObj << endl;
}

//オーバーロードにより、関数の部分特殊化を実現する。
template<typename T, bool isPolyMorphic>
void DoSomething(T* pObj)
{
    DoSth_impl(pObj, Int2Type<isPolyMorphic>());
}

//普通に関数の部分特殊化を以下のように行うと、失敗することに注意。
//template<typename T>
//void DoSomething<false>(T* pObj) { /* Do Sth*/ }

int main(void)
{
    int* p = new int;
    *p = 7;
    DoSomething<int, false>(p);
    
    return 0;
}

昔風に、enumハック*3を用いて、コンパイル時階乗計算:

#include <iostream>
using namespace std;

template<int N>
struct factorial
{
    //enum hack
    enum { value = N * factorial<N - 1>::value };
};

template<>
struct factorial<0>
{
    enum {value = 1 };
};

int main(void)
{
    cout << factorial<4>::value << endl;
    return 0;
}

enumハック使わずに、static constを用いる方法もある。(というより、enum ハックが技巧的)

#include <iostream>
using namespace std;

template<int N>
struct factorial
{
    static const int value = N * factorial<N-1>::value;
};

template<>
struct factorial<0>
{
    static const int value = 1;
};

int main(void)
{
    cout << factorial<4>::value << endl;
    return 0;
}

C++11以降のconstexprを用いた*4コンパイル時階乗計算:

#include <iostream>
using namespace std;

//引数(int n)がコンパイル時にわかっていれば、factorial関数の戻り値はコンパイル時に定数として求められる。
//逆に引数がコンパイル時にわかっていなければ、factorial関数の戻り値は実行時に決定する。
constexpr int factorial(int n)
{
    return n == 0 ? 1 : n*factorial(n-1);
}

int main(void)
{
    int n = 4;
    //実行時計算
    cout << factorial(n) << endl;
    
    //引数が定数 => コンパイル時計算
    cout << factorial(4) << endl;
}

まとめると、値をコンパイル時に計算する場合は、enum, const static, constexprを用いる。
ちなみに、型の変換や型の判別を静的に行う場合は、typedef, usingを用いる。*5

*1:でも、これ、関数の戻り値計算まではコンパイル時に計算してくれるけど、factorial関数から、mainに値を戻す作業は実行時に行うので、厳密な意味ではコンパイル時計算でない

*2:void DoSomethingの第二引数に、Int2Type型を指定しているが、空の構造体のサイズは0ではないので、inlineを指定しない限りは、オーバーヘッドが完全になくなるわけではないと思う。

*3:enum classは、汎整数型として解釈されない。詳しくは Effective Modern C++ ch.10を参照のこと

*4:constexpr関数は必ずしも、constexprの戻り値を返すわけではない。Effective Modern C++ ch.15を参照のこと。

*5:C++11では、usingはtypedefの上位互換である。 http://qiita.com/Linda_pp/items/44a67c64c14cba00eef1とか、Effective Modern C++ 項目9を参照してください