成对的功能评估算法(C++,STL)

Question

我需要成对地将一个自定义func应用于STL容器- >即:

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

应该解决这样的事情:

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

(我确信这种算法有一个合适的名称,但我不知道这可能是什么)

我试过std::accumulate,我不确定它的实现是否由标准定义,但在我的情况下和我的编译器似乎解决了这个问题(我认为这称为成对求和,对吧？):

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

这与我能得到的相同

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

我浏览了STL和Boost,但没有找到相关的东西.有没有提供这种算法的库？如果没有,任何关于良好的STL兼容实现的想法？

编辑 只是补充说我对添加传统意义上的元素并不感兴趣 - 在这种情况下,顺序并不重要.我的函数将执行更复杂,加权,类型的求和,并且如果以这种方式执行将给出不同的结果.不过,我的问题更为通用.

Answer 1

这是我在 C++11 标准上尝试的 STL 兼容解决方案：

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

也生活在 coliru 上，

它给出了最终输出：

36
0

我相信这表明它是正确的：

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

请注意，在不是 2 的幂的范围上的“正确”行为有点含糊。n在我的版本中，我所做的总是以小于 2 的一次幂来分割长度范围n。因此，如果你给它2的幂，你总是会得到一个完美平衡的二叉树。如果你给它 6，你会得到这样的结果：

        /\
    /\       /\
  /\  /\

然而，没有什么说总是除以二是不正确的，所以你会得到像这样的树结构

        /\
    /\       /\
  /\       /\

所以我认为你的问题有点不明确。也许这对你来说并不重要，只要深度就可以了O(log n)？