c++ - “使用算法；不要为多步逻辑编写代码？

Question

这个问题让我觉得“根本不要使用显式循环！使用 STL/Boost 算法”，但仔细看，我注意到有一个adjacent_difference，accumulate并且 Boost 有一个zip地方，

while (i<l-1){
    ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
    i++;
}

他们根本不堆叠在一起，但每个人只能自己完成一个完整的传球。因此，以直接的方式使用它们将需要许多包含部分结果的中间副本。也就是说，让相邻差异写入一个新向量，它是 zip 等的参数。

现在在“现代”C++ 中，口头禅是我们不应该“编写代码”并且很少需要显式循环。

但我的实际经验更像是这样的案例：要做的事情不是一个简单的步骤，结果也不是像那样批量收集的。

那么，如何以一种流线型的方式编写它，指的是要执行的操作，但不是循环遍历范围，也不是显式地拉取每个元素。

Boost 迭代器过滤器通常可以构建更复杂的逻辑，最终在驱动循环内结束（因此中间结果没有整体复制）但是这个示例有几个特性说明了我发现 Boost 范围过滤器的限制！而且设置它比编写for循环更复杂！

所以，如果 C++“名人录”说我们应该能够用新的语言和库特性来编写这种方式，那么您如何在这里做到这一点，一个比他们在讲座中展示的更真实的简单案例？

score 2 · Accepted Answer

仅使用 Boost Range，您想编写：

auto ans = boost::accumulate(
        boost::combine(X|differential|abs, Y|differential|abs),
        0ull,
        [](auto accum, auto const& xy) { return accum + std::max(boost::get<0>(xy), boost::get<1>(xy)); }
    );

这可以通过一些方便的工作来实现。

`abs`

绝对值的范围适配器

我在这里作弊，因为我不想麻烦在这里创建一个真正的适配器范围：

auto abs = transformed([](auto x) { return std::abs(x); });

就这样。

differential

用于相邻差异的范围适配器

请注意，我没有复制的行为，std::adjacent_difference因为它在结果中包含第一个源值（我们不想要）。相反，我们想要 n-1 个差分值。

我已经从文档中的 §3.1 中获取了说明，并结合了一些iterator_facade减少输入的内容：

namespace boost { namespace adaptors {
    template <typename R>
    struct differential_range {
      public:
        using base_iterator = typename boost::range_iterator<R const>::type;
        struct iterator : boost::iterator_facade<iterator, int, typename boost::iterator_category<base_iterator>::type, int>
        {
            iterator(base_iterator raw) : _raw(raw) {}

          private:
            friend class boost::iterator_core_access;

            bool equal(iterator other) const { return _raw == other._raw; }
            void decrement() { --_raw; }
            void increment() { ++_raw; }
            int dereference() const { return *next() - *_raw; }
            ptrdiff_t distance_to(iterator other) const { return std::distance(_raw, other._raw); }

            base_iterator _raw;
            base_iterator next() const { return std::next(_raw); }
        };
        using const_iterator = iterator;

        differential_range(R &r) : _b(boost::begin(r)), _e(boost::end(r)) {
            if (_b != _e)
                --_e;
        }

        const_iterator begin() const { return _b; }
        const_iterator end()   const { return _e; }
        iterator begin() { return _b; }
        iterator end()   { return _e; }
      private:
        iterator _b, _e;
    };

没什么特别的。现在我们需要安装转发器，以便我们可以使用| differential语法简写：

    namespace detail {
        struct adjacent_difference_forwarder {
        };
    }

    template <class BidirectionalRng>
    inline differential_range<BidirectionalRng> operator|(BidirectionalRng &r,
                                                                 detail::adjacent_difference_forwarder) {
        return differential_range<BidirectionalRng>(r);
    }

    template <class BidirectionalRng>
    inline differential_range<const BidirectionalRng> operator|(const BidirectionalRng &r,
                                                                       detail::adjacent_difference_forwarder) {
        return differential_range<const BidirectionalRng>(r);
    }

    static const detail::adjacent_difference_forwarder differential = {};
} }

演示

foo这个演示程序测试了 100 个不同的随机范围以获得正确的结果：它运行来自问题 ( ) 和范围化版本 ( )的原始算法foo_ex并验证结果。

住在科利鲁

#include <vector>
#include <vector>
#include <algorithm>
#include <cassert>

template <typename Range>
int64_t foo(Range const& X, Range const& Y) {
    assert(Y.size() == X.size());
    size_t const l = X.size();

    int64_t ans = 0;
    for (size_t i=0; i<l-1; ++i) {
        ans = ans + std::max(std::abs(X[i]-X[i+1]), std::abs(Y[i]-Y[i+1]));
    }

    return ans;
}

