テンプレートメタプログラミングにおける三項演算子の置換

Question

私はC++で二項係数（n choose k）関数を実装しています。 これはまた、（引数がコンパイル時に知られている場合）、テンプレートメタプログラミングを使用して達成することができる（実行時に評価される）「正常な」関数を使用して加えて：

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = Binomialkoeffizient<n, k-1>::value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
}; 

この実装の欠点は、それことです定理nを利用しない。k> nを選ぶ.k> n/2の場合はnkを選ぶ。したがって、不必要な算術オーバーフローが生じる可能性があります。 49を選択すると43がオーバーフローしますが、49は6を選択しません。

は、私はこれを改善するために、次の試してみました：

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = (2*k > n) ? Binomialkoeffizient<n, n-k>::value : Binomialkoeffizient<n, k-1>::value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
}; 

は、残念ながら、私はfatal error: template instantiation depth exceeds maximum of 900を取得します。

これは、再帰的テンプレートインスタンス化のプロセス中に3項演算子が評価されないことが原因であると考えられます。

?:を使用すると可能な代替方法は何ですか？

私はpre-C++ 11のソリューションと新しいソリューションに興味があります（おそらくstd::enable_ifが役に立ちますが、よく分かりません）。

Answer 1

C++ 11は、コンパイル時に 関数または変数の値を評価することが可能であることを宣言（これは）...、

をconstexpr指定子を導入しました。そのような変数と関数は、 （ただし、適切な関数の引数が与えられていれば）だけコンパイル時定数式が許されるところで使用することができます。オブジェクト宣言で使用されるconstexpr 指定子はconstを意味します。コンパイル時に評価することができ

template<class T> 
constexpr T binomial_coefficient(const T n, const T k) 
{ 
    if (2 * k > n) 
    { 
     return binomial_coefficient(n, n - k); 
    } 
    else 
    { 
     return k ? binomial_coefficient(n, k - 1) * (n - k + 1)/k : 1; 
    } 
} 

：（http://en.cppreference.com/w/cpp/language/constexprより引用）

実際に

は、次のような機能を実装することができます。例として 、このスニペットは異なるコンパイラによってコンパイルされ、ライン

constexpr auto value = binomial_coefficient(49, 43); 

がconstexprとの答えはあなたが使用していると仮定すると、それを行うための最善の方法である

mov  eax, 13983816 

Answer 2

になっているhttps://godbolt.org/g/b1MgFdを見て現代のC++コンパイラ。

ただし、次のコードは基本的にはあまりにも多くのテンプレートのインスタンス化を避けるコードの改善です。実際には、私が知っている限り、あなたの例のようにテンプレートを使用すると、コンパイラは三項式にあるすべてのテンプレートを生成し、選択されたものだけでなく、2 * k > nがtrueの場合k2を定義することにより

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient 
{ 
    static const unsigned int k2 = (2 * k > n) ? n - k : k; 
    static const unsigned int value = Binomialkoeffizient<n, k2 - 1>::value * (n - k2 + 1)/k2 ; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
}; 

私は1つの余分なレベルを削除することができます。

C++ 11コンパイラを使用している場合は、constをconstexprに置き換えることができます。それ以外の場合は、enumの名前を使用しない方が望ましいかもしれません。コンパイラーがそれぞれのインスタンシエーションレベルでvalueメンバのメモリを予約している可能性があります。

Answer 3

睡眠の夜の後、私はstd::conditionalでポイントを得たと思う。

編集： @Yakkが提案したように、私もconditionalを実装しました。

この実装は、すべてのC++標準規格で動作します：コードはより簡潔またはエレガントにする方法について

#if __cplusplus >= 201103L 
    // in C++11 and above we can use std::conditional which is defined in <type_traits> 
    #include <type_traits> 
    namespace my { 
     using std::conditional; 
    } 
#else 
    // in older C++ we have to use our own implementation of conditional 
    namespace my { 
     template <bool b, typename T, typename F> 
     struct conditional { 
      typedef T type; 
     }; 

     template <typename T, typename F> 
     struct conditional<false, T, F> { 
      typedef F type; 
     }; 
    } 
#endif 

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = my::conditional< (2*k > n), Binomialkoeffizient<n, n-k>, Binomialkoeffizient<n, k> >::type::_value; 
    static const unsigned int _value = Binomialkoeffizient<n, k-1>::_value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
    static const unsigned int _value = 1; 
}; 

は、提案が（第2静的メンバ_valueを使用することが本当に必要なのか？）暖かく歓迎されています。