对（C ++，STL）的函数评估算法 [英] Algorithm for function evaluation by pairs (C++, STL)
问题描述
我需要将一个自定义 func 应用到对的STL容器中：
// if c => {a，b，c，d，e，f，g}; // a，b，c，..只是某些对象的别名
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兼容实现的任何想法？
EDIT
只是补充说，添加了传统意义上的元素 - 在这种情况下顺序并不重要。我的功能将做一个更复杂，加权，种类的总和，如果以这种方式进行，将给出不同的结果。
这是我尝试使用C ++ 11标准的STL兼容解决方案： / p>
#include< cassert>
#include< cmath>
#include< cstddef>
#include< array>
#include< iostream>
#include< iterator>
命名空间详细信息{
//返回严格小于n的第一个二的幂b $ b unsigned int pot_half（std :: ptrdiff_t n）{
断言（n> 1）;
return 1<< （static_cast< unsigned int>（ceil（log2（n））） - 1）;
}
} // end命名空间详细信息
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））;
默认值：{
迭代器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;
}
它将此作为最终输出：
36
0
我相信这表明这是正确的：
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
（（1-2） - （3-4）） - （（5-6） - （7-8））=
（（ - （（-1） - （-1））=
0 - 0 = 0
注意，不是2的幂的范围上的正确行为是有点模糊的。在我的版本中，我所做的总是分割一个长度 n 的范围，小于 n 。所以如果你赋予它的力量，你总是得到一个完美的平衡二叉树。如果你给它6，你会得到这样的：
/ \
/ \ / \
/ \ / \
但是没有什么说总是除以2也不是正确，以便您可以得到这样的树结构
/ \
/ \ / \ $所以IMO的问题有点欠缺了。也许对你没有关系，只要深度 O（log n）？
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.
解决方案 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;
}
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)?
这篇关于对（C ++，STL）的函数评估算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
