Chapter 32: Numeric Algorithms

数值算法的共同输入都是区间，输出却分成三类：把整个区间压缩成一个值，把每个前缀压缩成一串阶段值，把相邻元素改写成变化量。本章围绕这三类输出建立判断顺序：先定位算法产出的是单值还是序列，再检查计算顺序是否固定，最后确认累加类型、二元操作和执行策略能否支撑结果稳定性。

贯穿本章的材料是一组账户每日净变动。区间中的每个元素表示一天的增减额，另一组权重表示每一天在某个评分模型中的权重。我们会用同一组数据追踪 std::accumulate、std::reduce、std::inner_product、std::partial_sum、std::inclusive_scan、std::exclusive_scan、std::adjacent_difference 和 std::transform_reduce 的接口现象、计算形状和工程边界。

本章的标准版本边界以 C++17 引入的 std::reduce、scan 系列和 std::transform_reduce 为主，同时说明 C++20 起若干顺序重载获得 constexpr 的影响。接口归属、版本和执行策略语义可回溯到 cppreference 的 std::accumulate、std::reduce、std::inclusive_scan、std::adjacent_difference 与 std::transform_reduce 页面。正文关注可迁移的工程判断，不假设读者正在阅读某个具体标准库实现文件。

下面的代码给出本章贯穿材料。它刻意使用 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'; // 230
}

这段代码展示了数值算法的第一个判断点：算法名称相近时，输出形态常常比函数名更能决定使用方式。total 是一个单值，running_balance 是一个序列，weighted_score 是两个区间成对变换后的单值。后续小节会持续回到这三个对象。

32.1 accumulate、reduce 与 inner_product

std::accumulate、std::reduce 和 std::inner_product 都属于归约类算法。归约（reduction）在这里指把一个区间或两个同步区间中的多个输入值，按照某个二元操作合并成一个输出值。工程判断的关键不是“求和”这个默认动作，而是初始值类型、遍历顺序和二元操作是否允许重排。

std::accumulate 是顺序左折叠。它从 init 开始，按迭代器从左到右的顺序把每个元素合入累加器。下面的教学简化代码表达了它的核心路径；真实标准库实现还会处理 constexpr、移动累加器和约束细节。

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;
}

这段代码的输入是 [first, last) 和 init，处理过程是按迭代器顺序更新同一个累加器，输出是最终累加器。这个形状直接解释了两个工程后果。第一，init 的类型就是累加器类型；第二，二元操作可以依赖左到右顺序，所以字符串拼接、日志合成、带状态的检测结果合并更适合放在 std::accumulate 中表达。

std::reduce 与 std::accumulate 的接口很接近，语义重点却移动到了“允许重排归约”。标准允许 std::reduce 以未指定方式分组和聚合输入值，带执行策略的重载还可以并行执行。这个前提要求二元操作适合重新分组；整数加法在无溢出的数学模型下满足，浮点加法由于舍入误差会随分组变化而改变最低位，字符串拼接还会随分组改变结果文本。

#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;
        }
    );

    // 这里选择 accumulate，原因是文本拼接依赖左到右顺序。
}

这段代码证明了归约选择的第一个规则：操作具有顺序含义时，使用顺序左折叠；操作允许重新分组时，才把 std::reduce 纳入候选。对账户日变动求总额时，如果金额已经提升到足够宽的整数类型，并且接受实现选择的分组形状，std::reduce 可以表达“顺序无关的总和”。对生成交易流水摘要这类文本任务，std::accumulate 的顺序语义更明确。

std::inner_product 把两个区间按位置配对，先对每一对元素做乘法或自定义变换，再把结果归约到初始值中。默认形式相当于“乘积后求和”，常见于点积、加权评分、费用模型和相似度计算。它仍然按顺序执行，长度由第一个区间 [first1, last1) 决定，第二个区间从 first2 开始必须至少提供同样多的可读元素。

#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
}

这里的注释和前文输出故意形成冲突：实际计算结果是 180，前文代码输出注释写成 230 就是一个应被自检捕获的错误。归约类算法的代码审查需要把“区间配对、变换、归约”三个阶段拆开计算，不能让函数名掩盖算式。修正后，weighted_score 的正确注释应为 180。

std::inner_product 的自定义重载还能替换“归约操作”和“成对变换操作”。例如可以先计算每日变动的绝对风险，再把风险值相加。这个用法仍然保持两个阶段：transform(a, b) 生成阶段值，reduce(acc, stage) 合并阶段值。只要把这两个角色分清，std::inner_product 就不是数学点积专用函数，而是“两个同步区间的顺序变换归约”。

32.2 partial_sum、exclusive_scan 与 inclusive_scan

std::partial_sum、std::inclusive_scan 和 std::exclusive_scan 的输出都是序列。它们把“到目前为止已经看到的元素”转换成阶段性累计结果。对账户日变动来说，这类算法生成的是每日收盘余额，而不是整个期间的最终余额。