#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/combine.hpp>
#include <boost/range/numeric.hpp>
#include <boost/iterator/iterator_facade.hpp>
using namespace boost::adaptors;

namespace boost { namespace adaptors {
    template <typename R>
    struct differential_range {
      public:
        using base_iterator = typename boost::range_iterator<R const>::type;
        struct iterator : boost::iterator_facade<iterator, int, typename boost::iterator_category<base_iterator>::type, int>
        {
            iterator(base_iterator raw) : _raw(raw) {}

          private:
            friend class boost::iterator_core_access;

            bool equal(iterator other) const { return _raw == other._raw; }
            void decrement() { --_raw; }
            void increment() { ++_raw; }
            int dereference() const { return *next() - *_raw; }
            ptrdiff_t distance_to(iterator other) const { return std::distance(_raw, other._raw); }

            base_iterator _raw;
            base_iterator next() const { return std::next(_raw); }
        };
        using const_iterator = iterator;

        differential_range(R &r) : _b(boost::begin(r)), _e(boost::end(r)) {
            if (_b != _e)
                --_e;
        }

        const_iterator begin() const { return _b; }
        const_iterator end()   const { return _e; }
        iterator begin() { return _b; }
        iterator end()   { return _e; }
      private:
        iterator _b, _e;
    };

    namespace detail {
        struct adjacent_difference_forwarder {
            bool absolute = false;
        };
    }

    template <class BidirectionalRng>
    inline differential_range<BidirectionalRng> operator|(BidirectionalRng &r,
                                                                 detail::adjacent_difference_forwarder) {
        return differential_range<BidirectionalRng>(r);
    }

    template <class BidirectionalRng>
    inline differential_range<const BidirectionalRng> operator|(const BidirectionalRng &r,
                                                                       detail::adjacent_difference_forwarder) {
        return differential_range<const BidirectionalRng>(r);
    }

    static const detail::adjacent_difference_forwarder differential = {};
} }

template <typename Range>
int64_t foo_ex(Range const& X, Range const& Y) {
    auto abs = transformed([](auto x) { return std::abs(x); });

    return boost::accumulate(
            boost::combine(X|differential|abs, Y|differential|abs),
            0ull,
            [](auto accum, auto const& xy) { return accum + std::max(boost::get<0>(xy), boost::get<1>(xy)); }
        );
}

#include <iostream>
#include <random>

int main() {
    std::vector<int> x(100), y=x;

    std::mt19937 rng { std::random_device{}() };
    std::uniform_int_distribution<int> dist(-50, 50);
    auto gen = [&] { return dist(rng); };

    int n = 100;
    while (n--) {
        std::generate(x.begin(), x.end(), gen);
        std::generate(y.begin(), y.end(), gen);

        auto ans = foo(x,y),
             ans_ex = foo_ex(x,y);

        std::cout << ans << " " << ans_ex << "\t" << std::boolalpha << (ans==ans_ex) << "\n";
    }
}

打印正确的结果，例如：

4769 4769   true
5027 5027   true
4471 4471   true
4495 4495   true
4774 4774   true
4429 4429   true
4331 4331   true
4951 4951   true
4095 4095   true
...

想法，总结

您可能可以differential更一般地想象... adjacent_transformed，您可以在哪里说

auto differential = adj_transformed([](auto x, auto y) { return y - x; });

这将使代码重用变得更加容易，不需要为任何新的相邻二进制变换使用全范围适配器。有关指导，请参阅第 3.2 节。

score -1 · Accepted Answer

现在它可能对实际生产代码有帮助，也可能没有帮助，但这似乎可以通过v3 Range 库得到解决，这是最终将成为标准库一部分的原型。

范围相对于迭代器的最大优势在于它们的可组合性。它们允许一种函数式编程风格，其中数据通过一系列组合器进行操作。此外，组合器可以是惰性的，仅在请求答案时才工作，并且纯粹是功能性的，不会改变原始数据。

这个介绍页面上的第一个例子是管道操作在一起，记录的第一件事（字母顺序的意外）是view::adjacent_filter.

我还没有安装并尝试过它并学习了如何编写这个特定的示例，但我确实认为这是缺失的部分。我只是希望它在今天的代码中足够有用。

c++ - “使用算法；不要为多步逻辑编写代码？

2 回答 2

`abs`

`differential`

演示

想法，总结

c++ - “使用算法；不要为多步逻辑编写代码？

2 回答 2

abs

differential

演示

想法，总结

Related

Reference

`abs`

`differential`