C++ 数值算法：accumulate、partial_sum 与 inner_product
07 数值算法：折叠、扫描与成对归约
下面这段代码能通过编译，运行也不会崩溃，但结果是错的（以下为片段）：
std::vector<double> values{0.5, 0.5, 0.5, 0.5};
int result = std::accumulate(values.begin(), values.end(), 0);
// result == 0
四个 0.5 相加应该得到 2.0，实际拿到的是 0。没有语法错误，没有运行时异常，编译器甚至不会给出警告。问题出在第三个参数：初始值写成了整数字面量 0，accumulate 从它推导出累计器类型为 int，每一步 int + double 的结果都被截断回 int。0 加 0.5 得到 0.5，截断后变成 0，下一个 0.5 面对的累计器仍然是 0，四轮下来结果纹丝不动。一行代码就能说明数值算法里最容易写错的地方：初始值不只是计算的起点，还是整个表达式的类型锚点。
本章涉及的三个算法——accumulate、partial_sum、inner_product——解决的是同一类问题：沿一段范围把元素逐个合并进一个累计状态。accumulate 只交出最终状态，partial_sum 把每一步的中间状态写进输出范围，inner_product 同时走两段范围、成对组合后再合并。它们共享三个核心参数：初始值决定起点状态和结果类型，组合规则决定每一步怎样把新元素并入，范围决定处理的起止位置。三个算法都定义在 <numeric> 头文件里，和前几章 <algorithm> 里的查询、排序、删除类算法不同，它们的返回值不是迭代器位置，而是计算结果本身。
accumulate 怎样把范围折叠成一个值
std::accumulate 的完整行为可以用三步描述：把初始值复制成一个局部的累计器，从 first 到 last 每遇到一个元素就执行一次 acc = op(acc, element)，遍历结束后把累计器按值返回。默认的组合规则是加法，所以最常见的用法是求和，但折叠（fold）这个模型比求和宽广得多——把 op 换成乘法就是连乘，换成字符串拼接就是把一段范围按顺序拼成一条文本，换成对结构体字段的更新就能把整批记录聚合进一个统计对象。算法本身对元素类型一无所知，语义完全由初始值和组合规则给出。
这个模型有几个容易被忽略的性质。折叠是严格从左到右进行的，标准保证每一步按范围顺序依次应用组合规则。对字符串拼接、浮点求和这类不满足交换律或结合律的操作，顺序保证意味着同一份输入永远得到同一个结果。accumulate 只要求输入迭代器（Input Iterator），单趟扫描、只读前进就够了，因此它能直接用在输入流迭代器这种只能走一遍的范围上，代价是不提供任何回退或提前退出的机制。空范围的行为也是自然定义的：没有元素可以合并时，返回值就是初始值本身。
初始值按值传入，返回值也按值交出，累计器在算法内部是一个独立的局部对象，调用方传入的那个初始值对象本身不会被修改。这使得 accumulate 成为一个纯粹的函数式接口：同样的输入范围加同样的初始值，永远得到同样的返回值，调用前后外部世界没有任何变化。复杂度的承诺也很直接——恰好对范围做一次线性扫描，元素有多少个组合规则就被调用多少次，不多不少。没有隐藏的状态，没有隐藏的分配，没有隐藏的额外遍历。
初始值为什么决定结果类型
accumulate 的返回类型由初始值的类型推导出来。写 0 就是 int，写 0.0 就是 double，写 0LL 就是 long long。更关键的是，截断发生在每一步而不是最后统一截断一次。开头那个例子里累计器是 int，每一步 acc + 0.5 在算术上得到 0.5，赋值回 int 立刻变成 0，下一个元素面对的累计器仍然是 0。哪怕范围里有一万个 0.5，结果也不会挪动分毫。修正方式只有一种：让初始值的类型表达你想要的结果精度。
整数场景里同一个机制换了另一副面孔。一批 int 元素的累加可能超出 int 的表示范围，有符号整数溢出在 C++ 里是未定义行为（Undefined Behavior），编译器可以假设它永不发生并据此优化，溢出后拿到的值没有任何可依赖的意义。把初始值写成 0LL，累计器就变成 long long，每一步 long long + int 自动按较宽类型计算，溢出的门槛被推远。具体来说，三个接近二十亿的 int 元素相加，数学结果大约六十亿，远超 int 大约二十一亿的上限，但初始值改成 0LL 之后每一步都在 long long 里进行，结果完全正常。两种写法只差两个字符，在小数据量的测试用例里都能通过，问题往往要到生产数据上才暴露。
标准把类型决定权交给初始值，而不是从元素类型自动推导，是刻意的选择。折叠的结果可以和元素类型完全不同：订单对象折叠出金额，日志条目折叠出统计报表，字符串片段折叠出哈希值。如果结果类型被锁死在元素类型上，这一类跨类型聚合全部写不出来。代价就是开头看到的那样：调用方给错类型，算法照单全收，编译器不会替你拦截。写 accumulate 调用时先确定结果应该是什么类型，再把初始值写成那个类型的字面量，这是一个值得固定下来的习惯。
初始值还可以是自定义类型的对象。要同时统计一批订单的总金额和最大单笔金额，可以定义一个包含两个字段的聚合结构体，初始值写成该结构体的零值状态，组合规则写成接收聚合对象和订单、返回更新后聚合对象的 lambda。C++20 起标准把每一步的合并明确规定为对累计器的移动赋值，累计器是大对象时不再产生逐步拷贝的开销，用重型对象当累计器也因此变得更实际。
partial_sum：保留折叠的每一步
accumulate 只交出终点状态，中间经过的每一步都被丢掉了。很多场景要的恰恰是中间过程：账户余额随流水的变化、订单金额随时间的累计曲线、用于快速回答区间和查询的前缀和（prefix sum）数组。std::partial_sum 做的就是保留中间结果的折叠，算法领域把这类操作叫作扫描（scan）。它把输入的第一个元素直接写入输出的第一个位置，之后每个输出位置写入到此为止的累计值。输入 {120, 80, 300} 得到的输出是 {120, 200, 500}，输出序列的最后一个元素恰好等于 accumulate 对同一段输入的返回值。
调用形式和第 05 章的 transform 类似：传入输入范围和输出起点，调用方负责保证输出空间足够，返回值是紧挨最后一个写入位置之后的输出迭代器。标准明确允许输出覆盖输入——std::partial_sum(v.begin(), v.end(), v.begin()) 可以原地把数组改成自己的前缀和，不需要临时数组。空范围同样安全，什么都不写，直接返回输出起点。
前缀和数组之所以值得专门生成，是因为它能把一类查询的成本压到常数时间。有了前缀和之后，任意一段连续子区间的元素和都可以用一次减法回答：区间终点之后的前缀值减去区间起点处的前缀值。报表系统里频繁出现的"某段时间的合计""某个区间的总量"，背后都是这个结构。手写循环当然也能在每次查询时重新累加，但那是把折叠的成本摊到每一次查询上；先做一次 partial_sum 等于一次性把中间结果缓存成数组，后续查询全部走减法。折叠和扫描在这里的分工可以归结为：折叠交付最终状态，扫描交付全部中间状态，选哪个取决于调用方需要查一次还是需要查多次。
<numeric> 里还有一个方向相反的成员：std::adjacent_difference 对每个位置写入当前元素与前一个元素的差值，恰好是 partial_sum 的逆操作——对前缀和数组做 adjacent_difference 能还原出原始序列。这两个算法加上生成递增序列的 std::iota，共同点是都在范围上维护一个随位置推进的状态。
inner_product：同时走两段范围
std::inner_product 在折叠模型上加了一个维度：它同时遍历两段范围，每一步从两边各取一个元素，先用一个二元操作把这对元素组合起来，再用另一个二元操作把组合结果合并进累计器。默认规则是先乘后加，inner_product(a.begin(), a.end(), b.begin(), 0.0) 计算的是 a[0]*b[0] + a[1]*b[1] + ...，即数学上的点积（dot product）。价格乘数量求货款、权重乘分数求加权总分、特征向量乘系数向量求线性模型输出，都是这个形状。
这个算法的签名里藏着一个真实的边界：第二段范围只传起点，不传终点。标准不提供长度检查，它假定从 first2 开始至少有和第一段范围同样多的元素。如果第二段范围短了，算法会安静地读到不属于调用方的内存，不会报错也不会抛异常，后果是未定义行为。调用 inner_product 之前确认两段范围的长度关系，是调用方自己的责任。
顺序保证和 accumulate 一致：成对元素按下标依次组合，合并进累计器的方向也是从左到右。两段范围可以来自不同类型的容器，价格放在 vector<double> 里、数量放在 deque<int> 里完全没有问题，算法对两边各自只要求能单趟前进的迭代器。甚至两段范围可以指向同一个容器——对一段范围和自身做 inner_product 得到的是平方和，这在向量范数和方差计算里是常见的中间量。
和 accumulate 一样，inner_product 也能替换规则，而且一次能换两个：第一个可调用对象替换累加的加法，第二个替换成对的乘法。初始值的角色没有任何变化，它依然同时担任起点状态和类型锚点，前面关于 0 和 0.0 的结论在这里原样成立。
代码示例
本章示例文件是 代码示例/07-numeric-accumulate/numeric_accumulate.cc，在一个程序里同时展示折叠和扫描，运行后可以直接验证两者的结果关系。
// Copyright (c) 2026 yus3nable
// SPDX-License-Identifier: MIT
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
struct Order {
std::string id;
int amount = 0; // 金额，单位：分
};
int main() {
const std::vector<Order> orders{{"a", 120}, {"b", 80}, {"c", 300}};
// accumulate：把订单范围折叠成总金额
// 第一个参数 sum 是累计器，第二个参数 order 是当前元素
const int total = std::accumulate(
orders.begin(), orders.end(), 0,
[](int sum, const Order& order) { return sum + order.amount; });
std::cout << "total: " << total << '\n';
// 为 partial_sum 准备纯数值范围
std::vector<int> amounts;
amounts.reserve(orders.size());
for (const Order& order : orders) {
amounts.push_back(order.amount);
}
// partial_sum：保留每一步的累计值
std::vector<int> prefix(amounts.size());
std::partial_sum(amounts.begin(), amounts.end(), prefix.begin());
std::cout << "prefix:";
for (int value : prefix) {
std::cout << ' ' << value;
}
std::cout << '\n';
// 前缀和的最后一个元素应当等于 accumulate 的返回值
std::cout << "prefix.back() == total: "
<< (prefix.back() == total ? "yes" : "no") << '\n';
}
运行输出：
total: 500
prefix: 120 200 500
remaining: prefix.back() == total: yes
Order 结构体模拟的是真实代码中的常态：需要汇总的数值埋在对象的某个字段里，元素本身并不能直接相加。accumulate 调用因此传入了自定义 lambda，lambda 的第一个参数 sum 是到目前为止的累计状态，第二个参数 order 是当前元素，返回值成为下一步的累计状态——这个参数顺序是固定的，对加法和乘法这种满足交换律的操作写反了看不出来，对字符串拼接或结构体聚合这种左右有区分的操作写反了结果就是错的。初始值写成 0 在这里没有风险，因为订单金额本来就是 int，类型锚点和字段类型一致。如果 amount 字段改成 double，这个 0 就必须跟着改成 0.0，否则开头演示的逐步截断就会在这行代码里复现。
中间那段手写循环把订单里的金额抽取到独立的 amounts 数组，这是为 partial_sum 准备纯数值输入。这一步映射用第 05 章的 transform 更贴切，示例保留成普通循环是为了让数据流更显眼。prefix 预先开好和输入等长的空间，partial_sum 从 prefix.begin() 开始依次写入三步累计值。最后一行验证了 prefix.back() 与 total 严格相等——折叠和扫描走的是同一条按顺序合并的路径，区别只在于一个丢弃了中间状态、一个把中间状态保留下来。
自定义组合规则的写法约束
三个算法替换组合规则的方式是统一的：多传一个可调用对象，算法每一步调用它来替代默认的加法或乘法。写法上最容易出错的就是参数顺序，上一节已经提到：accumulate 的组合规则永远按 op(累计器, 元素) 调用，累计器在左，元素在右。
标准对组合规则还有两条硬性约束：它不能修改范围里的元素，也不能让迭代器失效。这两条把一类写法挡在了门外——在规则里顺手给元素打标记、往正在遍历的容器里追加元素，都属于越过契约的行为。规则对象应该只读取元素、返回新状态，把范围本身当作只读输入。
从工程角度看，规则的长度和复用频率决定了它应当以什么形态出现。只有一行的临时逻辑写成调用点上的 lambda 最经济，上面示例里的金额提取就是这种形态；规则长到需要两三个中间变量才能读清，或者同一条规则在多个归约里反复出现时，应该给它一个名字，提成普通函数或者函数对象。还有一个容易踩的细节：对 int、double 这类小类型，lambda 参数按值还是按引用影响不大；对字符串、容器这类大对象，把元素参数声明成 const 引用可以避免每一步合并伴随一次不必要的拷贝。这是零成本的习惯，值得在写法上固定下来。
浮点求和为什么对顺序敏感
整数折叠的主要风险是溢出，浮点折叠的主要风险是顺序。浮点加法不满足结合律，(a + b) + c 和 a + (b + c) 的结果可能不同，差距会随数据规模放大。背后的物理机制是有效位数有限导致的吞没：累计器涨到很大之后，绝对值很小的元素加进去会因为对齐指数时低位被丢弃而部分甚至全部消失。先加一堆小数再加一个大数，和先加大数再加一堆小数，最终结果可能肉眼可见地不同。
accumulate 保证从左到右的固定顺序，因此同一份输入在同一台机器上反复运行结果稳定。这种稳定性对回归测试和对账系统是刚需，但它保证的是可复现，不是数学上最精确。想让浮点求和更准确，有几条常见路径：用 long double 做累计器（初始值写 0.0L）是最便宜的一档精度提升；按绝对值从小到大排序后再累加，能减轻大数吞没小数的程度；要求更高时有 Kahan 补偿求和这类专门算法，把每一步丢失的低位记进一个补偿项，在下一步加回来。标准库算法本身不对精度做任何承诺，它只承诺按给定顺序执行给定规则。
C++17 在 <numeric> 里增加了 std::reduce，做的是同一件折叠工作，但故意松开了顺序约束：标准允许实现把元素重新分组、并行计算，前提是调用方给出的组合规则满足结合律和交换律。对浮点加法这种不满足结合律的规则，reduce 的结果允许在不同实现或不同运行之间变化；对整数加法这种严格可结合的运算，它换来的是并行加速的可能。判断标准可以在这里建立：要严格复现的顺序归约用 accumulate，规则可结合且愿意接受浮点结果波动时才考虑 reduce。reduce 和配套的 transform_reduce 以及执行策略属于并行算法的范畴，本系列不展开。
浮点顺序问题还有一种工程上更彻底的规避方式：能用整数就不用浮点。金额、库存、配额这类需要严格对账的场景，业界常见做法是用整数保存最小单位——分代替元、厘代替分——整个归约过程在整数域进行，结合律严格成立，任何顺序都得到同一个结果，展示时再换算回带小数的格式。上面代码示例里 Order::amount 用 int 表示分而不是 double 表示元，就是这个思路的落地。浮点留给真正需要连续量的物理计算、图形和统计场景，整数留给需要严格对账的业务场景，这个分工比任何求和精度技巧都更能从根源上消除问题。
工程判断
判断是否该用数值算法和前几章的标准一致：如果一段代码的意图是"沿范围方向把元素合并进一个累计状态"，而且组合规则可以用一个短小的可调用对象表达，accumulate 就比手写循环更直接。读者看到 accumulate，注意力自然落到初始值类型和组合规则两个检查点上；看到手写的 for 循环加一个累加变量，就需要先通读循环体才能确认这段代码到底是在求和、求最大值、拼接字符串还是做别的事。
手写循环更合适的场景是：累计过程中需要提前退出（遇到某个条件就停下来），需要同时维护多个互相影响的状态，或者每一步的控制路径依赖前一步的结果而无法用一个固定签名的组合规则表达。accumulate 的设计契约是"从头到尾每个元素都走一遍，没有跳过也没有回退"，一旦业务逻辑需要中途改变遍历方向或者在不同元素上执行不同的合并策略，循环的控制流表达能力就更合适。
性能方面，标准算法和等价的手写循环之间通常没有天然差距，编译器会把 accumulate 内联展开成和手写循环相近的机器码。真正可能产生成本的是组合规则中的间接调用（如通过 std::function 而不是 lambda 传入规则）、累计器是大对象时的拷贝开销（C++20 之前每一步可能产生一次拷贝）、以及算法链之间产生不必要的中间容器。这些开销不来自算法本身，而来自调用方对规则对象、初始值类型和数据布局的选择。
总结
前几章的算法——find_if、sort、remove_if——在范围上查询、重排、压缩元素，返回的是迭代器位置或重排后的逻辑尾。本章的数值算法在范围上做另一件事：把元素沿遍历方向逐步合并进一个状态，返回的是计算结果本身。两类算法共享同一个结构——范围在参数里，规则在可调用对象里，算法名字表达意图——但对范围的使用方式不同，一类是在范围里选位置，另一类是沿范围做归约。
本章的可调用对象都还很轻：一个提取字段的 lambda，一个加法，一个乘法。真实代码里的组合规则会变重——要读外部的汇率表、要跳过特定状态的记录、要带配置参数——这些都要求规则对象从调用点拿到外部状态。lambda 靠什么机制拿到外部变量、捕获列表里的每个名字到底在闭包对象里变成了什么，是下一章的主题。
阅读导航