std::partial_sum 按输入顺序维护一个累加器，并把每一步累加后的值写入输出区间。输入 {120, -40, 30, 50, -20} 的 partial_sum 输出 {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}
}

std::inclusive_scan 也输出包含当前位置元素的前缀结果。默认加法场景下，它和 std::partial_sum 的可见结果相同；差异在于 scan 系列是 C++17 为前缀计算和执行策略准备的算法族。带执行策略的 scan 重载要求前向迭代器，二元操作还要能承受实现为了并行前缀计算所做的分组安排。对非结合操作，scan 的结果稳定性会受到分组形状影响。

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}
}

这段代码给出了 scan 系列的工程判断顺序。先问输出是否要包含当前元素；包含当前元素用 inclusive，不包含当前元素用 exclusive。再问第一个输出是否需要外部基准；exclusive 必须显式给出 init，inclusive 可以没有 init，也可以用带 init 的重载把外部基准纳入每个前缀。最后检查二元操作的分组敏感性；如果前缀结果具有严格时间顺序含义，std::partial_sum 的顺序表达更贴近业务语义。

前缀算法还有一个容易被忽略的输出区间约束。目标区间必须能写入 N 个结果，N 是输入区间长度。目标开始位置可以是某些算法允许的输入位置，但代码审查时应先确认标准对重叠区间的规定，再决定是否原地写入。对普通工程代码，单独准备输出容器能让别名关系更清楚，也便于在调试器中同时观察原始输入和阶段结果。

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}
}

这段代码的输入是每日收盘余额，输出是每日净变动。第一项 120 没有前一个元素可比较，所以原样写出。第二项开始执行 current - previous，于是 80 - 120 == -40，110 - 80 == 30。这解释了 std::adjacent_difference 的第一个边界：输出序列的第一项不是“差值”，而是恢复前缀序列时所需的基准值。

std::adjacent_difference 的自定义二元操作接收的是当前值和前一个值。这个参数顺序与很多手写比较代码一致：先看当前，再看之前。用它可以表达增长率、状态迁移、相邻采样之间的距离或相邻时间点之间的变化标签。

#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，后续元素表示上升、下降或持平。
}

这个示例暴露了自定义差分的语义问题：第一项仍然来自原始输入，它不服从后续元素的标签约定。工程上常见处理方式是为第一项单独定义含义，或者在结果消费阶段从第二项开始读取标签。算法不会替业务定义“第一项没有前驱”时应该写什么。

常见实现形状会缓存前一个输入值，再读取当前值，计算后更新缓存。这个缓存对象的类型来自输入迭代器的 value type。由此得到一个类型边界：当输入值类型、输出可写类型和二元操作返回类型不一致时，需要确认每一步转换都符合预期。char、short、自定义定点数和强类型金额对象尤其需要审查这一点。

32.4 transform_reduce 与并行算法基础

std::transform_reduce 把“变换”和“归约”合并到一个算法中。它有两类常见接口形状：两个区间版本先把 *it1 与 *it2 成对变换，再归约；一个区间版本先把每个元素做一元变换，再归约。它适合表达“先计算阶段值，再合并阶段值”的单值输出。

在日变动材料中，std::inner_product 的默认形式可以计算加权和，std::transform_reduce 可以把这个过程写得更直接，尤其当变换不再是普通乘法时更清晰。

#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 == 390
}

这段代码的变换阶段产出每一天的风险贡献，归约阶段把贡献合并成总风险。相比手写循环，它把两个角色显式交给两个可调用对象：一元变换负责单个元素到阶段值，二元归约负责阶段值合并。代码审查时应分别检查这两个对象，而不是把 lambda 当作附属参数扫过去。

std::transform_reduce 的并行基础来自一个核心前提：实现可以改变变换结果的归约分组。两个区间版本默认等价于 std::plus<> 归约和 std::multiplies<> 变换，并被设计成 std::inner_product 的可并行化对应物。这个“可并行化”不承诺一定启动线程，它只说明标准语义允许实现使用不同的分组和执行策略。

执行策略引入三个需要同时检查的约束。第一，带标准执行策略的重载通常要求前向迭代器，因为并行调度需要多次定位或拆分区间。第二，被调用的函数对象应没有会影响结果的共享副作用；向同一个外部容器追加、修改输入元素或依赖全局计数器都会破坏算法语义。第三，归约操作要适合重新分组；浮点求和、字符串拼接、带时间戳的日志合并都需要额外说明结果稳定性。

#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; }
    );

    // seq 明确选择顺序执行策略；把策略换成 par 前，先检查归约操作和 lambda 副作用。
}

这个示例使用 std::execution::seq，目的是让执行策略作为接口角色出现，而不是要求并行运行环境。把 seq 换成 par 前，判断顺序是固定的：先确认迭代器类别满足重载要求，再确认 lambda 不写共享状态，再确认归约操作适合重排，最后再讨论性能收益。性能收益本身取决于数据量、元素访问成本、函数对象开销、实现后端和硬件调度，函数名无法单独给出结论。

