C++数组作为模板参数

Question

我想写一个简单的多项式 class，它可以接受一个系数数组，并在编译时将其展开为一个函数，这样我就不需要在运行处遍历系数时间。我想做这样的事情：

template <PARAM_TYPE, PARAMS>
class P {
public:
    PARAM_TYPE eval(PARAM_TYPE p){
        //Does PARAMS[0] * pow(p, PARAMS.length() -1) + ... + PARAMS[N-1] 
    }
}

调用示例[=12=]

P<double,{2,4,3}> quadratic;
quadratic.eval(5); //returns 73

我不想做循环，因为这会花费时间。理想情况下，我希望能够在编译时形成上面的表达式。这可能吗？谢谢

Answer 1

这里是一个做你想做的事的例子。编译器对是否将所有代码优化为常量很挑剔，具体取决于我注意到的用法和您使用的编译器。

test here

#include <type_traits>

template<class T, unsigned Exponent>
inline constexpr typename std::enable_if<Exponent == 0, T>::type
pow2(const T base)
{
    return 1;
}

template<class T, unsigned Exponent>
inline constexpr typename std::enable_if<Exponent % 2 != 0, T>::type
pow2(const T base)
{
      return base * pow2<T, (Exponent-1)/2>(base) * pow2<T, (Exponent-1)/2>(base);
}

template<class T, unsigned Exponent>
inline constexpr typename std::enable_if<Exponent != 0 && Exponent % 2 == 0, T>::type
pow2(const T base)
{
    return pow2<T, Exponent / 2>(base) * pow2<T, Exponent / 2>(base);
}

template<typename ParamType>
inline constexpr ParamType polynomial(const ParamType&, const ParamType& c0)
{
  return c0;
}

template<typename ParamType, typename Coeff0, typename ...Coeffs>
inline constexpr ParamType polynomial(const ParamType& x, const Coeff0& c0, const Coeffs& ...cs)
{
    return (static_cast<ParamType>(c0) * pow2<ParamType, sizeof...(cs)>(x)) + polynomial(x, static_cast<ParamType>(cs)...);
}

unsigned run(unsigned x)
{
   return polynomial(x, 2, 4, 3);
}

double run(double x)
{
  return polynomial(x, 2, 4, 3);
}

unsigned const_unsigned()
{
    static const unsigned value = polynomial(5, 2, 4, 3);
    return value;
}

double const_double()
{
    static const double value = polynomial(5, 2, 4, 3);
    return value;
}

编辑： 我已经将代码更新为使用 pow2<>() 的调整版本，它在编译时主动执行计算。这个版本在 -O2 上优化得非常好，它真的让我感到惊讶。您可以使用代码上方的按钮查看为完整程序生成的程序集。如果所有参数都是常量，编译器将在编译时生成整个常量值。如果第一个参数依赖于运行时，它仍然会为它生成非常紧凑的代码。

（感谢 this question 上的@dyp 给 pow 的灵感）

Answer 2

要计算多项式，一个好的算法是 Horner（参见 https://en.wikipedia.org/wiki/Horner%27s_method）。主要思想是递归地计算多项式。设一个系数为 ai 的 n 阶多项式 P。很容易看出序列Pk = Pk-1*x0 + an-k 其中P0 = an, 即P(x0) = Pn.

所以让我们使用 constexpr 函数来实现这个算法：

template<class T>
constexpr double horner(double x, T an) { return an; }

template<class... T, class U = T>
constexpr double horner(double x, U an, T... a) { return horner(x, a...) * x + an; }

std::cout << horner(5., 1, 2, 1) << std::endl;

//test if the invocation of the constexpr function takes the constant expression branch
std::cout << noexcept(horner(5., 1, 2, 1)) << std::endl;

如您所见，使用递归公式通过 constexpr 函数计算多项式非常容易。

C++数组作为模板参数

C++ array as template parameter

c++

templates

compile-time

template-meta-programming