“use algorithms; don’t write code” for multi-step logic?

Question

This question makes me think “don’t use an explicit loop at all! Use STL/Boost algorithms” but looking in detail, I note that there is an adjacent_difference, and accumulate and Boost has a zip somewhere,

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

They simply don’t stack together but each can only make a whole pass by itself. So using them in the straightforward way would require a number of intermediate copies containing partial results. That is, have adjacent_difference write a new vector which is the argument of zip, etc.

Now in “modern” C++ the mantra is that we should not be “writing code” and seldom need an explicit loop.

But my real-world experience is more like this case: the thing to be done is not a simple step and the results are not gathered in a batch like that.

So, how can this be written in a streamlined way, referring to operations to perform but not looping over the ranges and not pulling each element explicitly.

Boost iterator filters can in general build up more complex logic that ends up inside the driving loop (so no whole-thing-copy for intermediate results) but this example has several features illustrating what I find limiting with Boost range filters too! And setting it up is more complex than just writing the for loop!

So, if the C++ “who’s who” say that we should be able to write that way with new language and library features, how do you do that here, a simple case that’s more real-world than they show in their lectures?

Answer 1

Using just Boost Range, you would like to write:

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

This can be achieved, with a little bit of handy-work.

---

abs

A range adaptor for absolute values

I cheat a bit here, because I don't want to go through the trouble to create a real adaptor range here:

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

That's all.

---

differential

A range adaptor for adjacent_difference

Note that I didn't copy the behaviour of std::adjacent_difference as it includes the first source value in the result (which we do not want). We, instead, want n-1 differential values.

I've taken the instructions from §3.1 in the docs, combined with a bit of 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;
    };

Nothing special. Now we need to rig up the forwarder so we can use the | differential syntax shorthand:

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

DEMO

This demo program tests 100 different random ranges for correct results: it runs the original algorithm from the question (foo) and the Range-ified version (foo_ex) and verifies the result.

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

Printing correct results like:

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
...

---

Thoughts, Summary

You could probably imagine differential more generically like... adjacent_transformed, where you could say

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

This would make code re-use a lot easier, not requiring a full-on range adaptor for any new adjacent-binary transform. See §3.2 for guidance.

Answer 2

It may or may not help with real production code now, but this seems to be addressed squarely with v3 Range library, a prototype for what will be part of the standard library eventually.

The big advantage of ranges over iterators is their composability. They permit a functional style of programming where data is manipulated by passing it through a series of combinators. In addition, the combinators can be lazy, only doing work when the answer is requested, and purely functional, without mutating the original data.

The very first examples on this intro page is piping operations together, and the first thing documented (an accident of alphabetical order) is view::adjacent_filter.

I have not installed and tried it and learned how to code this specific example yet, but I do think that this is the missing piece. I just hope it’s usable enough in today’s code.