草庐IT

c++ - 成对函数评估算法(C++、STL)

coder 2024-02-03 原文

我需要将自定义 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 兼容实现的想法吗？

编辑 只是补充一点，我对添加传统意义上的元素并不感兴趣——在那种情况下，顺序并不重要。如果以这种方式执行，我的函数将进行更复杂的、加权的、某种求和，并会给出不同的结果。尽管如此，我的问题更为笼统。

最佳答案

这是我在 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;
}

Live on coliru also,

它给出了这个作为最终输出:

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。所以如果你给它一个二的幂，你总是会得到一个完美平衡的二叉树。如果你给它 6，你会得到这样的东西:

        /\
    /\       /\
  /\  /\

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

        /\
    /\       /\
  /\       /\

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

关于c++ - 成对函数评估算法(C++、STL)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35301733/

amp43codetempltc++algorithmc++11stlc++14

有关c++ - 成对函数评估算法(C++、STL)的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  3. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  4. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  5. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  6. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

  7. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  8. C51单片机——实现用独立按键控制LED亮灭（调用函数篇） - 2

    说在前面这部分我本来是合为一篇来写的，因为目的是一样的，都是通过独立按键来控制LED闪灭本质上是起到开关的作用，即调用函数和中断函数。但是写一篇太累了，我还是决定分为两篇写，这篇是调用函数篇。在本篇中你主要看到这些东西！！！1.调用函数的方法（主要讲语法和格式）2.独立按键如何控制LED亮灭3.程序中的一些细节（软件消抖等）1.调用函数的方法思路还是比较清晰地，就是通过按下按键来控制LED闪灭，即每按下一次，LED取反一次。重要的是，把按键与LED联系在一起。我打算用K1来作为开关，看了一下开发板原理图，K1连接的是单片机的P31口，当按下K1时，P31是与GND相连的，也就是说，当我按下去时

  9. ruby-on-rails - 将字符串转换为 ruby​​-on-rails 中的函数 - 2

    我需要一个通过输入字符串进行计算的方法，像这样function="(a/b)*100"a=25b=50function.something>>50有什么方法吗？ 最佳答案 您可以使用instance_eval:function="(a/b)*100"a=25.0b=50instance_evalfunction#=>50.0请注意，使用eval本质上是不安全的，尤其是当您使用外部输入时，因为它可能包含注入(inject)的恶意代码。另请注意，a设置为25.0而不是25，因为如果它是整数a/b将导致0(整数)。

  10. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

随机推荐