c++ - “use algorithms; don’ t 为多步逻辑编写代码？

Question

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

它们根本不堆叠在一起，但每个只能单独完成一次完整的传球。因此，以直接的方式使用它们需要大量包含部分结果的中间拷贝。也就是说，让 adjacent_difference 写入一个新 vector ，它是 zip 等的参数。

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

但我的实际经验更像是这种情况:要做的事情不是简单的一步，结果也不是那样成批收集的。

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

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

因此，如果 C++ “名人录”说我们应该能够使用新的语言和库功能以这种方式编写，那么此处您如何做到这一点，一个更真实的简单案例-世界比他们在演讲中展示的要多？

Answer 1

仅使用 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)); }
    );

这可以通过一些手工操作来实现。

---

绝对值

绝对值的范围适配器

我在这里有点作弊，因为我不想在这里创建一个真正的适配器范围:

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

就这些。

---

differential

adjacent_difference 的范围适配器

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

我已按照 §3.1 in the docs 中的说明进行操作, 结合一点 iterator_facade to reduce typing :

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

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

演示

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

Live On Coliru

#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寻求指导。