C++

Little Inside TMP

updated on Leave a Comment on Little Inside TMP

引子

下面是一段 TMP 代码，用来求 sum(range(from, to, step)):

namespace SigmaDetails
{
    template <int _From, int _To, int _Step, bool _Stop>
    struct SigmaImpl
    {
        static_assert(_Step, "Step cannot be set zero!");

        static constexpr int
        value =
        _From +
        SigmaImpl<
            _From + _Step,
            _To,
            _Step,
            (_From + _Step >= _To && _Step > 0) ||
            (_From + _Step <= _To && _Step < 0)
        >::value;
    };

    template <int _From, int _To, int _Step>
    struct SigmaImpl<_From, _To, _Step, true>
    { static constexpr int value = 0; };
}

template <int _From, int _To, int _Step = 1>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{ };

它可以求：

$\sum i.$

可如果我们要求 $\sum i^2$呢？ 有人会说，我们可以把 SigmaImpl 的代码简单改改。 那如果 $\sum i^3$ 呢？显然，当需求不断增多，我们这样改是改不过来的。

一些坑

于是我们就想了一个办法，给这些模板添加一个参数 typename _F：

namespace SigmaDetails
{
    template <int _From, int _To, int _Step, typename _F, bool _Stop>
    struct SigmaImpl
    {
        static_assert(_Step, "Step cannot be set zero!");

        static constexpr int
        value =
        _F<_From>::value +
        SigmaImpl<
            _From + _Step,
            _To,
            _Step,
            _F,
            (_From + _Step >= _To && _Step > 0) ||
            (_From + _Step <= _To && _Step < 0)
        >::value;
    };

    template <int _From, int _To, int _Step, typename _F>
    struct SigmaImpl<_From, _To, _Step, _F, true>
    { static constexpr int value = 0; };
}

// Identity 是单位变换 I(x) = x
template <int _From, int _To, int _Step = 1, typename _F = Identity>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{ };

我们所料想的是，当我们像这样调用 Sigma：

Sigma<1145, 14191, 810, Identity>::value

模板会帮我们将 SigmaImpl 中的

_F<_From>::value

实例化为：

Identity<_From>::value

但实际上编译器会告诉我们： Identity 是一个 incomplete type. 我们连 Identity 的参数都没有给它，它又怎么会被实例化呢？并且我们也知道，模板类即使所有参数都有默认值，我们也至少需要在它后面加上一对空的尖括号。而如果我们给定模板的参数，那它就是一个完整的类，比如说 Identity<1>。那么下面这样的行为显然也是荒谬的：

Identity<1><_From>::value

于是我们又想到，我们干脆给模板塞个函数作参数得了，然而这样的方法麻烦也显而易见，并且缺失一种整体的美感。

解决方法（Pre-C++20）

  • 一个办法是：给所有的模板都添加一个静态成员函数，_call_，于是我们可以用 _F::_call_(_From) 来调用与这些模板行为相一致的函数。下面是代码：
template <int N = 0>
struct Identity
{
    static constexpr int value = N;
    static constexpr int _call_(int &&n) { return n; }
};

namespace SigmaDetails
{
    template <int _From, int _To, int _Step, typename _F, bool _Stop>
    struct SigmaImpl
    {
        static_assert(_Step, "Step cannot be set zero!");

        static constexpr int
        value =
        _F::_call_(_From) +
        SigmaImpl<
            _From + _Step,
            _To,
            _Step,
            _F,
            (_From + _Step >= _To && _Step > 0) ||
            (_From + _Step <= _To && _Step < 0)
        >::value;
    };

    template <int _From, int _To, int _Step, typename _F>
    struct SigmaImpl<_From, _To, _Step, _F, true>
    { static constexpr int value = 0; };
}

template <int _From, int _To, int _Step = 1, typename _F = Identity<>>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{ static constexpr int _call_() { return Sigma<_From, _To, _Step, _F>::value; } };

于是我们可以这样使用 Sigma：