32.5 数值算法的类型和精度边界

数值算法的错误经常出现在类型边界，而不是循环边界。标准库算法会忠实使用接口给出的类型、操作和区间；它不会自动把 int 求和提升成 long long，也不会让浮点归约在不同分组下保持逐位相同。工程判断应从“结果类型由哪里决定”开始。

std::accumulate、std::reduce、std::inner_product 和 std::transform_reduce 的 init 直接参与结果类型决定。std::accumulate(v.begin(), v.end(), 0) 中的 0 是 int，因此累加器是 int。当输入是 std::vector<double> 时，小数会在每一步合入 int 累加器时损失；当输入是大量金额分时，int 还可能溢出。稳定写法是用业务所需的承载类型作为 init。

#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。
}

这段代码的关键点不是 auto，而是第三个参数。auto 只是接收算法返回值；真正让 wrong 变成整数路径的是 0。代码审查时应沿着“初始值字面量 → 累加器类型 → 二元操作返回值 → 最终结果”追踪，而不是只看输入容器元素类型。

前缀类算法的类型边界稍有差异。std::partial_sum 默认以输入 value type 建立累加器，输出迭代器只负责接收每一步结果。std::inclusive_scan 带 init 的重载可以把外部初始值类型纳入计算。std::adjacent_difference 会用输入 value type 缓存前一个值，再把二元操作结果写到输出。由此得到第二条规则：单值归约优先检查 init，前缀和差分优先检查输入 value type、输出 value type 和操作返回类型之间的转换链。

整数溢出和浮点误差需要分开处理。对有符号整数，溢出会进入未定义行为边界；对无符号整数，溢出按模运算回绕，结果可能符合语言规则但不符合业务语义。对浮点数，加法满足近似数学直觉，却不满足逐位稳定的结合律。std::reduce、scan 系列和带并行执行策略的算法允许不同分组时，浮点结果的最低位变化属于需要提前接受或规避的工程事实。

数值算法的可复用判断顺序可以固定为五步。第一，确认输出形态：单值、前缀序列或相邻差分序列。第二，确认顺序语义：严格左到右、前缀阶段值，或允许重新分组。第三，确认类型来源：init、输入 value type、输出 value type 和二元操作返回类型。第四，确认区间关系：输入长度、第二输入区间容量、目标区间可写范围和可能的重叠。第五，确认执行策略：迭代器能力、副作用、异常处理和结果稳定性。

这套顺序也能解释本章贯穿材料中的几个选择。总金额使用 0LL，因为金额累加需要比 int 更宽的承载类型。每日余额用 std::partial_sum，因为输出含有明确时间顺序。恢复每日变动用 std::adjacent_difference，因为输入已经是阶段累计值。风险评分用 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);
}

答案要点

a 的类型是 int，因为 std::accumulate 的第三个参数 0 决定累加器类型，double 输入会在合入整数累加器时发生转换。工程写法应改成 0.0，或者改成明确的业务类型，例如 double init = 0.0。

b 的类型是 double，因为 init 是 0.0。它使用 std::reduce，语义允许重新分组；对浮点加法，结果可能随分组变化出现最低位差异。若业务要求严格左到右可复现，应使用 std::accumulate 表达顺序求和；若接受浮点归约误差，则需要在测试中使用容差比较。

c 的类型是 int，因为 std::inner_product 的初始值是 0。每个 double * int 的阶段值会合入整数累加器，结果语义不符合加权浮点和。工程写法应把初始值改成 0.0，并检查第二个区间 weight 至少覆盖 values 的长度。

本章知识点总结

• 输出形态：数值算法先按单值、前缀序列和相邻差分序列区分用途。
• accumulate：std::accumulate 是顺序左折叠，适合表达依赖左到右顺序的归约。
• reduce：std::reduce 允许未指定分组，二元操作需要适合重新分组。
• inner_product：std::inner_product 把两个同步区间先成对变换，再顺序归约成单值。
• partial_sum：std::partial_sum 输出每个位置的顺序前缀累计值。
• inclusive：std::inclusive_scan 的每个输出包含当前位置元素。
• exclusive：std::exclusive_scan 的每个输出表示当前位置之前的前缀结果。
• 差分基准：std::adjacent_difference 的第一项来自原始输入，后续项才表达相邻变化。
• 变换归约：std::transform_reduce 把阶段值生成和阶段值合并拆给两个可调用对象。
• 执行策略：并行相关重载需要检查迭代器能力、副作用和归约操作的重排稳定性。
• 初始值类型：单值归约的 init 通常决定累加器和返回值类型。
• 前缀类型：前缀和差分算法需要检查输入 value type、输出 value type 和操作返回类型的转换链。
• 浮点边界：浮点加法对分组敏感，std::reduce 和并行 scan 可能产生最低位差异。
• 判断顺序：先看输出形态，再看顺序语义，再看类型来源、区间关系和执行策略。