Have anybody written a C++ STL-compliant algorithm that combines std::transform
and std::accumulate
into a single pass algorithm supporting both the unary, binary and perhaps even (n-ary!) variant, say std::transformed_accumulate
? I want this because I have found this pattern highly reusable in for example linear algebra for example in (l1-)norm calculations. The l1-norm calculates the sum of the absolute values of the elements.
std::accumulate() is a built-in function in C++'s Standard Template Library. The function takes in a beginning iterator, an ending iterator, initial value, and (by default) computes the sum of the given initial value and the elements in the given range. The function can also be used for left folding.
As Scott Meyers puts it in Item 37 of Effective STL, std::accumulate is made to summarize a range. In other terms, this means that std::accumulate takes a collection of elements and returns only one value. If you don't specify anything, std::accumulate does the sum of all the elements in the range that it takes.
Transform-reduce is a pattern in which a set of data is first modified by applying a transformation on each of the elements and then it is reduced to a single value. In C++, this can be implemented straightforwardly with std::transform and std::accumulate.
It returns the result of accumulating all the values in the range [first,last) to init.
Uhm... My bet is that you can do that by embedding your transformation into the binary predicate, tranform the element and accumulate after the transformation.
struct times2accumulator {
int operator()( int oldvalue, int newvalue ) const {
return oldvalue + 2*newvalue;
}
};
int r = std::accumulate( v.begin(), v.end(), 2, times2accumulator() );
That functor would be equivalent to:
struct times2 {
int operator()( int x ) {
return 2*x;
}
};
std::vector<int> tmp; tmp.reserve( v.size() );
std::transform( v.begin(), v.end(), std::back_inserter(tmp), times2 );
int r = std::accumulate( tmp.begin(), tmp.end(), 0 );
Of course this could be made generic, just pass the transformation functor to a generic base functor:
template <typename Transform>
struct transform_accumulator_t {
Transform t;
transform_accumulator_t( Transform t ) : t(t) {}
int operator()( int oldvalue, int newvalue ) const {
return oldvalue + t(newvalue);
}
};
// syntactic sugar:
template <typename T>
transform_accumulator_t<T> transform_accumulator( T t ) {
return transform_accumulator_t<T>(t);
}
int r = std::accumulate(v.begin(), v.end(), 0, transform_accumulator(times2));
And you could also generalize on the type in the container... or even create a more generic transform_accumulator that takes both an accumulator and a transformation functors and applies them in order. Actual implementation left as an exercise for the reader.
Although it may not exactly fit the original intent, std::inner_product
is basically your binary version. You pass it an initial value, two ranges, and two functors, and it applies them as:
T acc = initial_value;
while (begin1 != end1) {
acc = binary_op1(acc, binary_op2(begin1, begin2);
++begin1;
++begin2;
return acc;
So, for your L1 you'd do something on this general order:
norm = std::inner_product(input1.begin(), input1.end(),
input2.begin(), input2.end(),
std::plus<int>(), std::abs);
Only that doesn't quite work -- right now, it's trying to pass std::abs
where you really need a binary function that combines the two inputs, but I'm not sure how the two inputs are really supposed to be combined.
std::partial_sum
is fairly close to your unary version, except that along with accumulating a result, it (attempts to) write out each intermediate result, not just the final result. To just get the final result, you'd have to write (and pass an instance of) a kind of do-nothing iterator that just holds a single value:
template<class T, class Dist=size_t, class Ptr = T*, class Ref = T&>
class unique_it : public std::iterator<std::random_access_iterator_tag, T, Dist, Ptr, Ref> {
T &value;
public:
unique_it(T &v) : value(v) {}
T &operator*() { return value; }
unique_it &operator++() { return *this; }
unique_it &operator+(size_t) { return *this; }
unique_it &operator++(int) { return *this; }
};
template <class T>
unique_it<T> make_res(T &v) { return unique_it<T>(v); }
With this, your L1 normalization would look something like this:
int main(){
double result=0.0;
double inputs[] = {1, -2, 3, -4, 5, -6};
std::partial_sum(
inputs, inputs+6,
make_res(result),
[](double acc, double v) {return acc + std::abs(v);});
std::cout << result << "\t";
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With