Chapter 32: Numeric Algorithms
核心问题与阅读主线
数值算法以区间为输入,却产出三类不同结构的结果:单值归约、前缀序列与相邻差分。工程选型的关键在于先锁定输出形态与计算顺序,再核对累加类型、二元操作可重排性与执行策略边界,防止静默截断、整数溢出或并行浮点漂移。
全章共用代码样本(下文各节持续拆解)
贯穿本章的材料是一组账户每日净变动 daily_delta 与每日评分权重 day_weight。基准代码用 long long 承接累加结果,同时演示单值归约、前缀序列与双区间变换归约(类型与溢出边界见 32.5):
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> daily_delta{120, -40, 30, 50, -20};
std::vector<int> day_weight{1, 2, 1, 3, 2};
long long total = std::accumulate(daily_delta.begin(), daily_delta.end(), 0LL);
std::vector<long long> running_balance(daily_delta.size());
std::partial_sum(daily_delta.begin(), daily_delta.end(), running_balance.begin());
long long weighted_score = std::inner_product(
daily_delta.begin(), daily_delta.end(),
day_weight.begin(),
0LL
);
std::cout << total << '\n'; // 140
std::cout << weighted_score << '\n'; // 180
}
仅看函数名容易混淆语义:total 是单值归约,running_balance 是前缀序列,weighted_score 是双区间成对变换后的单值结果。
C++17 引入了 std::reduce、scan 系列与 std::transform_reduce;C++20 起 std::accumulate、std::inner_product、std::partial_sum 与 std::adjacent_difference 等顺序重载支持 constexpr。接口细节见 cppreference 的 std::accumulate、std::reduce、std::inclusive_scan、std::adjacent_difference 与 std::transform_reduce。
32.1 accumulate、reduce 与 inner_product
归约(reduction)把一个或两个同步区间合并为单个值。选型取决于累加器类型、遍历顺序与操作是否允许重排。
std::accumulate 是严格顺序左折叠(C++20 起移动更新累加器并支持 constexpr),直接带来两个约束:init 的类型决定累加器类型;二元操作可依赖左到右顺序,适合字符串拼接、流水日志合成与带状态合并。
template <class InputIt, class T, class BinaryOp>
T fold_left_like(InputIt first, InputIt last, T init, BinaryOp op) {
for (; first != last; ++first) {
init = op(std::move(init), *first);
}
return init;
}
std::reduce 允许未指定分组与并行执行策略(<execution>),要求二元操作满足结合律与交换律语义。无溢出整数加法满足该前提;浮点加法会因分组改变舍入最低位,文本拼接更会随分组破坏顺序,因此必须留在 std::accumulate:
#include <numeric>
#include <string>
#include <vector>
int main() {
std::vector<std::string> pieces{"A", "B", "C"};
std::string stable = std::accumulate(
pieces.begin(), pieces.end(), std::string{},
[](std::string acc, const std::string& value) {
return std::move(acc) + value;
}
);
}
std::inner_product 将 [first1, last1) 与 [first2, ...) 按位置配对,顺序执行“成对变换 → 归约合并”。第二区间从 first2 起必须至少提供 last1 - first1 个可读元素;自定义重载支持分别替换归约与成对变换操作。
#include <numeric>
#include <vector>
int main() {
std::vector<int> daily_delta{120, -40, 30, 50, -20};
std::vector<int> day_weight{1, 2, 1, 3, 2};
long long weighted_score = std::inner_product(
daily_delta.begin(), daily_delta.end(),
day_weight.begin(),
0LL
);
// 120*1 + (-40)*2 + 30*1 + 50*3 + (-20)*2 == 180
}
| 算法 | 输入区间 | 执行顺序与并行 | 默认操作 | 适用场景 |
|---|---|---|---|---|
std::accumulate | 单区间 | 严格左到右,仅顺序 | std::plus<> | 字符串拼接、顺序敏感统计、精确浮点复现 |
std::reduce | 单区间 | 允许未指定分组与并行重排 | std::plus<> | 大规模可结合可交换数值汇总 |
std::inner_product | 双区间(第二区间至少等长) | 严格左到右,仅顺序 | 先 * 后 + | 点积、加权评分、双序列顺序变换归约 |
核心判断
操作依赖左到右顺序或禁止浮点重排漂移时选用 std::accumulate / std::inner_product,仅当操作满足结合律与交换律时才启用 std::reduce;自定义 std::inner_product 需注意参数顺序为归约 reduce 在前、变换 transform 在后。
32.2 partial_sum、exclusive_scan 与 inclusive_scan
前缀算法把长度为 N 的输入映射为等长阶段累计序列,在贯穿材料中对应每日收盘余额。
std::partial_sum 按输入顺序维护累加器并写出每步结果,输入 {120, -40, 30, 50, -20} 输出 {120, 80, 110, 160, 140}(第 i 项即前 i + 1 天净变动之和):
#include <numeric>
#include <vector>
int main() {
std::vector<int> daily_delta{120, -40, 30, 50, -20};
std::vector<int> running_balance(daily_delta.size());
std::partial_sum(daily_delta.begin(), daily_delta.end(), running_balance.begin());
// running_balance == {120, 80, 110, 160, 140}
}
C++17 引入的 scan 系列面向前缀并行化:
std::inclusive_scan:输出包含当前元素;支持可选init(位于binary_op之后),带执行策略重载要求前向迭代器与可重分组操作。std::exclusive_scan:输出不含当前元素,必须提供init作为首项基准;上例以init = 0输出{0, 120, 80, 110, 160}(当日开盘前余额),用于偏移表、前缀索引、分桶写位置与批量容量分配。
#include <numeric>
#include <vector>
int main() {
std::vector<int> daily_delta{120, -40, 30, 50, -20};
std::vector<int> before_day(daily_delta.size());
std::vector<int> end_of_day(daily_delta.size());
std::exclusive_scan(daily_delta.begin(), daily_delta.end(), before_day.begin(), 0);
std::inclusive_scan(daily_delta.begin(), daily_delta.end(), end_of_day.begin());
// before_day == {0, 120, 80, 110, 160}
// end_of_day == {120, 80, 110, 160, 140}
}
| 算法 | 包含当前项 | init 参数 | 执行策略 | 累加器类型来源 | 典型场景 |
|---|---|---|---|---|---|
std::partial_sum | 是 | 不支持 | 仅顺序 | 输入 value_type | 严格顺序时间序列累计 |
std::inclusive_scan | 是 | 可选(位于操作后) | 支持(需前向迭代器) | 无 init 用输入类型,否则用 init | 可并行闭区间前缀聚合 |
std::exclusive_scan | 否 | 必选(首项输出) | 支持(需前向迭代器) | init 类型 | 偏移表、分桶索引、容量分配 |
核心判断
先看是否包含当前项(包含用 partial_sum / inclusive_scan,不含用 exclusive_scan);需要外部 init 基准或并行重排选 scan 系列,要求严格左到右语义(如时序或精准浮点)选 std::partial_sum。
边界与误区
输出区间必须至少可写入 N 个元素(N 为输入长度)。标准虽允许 d_first == first 原地覆写,但部分重叠属未定义行为;日常工程应独立分配输出容器,消除别名风险并方便调试对比。
32.3 adjacent_difference
std::adjacent_difference 原样输出首项,从第二项起写出相邻元素之差。在无溢出整数加法下,它与 std::partial_sum 互为逆运算——对前缀余额做差分即可恢复每日净变动:
#include <numeric>
#include <vector>
int main() {
std::vector<int> running_balance{120, 80, 110, 160, 140};
std::vector<int> recovered_delta(running_balance.size());
std::adjacent_difference(
running_balance.begin(), running_balance.end(),
recovered_delta.begin()
);
// recovered_delta == {120, -40, 30, 50, -20}
}
自定义二元操作接收 (current, previous),适用于增长率、状态迁移或相邻变化标签:
#include <numeric>
#include <vector>
int main() {
std::vector<int> balance{100, 120, 90, 90, 160};
std::vector<int> direction(balance.size());
std::adjacent_difference(
balance.begin(), balance.end(), direction.begin(),
[](int current, int previous) {
if (current > previous) return 1;
if (current < previous) return -1;
return 0;
}
);
// direction[0] == 100,后续元素为 1、-1、0、1。
}
边界与误区
首项 output[0] 直接拷贝 *first 且不经过二元操作,因此自定义差分标签时需从第二项起消费或为首项单独赋义;同时实现按输入迭代器 value_type 缓存前驱值,遇到 char、short、定点数或强类型金额时须核对输入、操作返回与输出类型间的隐式转换。
32.4 transform_reduce 与并行算法基础
std::transform_reduce 将元素变换与归约合二为一,提供双区间(成对变换后归约,默认等价于 std::plus<> 与 std::multiplies<>,作 std::inner_product 的可并行对应物)与单区间(一元变换后归约)两种形式。下面将每日变动映射为加权绝对风险并汇总:
#include <cmath>
#include <numeric>
#include <vector>
struct DayRisk {
int delta;
int weight;
};
int main() {
std::vector<DayRisk> days{{120, 1}, {-40, 2}, {30, 1}, {50, 3}, {-20, 2}};
long long weighted_abs_risk = std::transform_reduce(
days.begin(), days.end(),
0LL,
std::plus<>{},
[](const DayRisk& day) {
return static_cast<long long>(std::abs(day.delta)) * day.weight;
}
);
// weighted_abs_risk == 420
}
带 <execution> 执行策略的重载允许实现重排分组并并行调度(但不保证一定启动线程)。下面的 std::execution::seq 显式固定为顺序执行:
#include <execution>
#include <numeric>
#include <vector>
int main() {
std::vector<int> values{1, 2, 3, 4, 5};
int sum_of_square = std::transform_reduce(
std::execution::seq,
values.begin(), values.end(),
0,
std::plus<>{},
[](int value) { return value * value; }
);
// sum_of_square == 55
}
把策略从 seq 切到 par 前,必须依次满足以下条件:
- 迭代器能力:带标准执行策略的重载通常要求前向迭代器,以支持区间拆分与多点定位。
- 无共享副作用:变换与归约函数对象不得读写共享可变状态(如向外部容器追加、改写输入或递增非原子计数器)。
- 可重排稳定性:归约操作需适合重新分组;浮点求和、字符串拼接与时序日志合并必须先评估漂移风险。
- 实测性能收益:前三条成立后再以基准测试验证,实际加速取决于数据规模、访存与调度开销。
排查顺序
审查 std::transform_reduce 时分别核对变换与归约两个可调用对象,切勿混为一谈;启用并行执行策略严格按“前向迭代器 → 无共享副作用 → 可重排性 → 基准测试”顺序逐项排除。
32.5 数值算法的类型和精度边界
数值算法的缺陷多源于类型边界与浮点重排,而非循环索引。标准库严格按照调用方提供的 init 与迭代器类型运算,不会自动把 int 提升为 long long。
单值归约的累加器类型由 init 实参决定。下面代码中的 auto 只承接返回值,真正触发整数截断的是第三个参数 0——代码审查应沿“初始值字面量 → 累加器类型 → 二元操作返回值 → 最终结果”整条链路追踪:
#include <numeric>
#include <vector>
int main() {
std::vector<double> ratios{0.1, 0.2, 0.3};
auto wrong = std::accumulate(ratios.begin(), ratios.end(), 0);
auto right = std::accumulate(ratios.begin(), ratios.end(), 0.0);
// wrong 为 int(小数被截断),right 为 double。
}
| 算法类别 | 代表算法 | 累加器 / 缓存类型来源 | 常见类型陷阱 |
|---|---|---|---|
| 单值归约 | accumulate、reduce、inner_product、transform_reduce | init 实参类型 | 传 0 导致 double 截断或大额整数溢出(应传 0.0 / 0LL) |
无 init 前缀和 | partial_sum、无 init 的 inclusive_scan | 输入迭代器 value_type | 输入为窄整数(如 int16_t、int)时累计溢出 |
带 init 扫描 | exclusive_scan、带 init 的 inclusive_scan | init 实参类型 | init 类型过窄会截断后续阶段值 |
| 相邻差分 | adjacent_difference | 输入 value_type 缓存前驱 | 输入、操作返回与输出类型不一致触发隐式转换 |
边界与误区
有符号整数溢出属于未定义行为(UB),无符号整数溢出按模运算回绕(合法但破坏金额语义);浮点加法不满足逐位结合律,std::reduce、scan 系列与并行策略产生的最低位差异属于规范行为,需要逐位复现时应改用 std::accumulate / std::partial_sum 或改用容差断言。
工程选型可按固定五步排查:
- 输出形态:单值归约、前缀序列还是相邻差分。
- 顺序语义:严格左到右、顺序前缀还是允许重分组。
- 类型来源:
init、输入value_type、输出value_type与操作返回类型转换链。 - 区间关系:输入长度、第二区间最小容量、目标可写长度与重叠约束。
- 执行策略:前向迭代器、无共享副作用、异常与结果稳定性。
核心判断
回到贯穿材料,上述五步直接锁定了所有实现选择:total 用 0LL 防溢出,running_balance 用 std::partial_sum 保留时间顺序,recovered_delta 用 std::adjacent_difference 逆推每日净变动,weighted_abs_risk 用 std::transform_reduce 合并映射与归约。
最小自检任务
阅读下面的代码,判断三个输出变量的类型和稳定性边界,并说明哪些地方需要修改才能让工程含义更清楚。
#include <numeric>
#include <vector>
int main() {
std::vector<double> values{0.1, 0.2, 0.3, 0.4};
std::vector<int> weight{1, 2, 3, 4};
auto a = std::accumulate(values.begin(), values.end(), 0);
auto b = std::reduce(values.begin(), values.end(), 0.0);
auto c = std::inner_product(values.begin(), values.end(), weight.begin(), 0);
}
本章知识点总结
- 输出形态三分法
数值算法先区分单值归约、前缀序列与相邻差分,再定接口与重载。
- 顺序 vs 重排
顺序敏感或要求逐位可复现用
std::accumulate;满足结合律与交换律且可重分组才用std::reduce。 - 变换归约分工
双区间顺序配对用
std::inner_product(reduce在前、transform在后),单区间映射或并行场景用std::transform_reduce。 - 前缀包含与基准
包含当前项用
std::partial_sum/std::inclusive_scan,不含当前项且需起点init(如偏移表)用std::exclusive_scan。 - 差分首项与参数序
std::adjacent_difference原样拷贝首项且跳过二元操作,后续按op(current, previous)计算并以输入value_type缓存前驱。 - 并行策略三前提
启用
<execution>前需同时核对前向迭代器、无共享副作用与归约可重排性。 - 类型与精度边界
单值归约与
exclusive_scan的累加类型由init决定,前缀/差分核对输入到输出转换链;有符号溢出属未定义行为,并行浮点归约需容忍低位误差。