Sigma<1145, 14191, 810, Identity<>>::value
  • 另一个解决办法：

用 template template argument，模板的模板参数。其实这样更加原教旨主义。用模板解决一切模板的问题。

一部分代码：

// 无需再使用 Identity<> 了
template <long long _From, long long _To, long long _Step = 1, template <long long> typename _F = Identity>
struct RangeSum:
    RangeSumDetails::RangeSumImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0LL) ||
        (_From <= _To && _Step < 0LL)>
{ };

更优雅的解决方法

C++ 20 支持了模板 auto 参数，并且 Lambda 可以作为模板参数使用了。

于是我们可以把 Sigma 的最后一个参数 typename _F 替换成 auto _F = [](int &&_){return _;}. 这样我们就能直接在参数里写 Lambda 或者 函数了。

效果图

这部分完整代码如下：

#if __cplusplus >= 201709L
// Sigma implementation details are hidden here:

namespace SigmaDetails
{
    template <int _From, int _To, int _Step, auto _F, bool _Stop>
    struct SigmaImpl
    {
        static_assert(_Step, "Step cannot be set zero!");
        static constexpr int
        value =
        _F(_From) +
        SigmaImpl<
            _From + _Step,
            _To,
            _Step,
            _F,
            (_From + _Step >= _To && _Step > 0) ||
            (_From + _Step <= _To && _Step < 0)
        >::value;
    };

    template <int _From, int _To, int _Step, auto _F>
    struct SigmaImpl<_From, _To, _Step, _F, true>
    { static constexpr int value = 0; };
}

// TMP.Sigma

template <int _From, int _To, int _Step = 1, auto _F = [](int &&_){ return _; }>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{
    Sigma() = delete;
    static constexpr int _call_() { return Sigma<_From, _To, _Step, _F>::value; }
};

#else // _HAS_CXX20
namespace SigmaDetails
{
    template <int _From, int _To, int _Step, typename _F, bool _Stop>
    struct SigmaImpl
    {
        static_assert(_Step, "Step cannot be set zero!");
        static constexpr int
        value =
        _F::_call_(_From) +
        SigmaImpl<
            _From + _Step,
            _To,
            _Step,
            _F,
            (_From + _Step >= _To && _Step > 0) ||
            (_From + _Step <= _To && _Step < 0)
        >::value;
    };

    template <int _From, int _To, int _Step, typename _F>
    struct SigmaImpl<_From, _To, _Step, _F, true>
    { static constexpr int value = 0; };
}

template <int _From, int _To, int _Step = 1, typename _F = Identity<>>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{
    Sigma() = delete;
    static constexpr int _call_() { return Sigma<_From, _To, _Step, _F>::value; }
};
#endif

尾递归的写法

（其实没卵用，照样会有递归层数超过限制的报错，而且静态断言没了）

namespace SigmaDetails
{
    template <int _From, int _To, int _Step, auto _F, bool _Stop, int _Res = 0>
    struct SigmaImpl:
        SigmaImpl<
                _From + _Step,
                _To,
                _Step,
                _F,
                (_From + _Step >= _To && _Step > 0) ||
                (_From + _Step <= _To && _Step < 0),
                _Res + _F(_From)
            >
    { };

    template <int _From, int _To, int _Step, auto _F, int _Res>
    struct SigmaImpl<_From, _To, _Step, _F, true, _Res>
    { static constexpr int value = _Res; };
}

// TMP.Sigma

template <int _From, int _To, int _Step = 1, auto _F = [](int &&_){ return _; }>
struct Sigma:
    SigmaDetails::SigmaImpl<
        _From,
        _To,
        _Step,
        _F,
        (_From >= _To && _Step > 0) ||
        (_From <= _To && _Step < 0)>
{
    Sigma() = delete;
};

template <int _From, int _To, auto _F>
struct Sigma<_From, _To, 0, _F>
{ };

Offensive77

A little learning is a dangerous thing.

You may also like

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注