"use algorithms, not write code" for multi-step logic?
This question makes me think, "Don't use an explicit loop at all! Use STL / Boost algorithms", but, in detail, I note that there is adjacent_difference
and accumulate
, and Boost is zip
somewhere,
while (i<l-1){
ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
i++;
}
They just don't fold, but each can only make one pass. Therefore, using them in a simple way would require several intermediate copies containing partial results. That is, adjacent_difference writes a new vector, which is the zip argument, and so on.
Now the mantra in "modern" C ++ is that we shouldn't "write code" and rarely need an explicit loop.
But my real experience is more like this case: the thing to be done is not an easy step, and the results are not collected in such a batch.
So how can this be written in a streamlined way, referencing the operations to be performed, but not looping through the ranges and not pulling out each element explicitly.
Boost iterator filters can generally create more complex logic that ends up inside an excitation loop (so there is no solid copy for intermediate results), but this example has several functions to illustrate what I find by limiting the Boost! And setting it up is harder than just writing a loop for
!
So if C ++ "who" says that we should be able to write this way with new language and library functions, how do you do it, a simple case, more real than they show in their lectures
source to share
Using only 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 practicality.
abs
Range adapter for absolute values
I'm cheating a little here because I don't want to bother creating a real range of adapters here:
auto abs = transformed([](auto x) { return std::abs(x); });
What all.
differential
Range adapter for adjacent_diff
Note that I have not copied the behavior std::adjacent_difference
, as it includes the first original value in the result (which we don't need). Instead, we want to get n-1 differential values.
I took the §3.1 instructions in the docs , combined with a bit 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 set up the forwarder so that we can use the shorthand syntax | 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 = {};
} }
DEMO
This demo tests 100 different random ranges for correct results: it runs the original algorithm from question ( foo
) and the range ( foo_ex
) version and checks the result.
#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";
}
}
Prints correct results such as:
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
Perhaps you could represent differential
more universally like ... adjacent_transformed
where you could say
auto differential = adj_transformed([](auto x, auto y) { return y - x; });
This will make code reuse much easier without requiring a full range adapter for any new adjacent binary conversion. See §3.2 for guidance.
source to share
Now it may or may not help with real production code, but this seems to be covered with the v3 Range library , a prototype for what will eventually become part of the standard library.
The big advantage of ranges over iterators is their compositional ability. They admit a functional programming style, where data is processed by passing it through a series of combinators. In addition, combinators can be lazy, perform work only when a response is requested, and purely functional, without altering the original data.
The earliest examples on this introductory page are pipeline operations and the first recorded (alphabetical accident) was view::adjacent_filter
.
I haven't installed or tried it, and have learned to code this particular example, but I think this is the missing piece. I just hope it can be used in today's code.
source to share