Skip to main content

Chapter 32: Numeric Algorithms

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

数值算法以区间为输入,却产出三类不同结构的结果:单值归约、前缀序列与相邻差分。工程选型的关键在于先锁定输出形态与计算顺序,再核对累加类型、二元操作可重排性与执行策略边界,防止静默截断、整数溢出或并行浮点漂移。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

贯穿本章的材料是一组账户每日净变动 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 前,必须依次满足以下条件:

  1. 迭代器能力:带标准执行策略的重载通常要求前向迭代器,以支持区间拆分与多点定位。
  2. 无共享副作用:变换与归约函数对象不得读写共享可变状态(如向外部容器追加、改写输入或递增非原子计数器)。
  3. 可重排稳定性:归约操作需适合重新分组;浮点求和、字符串拼接与时序日志合并必须先评估漂移风险。
  4. 实测性能收益:前三条成立后再以基准测试验证,实际加速取决于数据规模、访存与调度开销。

排查顺序

审查 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_reduceinit 实参类型传 0 导致 double 截断或大额整数溢出(应传 0.0 / 0LL)
无 init 前缀和partial_sum、无 init 的 inclusive_scan输入迭代器 value_type输入为窄整数(如 int16_t、int)时累计溢出
带 init 扫描exclusive_scan、带 init 的 inclusive_scaninit 实参类型init 类型过窄会截断后续阶段值
相邻差分adjacent_difference输入 value_type 缓存前驱输入、操作返回与输出类型不一致触发隐式转换

边界与误区

注意

有符号整数溢出属于未定义行为(UB),无符号整数溢出按模运算回绕(合法但破坏金额语义);浮点加法不满足逐位结合律,std::reduce、scan 系列与并行策略产生的最低位差异属于规范行为,需要逐位复现时应改用 std::accumulate / std::partial_sum 或改用容差断言。

工程选型可按固定五步排查:

  1. 输出形态:单值归约、前缀序列还是相邻差分。
  2. 顺序语义:严格左到右、顺序前缀还是允许重分组。
  3. 类型来源:init、输入 value_type、输出 value_type 与操作返回类型转换链。
  4. 区间关系:输入长度、第二区间最小容量、目标可写长度与重叠约束。
  5. 执行策略:前向迭代器、无共享副作用、异常与结果稳定性。

核心判断

回到贯穿材料,上述五步直接锁定了所有实现选择: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 决定,前缀/差分核对输入到输出转换链;有符号溢出属未定义行为,并行浮点归约需容忍低位误差。