Algorithm for evaluating a function by pairs (C ++, STL)

Question

I need to apply custom func to STL containers in pairs → that are:

 // if c => {a,b,c,d,e,f,g}; // a,b,c,.. are just aliases for some object my_algorithm(c.begin(),c.end(),[](auto a, auto b){ a + b }); // c++14 

should allow something like this:

 temp1 = a + b; temp2 = c + d; temp3 = e + f; temp4 = temp1 + temp2; temp5 = temp3 + g; result = temp4 + temp5; 

(I'm sure this type of algorithm has its own name, but I have no idea what it could be)

I tried with std::accumulate , I'm not sure that its implementation is defined by the standard, but in my case and with my compiler, it seems to allow this (I think this is called pairwise summation, right?):

 temp1 = a + b; temp2 = temp1 + c; temp3 = temp2 + d; // etc 

which is less than what i can get with

 auto temp = c[0]; std::for_each(c.begin()+1,c.end(),[&temp](auto a){temp + a); // c++14 

I looked at STL and Boost, but could not find something important. Is there a library that provides such an algorithm? If not, any ideas for a good implementation of STL compatibility?

EDIT Just add that I'm not very interested in adding elements in the traditional sense - in this case, the order does not really matter. My function will perform more complicated weighted summation and will give different results if this is done. However, my question is more general.

Answer 1

Here is my attempt at a STL compatible solution in the C ++ 11 standard:

 #include <cassert> #include <cmath> #include <cstddef> #include <array> #include <iostream> #include <iterator> namespace detail { // Returns first power of two which is strictly less than n unsigned int pot_half(std::ptrdiff_t n) { assert(n > 1); return 1 << (static_cast<unsigned int>(ceil(log2(n))) - 1); } } // end namespace detail struct tree_fold_on_empty_range : std::exception {}; template <typename Iterator, typename F> auto tree_fold(const Iterator & begin, const Iterator & end, F && func) -> decltype(func(*begin, *end)) { std::ptrdiff_t diff = end - begin; switch (diff) { case 0: throw tree_fold_on_empty_range{}; // or, return {}; ? case 1: return *begin; case 2: return func(*begin, *(begin + 1)); default: { Iterator mid{begin}; std::advance(mid, detail::pot_half(diff)); return func(tree_fold(begin, mid, func), tree_fold(mid, end, func)); } } } int main() { for (uint n = 2; n < 20; ++n) { std::cout << n << " -> " << detail::pot_half(n) << std::endl; } std::cout << std::endl; std::array<int, 8> test{1, 2, 3, 4, 5, 6, 7, 8}; std::cout << tree_fold(test.begin(), test.end(), [](int a, int b){ return a + b; }) << std::endl; std::cout << tree_fold(test.begin(), test.end(), [](int a, int b){ return a - b; }) << std::endl; } 

In live on coliru mode,

he gives this as a final conclusion:

 36 0 

I believe this indicates correctness:

 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 ((1 - 2) - (3 - 4)) - ((5 - 6) - (7 - 8)) = ((-1) - (-1)) - ((-1) - (-1)) = 0 - 0 = 0 

Note that the “correct” behavior in non-power ranges is a bit ambiguous. In my version, what I am doing is always sharing a range of length n at the first power equal to two less than n . Therefore, if you give it a strength of two, you always get a perfectly balanced binary tree. If you give 6, you will get something like this:

  /\ /\ /\ /\ /\ 

However, nothing that says always dividing by two is also wrong, so you get a tree structure like this

  /\ /\ /\ /\ /\ 

So, with IMO, your question is a little vague. Maybe it doesn't matter to you if the depth is O(log n) ?

Answer 2

Since November 2015, I have been working in the so-called VectorFuncRange container, which allows this in STL style in C ++ 14.

I made my own beta version, which is good for simulating the std :: vector container, but using the func_range () method, which returns an O (log n) function rating in the range, evaluating it as a tree. I confirm that even judging as a tree inside, they are just vectors and have O (1) random access, push_back in depreciated O (1) and worst case scenario O (log n), etc. Some std :: vector methods have not yet been programmed by me, like emplace_back () and various constructions, but the main ones to use as a vector. For testing reasons, I compare rang_func () with range_func_dumb (), the second version evaluates the function in a linear order.

VectorFuncRange.h Current version: http://pastebin.com/dnwznUqg Test code that does this in different ways, with integers, matrix and other types and many functions: http://pastebin.com/YdRfN0CQ

I thought about publishing a publicly available Git, but I guess I had to organize more of my code before that, and I don't know if other people are interested in this.

Answer 3

You should take a look at the second form of std :: transform: http://www.cplusplus.com/reference/algorithm/transform/

In pseudocode near C ++ 11, the STL implementation of your algorithm may look like this:

 c = {a,b,c,d,e,f,g} // container of elements of type 'my_obj' tmp = {a,b,c,d,e,f,g} // copy of 'c' to not impact 'c' while executing algorithm while (tmp.size() > 1) { // partition 'tmp' into even index elements 'c1' and odd index elements 'c2' // first iteration would look like this : // c1 = {a,c,e,g} // c2 = {b,d,f,identity} where 'idendity' is a new element (when 'tmp' size is odd) to match 'g' without impacting final result... identity = 0 for integers addition :) // overwrite first elements of 'tmp' with intermediate results std::transform(c1.cbegin(), c1.cend(), c2.cbegin(), tmp.begin(), std::plus<my_obj>()); // replace std::plus with any other binary operation including any proper lambda // cut 'tmp' ununsed upper half tmp.resize(size_t(0.5 * (tmp.size() + 1))); } my_obj result = tmp[0]; 

Obviously, you should copy the 'c' at the beginning and the 'tmp' section into two halves in each iteration. You decide how to optimize here :)

Answer 4

Given the number of proposed solutions (in particular, Chris Beck's), I came up with this algorithm , which I am currently trying to optimize. I moved this to another thread, because the code reveals a number of issues that are worth discussing on their own respect, I think.