数值算法与集合算法：accumulate, inner_product, adjacent_difference, set_union, set_intersection

数值计算和集合操作，是日常开发中绕不开的两类场景。STL 在 <numeric> 和 <algorithm> 头文件里，给我们准备了一套相当趁手的工具。今天我就带大家把这几个算法彻底捋一遍。

1. accumulate：累加，但不止于累加

std::accumulate 是 <numeric> 里最基础的算法。它的作用很简单：从一个初始值开始，依次对序列中的每个元素执行二元操作，最终得到一个累积结果。

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 默认加法：1+2+3+4+5 = 15
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << sum << std::endl;  // 15
    
    // 自定义操作：乘法，初始值1
    int product = std::accumulate(v.begin(), v.end(), 1, 
                                  [](int a, int b) { return a * b; });
    std::cout << product << std::endl;  // 120
    
    return 0;
}

这里有个细节很多人会踩坑：初始值的类型决定了返回类型。如果你传 0，返回 int；传 0.0，返回 double。我曾经在项目里用 accumulate 累加一堆浮点数，结果因为初始值写了 0，精度全丢了。嗯，从那以后我每次都会检查初始值类型。

2. inner_product：内积，两个序列的「点乘」

std::inner_product 计算两个序列的内积。默认行为是：对应元素相乘，然后全部加起来。说白了就是数学里的点积。

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    
    // 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32
    int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    std::cout << dot << std::endl;  // 32
    
    return 0;
}

你想想看，如果两个序列长度不一致会怎样？inner_product 只遍历到第一个序列的末尾，第二个序列如果更短，就会越界访问。所以调用前务必保证第二个序列长度 ≥ 第一个序列。我在做图像处理时，用这个算两个特征向量的相似度，就因为这个细节排查了半天。

它还有两个可选的二元操作参数：一个用于「加法」步骤，一个用于「乘法」步骤。你可以用它实现自定义的「内积」逻辑，比如字符串的某种匹配度计算。

3. adjacent_difference：相邻元素的差

std::adjacent_difference 计算序列中相邻元素的差值。第一个元素直接复制到输出，从第二个开始，每个元素等于当前元素减去前一个元素。

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {2, 5, 9, 14, 20};
    std::vector<int> diff(v.size());
    
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    // diff = {2, 3, 4, 5, 6}
    
    for (int x : diff) std::cout << x << " ";
    // 输出：2 3 4 5 6
    
    return 0;
}

这个算法有个很妙的特性：它是可逆的。如果你对差值结果再做一次 partial_sum，就能恢复原始序列。我在做时间序列分析时，经常用这个算法把原始数据转成增量数据，方便做差分检测。

4. set_union：并集，有序序列的合并

std::set_union 计算两个已排序序列的并集。注意前提：两个序列必须已经按升序排好。它会把所有出现在任一序列中的元素，按顺序写入输出。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    std::set_union(v1.begin(), v1.end(),
                   v2.begin(), v2.end(),
                   std::back_inserter(result));
    // result = {1, 2, 3, 4, 5, 6, 7}
    
    return 0;
}

这里有个坑：如果两个序列中有重复元素，set_union 会保留出现次数较多的那个。比如 v1 有两个 3，v2 有一个 3，结果里会有两个 3。我个人习惯在调用前先用 std::unique 去重，除非你明确需要保留重复。

5. set_intersection：交集，取公共部分

std::set_intersection 计算两个已排序序列的交集。只有同时出现在两个序列中的元素才会被写入输出。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(result));
    // result = {3, 4, 5}
    
    return 0;
}

这个算法的时间复杂度是 O(m+n)，比暴力 O(m*n) 快得多。我在做权限系统时，用这个算法快速计算用户角色和资源角色的交集，效率非常高。

知识体系总览

下面这张图帮你理清这几个算法的关系和使用场景：

避坑指南与实战建议

这几个算法虽然简单，但用起来有几个地方特别容易翻车：

• 迭代器范围要合法：所有算法都要求传入的迭代器范围是有效的，[first, last) 必须是一个合法区间。空区间是允许的，但不要传反了。
• 输出空间要足够：如果你直接传一个普通迭代器（而不是 back_inserter），必须确保目标容器有足够的空间。否则就是越界写入。
• 集合算法要求有序：这是最容易被忽略的一点。我见过有人把未排序的 vector 传给 set_union，结果出来一堆乱序数据，排查了半天才发现是排序问题。
• 自定义比较器要一致：如果你用了自定义比较器，所有相关算法（排序、集合操作）必须使用同一个比较器，否则结果不可预测。

好了，这几个数值算法和集合算法就讲到这里。它们虽然基础，但用好了能写出非常简洁高效的代码。下次遇到累加、内积、差分、并集、交集这些需求时，别自己手写循环了——STL 已经帮你准备好了。

---