替换为模板元编程中的三元运算符

我正在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; 
};

这种实现的缺陷在于，它不使用定理n在k> n/2的情况下选择k = n选择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。

这似乎是由递归模板实例化过程中未评估三元运算符的事实引起的。

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

我对pre-C++ 11解决方案和更新的解决方案很感兴趣（也许std::enable_if有帮助，但我对此不太了解）。

来源

2017-07-28 Fabian

您是否尝试过使用['std :: conditional']（http://en.cppreference.com/w/cpp/types/conditional）？ – NathanOliver

请您详细说明一下吗？我不确定如何正确使用它。它似乎也只适用于C++ 11以上。 – Fabian

@Fabian是的，它是C++ 11。第1步：使用'std :: conditional'在C++ 11中解决它。第2步：在C++ 03中编写'my :: conditional'。第3步：利润。 – Yakk

C++ 11引入的constexpr说明符，

...（这）声明，它能够评价在编译时函数或变量的值。如果只允许编译时间常量表达式（前提是给出了适当的函数参数），那么可以使用这些变量和函数。在对象声明中使用的constexpr 说明符暗示const。

（从http://en.cppreference.com/w/cpp/language/constexpr报价）

在实际应用中，可以实现这样的功能：

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

，可以在编译时进行评估。作为一个例子，看看https://godbolt.org/g/b1MgFd其中该片段是由不同的编译器和线路

constexpr auto value = binomial_coefficient(49, 43);

成为

mov  eax, 13983816

来源

2017-07-28 23:04:37

我认为'constexpr'函数中的多个语句正式添加到C++ 14中。 – Phil1970

@ Phil1970你是对的。在这种特殊情况下，通过使用单个返回与另一个条件操作符（而不是我使用的“if”）很容易解决。 –

感谢您的建议。我通过用'objdump'分解目标代码来验证它，并且实际上计算的值在文件中。有趣的是，立即使用该值而不事先赋值给变量，例如'std :: cout << binomial_coefficient（49,43）;'导致值不在编译时计算。 – Fabian

与constexpr答案是做假设你使用的是最好的方式编译现代C++编译器。

但是，下面的代码基本上是对代码的改进，可以避免实例化太多的模板。实际上，据我所知，在你的例子中使用模板时，编译器会生成所有处于三元表达式的模板，而不仅仅是所选的一面。

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

通过定义k2我可以删除一个额外的水平时2 * k > n是真实的。

如果您使用的是C++ 11编译器，则可以用constexpr替换const。否则，使用未命名的enum可能更好，否则，编译器仍可能为每个实例级别的value成员保留内存。

来源

2017-07-29 14:11:57 Phil1970

感谢k2的好主意。正好在n = k的情况下，例如'Binomialkoeffizient <49, 49> :: value'你的程序不起作用，因为它永远实例化新模板直到达到极限。添加进一步spezialization'模板 struct Binomialkoeffizient { static const unsigned int value = 1; };'帮助。 – Fabian

经过一个晚上的睡眠，我想我得到了与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; 
};

建议（？是不是真的需要使用第二静态成员_value）的热烈欢迎。

来源

2017-07-29 23:22:07 Fabian

替换为模板元编程中的三元运算符

回答

相关问题