替换模板元编程中的三元运算符 [英] Replacement for ternary operator in template metaprogramming

问题描述

我正在用 C++ 实现一个二项式系数(n 选择 k)函数.除了使用正常"函数(在运行时计算)之外，这也可以使用模板元编程(当参数在编译时已知)来完成:

I am implementing a binomial coefficient (n choose k) function in C++. Besides using a "normal" function (which is evaluated at runtime) this also can be accomplished using template metaprogramming (when the arguments are known at compile time):

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 选择 k = n 选择 n-k.因此可能会发生不必要的算术溢出，例如49 选择 43 会溢出，而 49 选择 6 不会.

The drawback of this implementation is, that it does not make use of the theorem n choose k = n choose n-k in the cases where k > n/2. So unnecessary arithmetic overflow may occur, e.g. 49 choose 43 does overflow, whereas 49 choose 6 does not.

我尝试了以下方法来改善这一点:

I have tried the following to improve this:

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;
};

不幸的是，我收到致命错误:模板实例化深度超过最大值 900.

这似乎是因为在递归模板实例化过程中没有评估三元运算符.

This seems to be caused by the fact, that the ternary operator is not evaluated during the process of recursive template instantiation.

使用 的可能替代方法是什么?: ?

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

I am interested in pre-C++11 solutions and newer solutions alike (maybe std::enable_if helps, but I do not know well about it).

推荐答案

经过一夜的睡眠，我想我明白了 std::conditional 的要点.

After a night of sleep, I think I got the point with the std::conditional.

正如@Yakk 所提议的，我也自己实现了conditional.

As @Yakk has proposed, I also have implemented the conditional myself.

此实现适用于所有 C++ 标准:

This implementation works with all C++ standards:

#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 ?).

Suggestions on how to make the code more concise or elegant (is it really necessary to use the second static member _value ?) are warmly welcome.

这篇关于替换模板元编程中的三元运算符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！