c++ - 模板元编程中三元运算符的替换

Question

我正在用 C++ 实现二项式系数(n 选择 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;
};

此实现的缺点是，在 k > n/2 的情况下，它没有使用定理 n choose k = n choose n-k。因此可能会发生不必要的算术溢出，例如49 choose 43确实会溢出，而49 choose 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 :模板实例化深度超过最大值 900。

这似乎是由于在递归模板实例化过程中没有对三元运算符求值造成的。

使用有哪些可能的替代方案？:？

我对 C++11 之前的解决方案和更新的解决方案都感兴趣(也许 std::enable_if 有帮助，但我不太了解)。

Answer 1

经过一夜的 sleep ，我想我明白了 std::conditional 的意义。

编辑:正如@Yakk 所建议的，我自己也实现了条件。

此实现适用于所有 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;
};

热烈欢迎有关如何使代码更简洁或优雅的建议(是否真的有必要使用第二个静态成员 _value ？)。