Algorithm for function evaluation by pairs (C++, STL)

Question

I need to apply a custom func to an STL containers by pairs -> that is:

// 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 resolve into something like this:

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

(I am sure this kind of algorithm has a proper name but I have no idea what this may be)

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

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

which is more less the same I can get with

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

I browsed STL and Boost, but did not manage to find something relevant. Is there any library that provides such an algorithm? If not, any ideas for a good STL compliant implementation?

EDIT Just to add that I'm not really interested in adding the elements in the traditional sense - in that case order does not really matter. My function will do a more complex, weighted, kind of summation and will give different results if carried out this way. My question is more generic nevertheless.

Answer 1

Here's my attempt at an STL-compatible solution, at 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;
}

Live on coliru also,

it gives this as the final output:

36
0

I believe this indicates that it is correct:

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 on ranges that are not a power of two is a bit ambiguous. In my version what I do is always split a range of length n at the first power of two less than n. So if you give it a power of two, you always get a perfectly balanced binary tree. If you give it 6, you get something like this:

        /\
    /\       /\
  /\  /\

However there's nothing that says always dividing by two is not also correct, so that you would get a tree structure like this

        /\
    /\       /\
  /\       /\

So IMO your question is a bit underspecified. Maybe it doesn't matter to you, so long as the depth is O(log n)?

Answer 2

Since November 2015 I had been working in a so called VectorFuncRange container that resolvs that in a STL style in C++14.

I did my own beta version that works good to imitate a std::vector container but with a func_range() method that returns in O(log n) a function evaluation in a range, evaluating as a tree. I endorse that even evaluating as a tree internally they are just vectors and has O(1) random access, push_back in amortized O(1) and worst scenario O(log n) and etc. Some std::vector methods are not yet programmed by me, as emplace_back() and different constructs, but the main ones to use as a vector are. For test reasons I compare the rang_func() with range_func_dumb(), the second version evaluate the function in linear order.

VectorFuncRange.h my current version: http://pastebin.com/dnwznUqg A test code that do it in 5 different ways, with integers, matrix and other types and a lot of functions: http://pastebin.com/YdRfN0CQ

I had think about put in a public Git, but I guess I should organized more my code before that and I do not know if other people have interest to contribute.

Answer 3

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

In pseudo-code near C++ 11, a STL implementation of your algorithm might 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];

There is obviously a cost to copy 'c' at start and partition 'tmp' into two halves at each iteration. You decide how to optimize from here :)