＜numeric＞
简介
这是一个“小而精”的算法库，主要用于对数值序列进行数值累计和计算
基础累加与乘积
accumulate()（C++03起）
版本一
template <class InputIterator, class T> T accumulate (InputIterator first, InputIterator last, T init); //first,last：定义了要计算的范围（左闭右开区间 [first, last)） //init: 累加的初始值 //函数返回值：最终的累加结果，类型与 init 相同意思是从 init 开始，顺序地把区间里的每一个元素加进去
版本二
template <class InputIterator, class T, class BinaryOperation> T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op); //first,last：定义了要计算的范围（左闭右开区间 [first, last)） //init：累加的初始值 //binary_op：二元操作，可以是一个 Lambda 表达式（最常用的） // 也可以是一个 函数指针 // 也可以是一个 函数对象注：
Lambda 表达式：
是 C++11 引入的一种 匿名函数
它允许你在代码中直接定义一个“临时函数”，而不必专门去写一个完整的 function 或 class
格式：[capture](parameters { return_type{body} }
[capture]：决定了 Lambda 能不能看到并使用它外部定义的变量
[]：空捕获，不能访问外部变量
[x]：捕获变量 x 的值（拷贝一份）
[&x]：捕获变量 x 的引用（直接操作原变量）
[=]：捕获外部所有变量的值
[&]：捕获外部所有变量的引用
(parameters)：参数列表，跟普通函数一样，定义要传入的参数
{ return_type{body} }：函数体，具体的逻辑代码以及函数返回值
EG：
//传统写法 bool isbigfive(int n) { return n > 5; } // 然后在 main 里调用 find_if(v.begin(), v.end(), isbigfive); //Lambda 写法 find_if(v.begin(),v.end(),[](int) { return n > 5; }); //find_if()：在指定范围内，寻找第一个满足特定条件的元素注：
详细了解 find_if()
注意
如果编写这样编写 accumulate(v.begin(), v.end(), 0)，即使 v 里面存的是浮点数，结果也会被强转成 int（因为初始值 0 是 int）；如果要保留小数，初始值应写成 0.0
EG：
#include <iostream> #include <vector> #include <numeric> // accumulate 所在的头文件 #include <string> using namespace std; int main() { vector<int> v = { 1, 2, 3, 4, 5 }; int sum = accumulate(v.begin(), v.end(), 0); cout << "版本一 (默认累加): " << sum << endl; int sum_of_squares = accumulate(v.begin(), v.end(), 0, [](int acc, int x) { return acc + (x * x); }); cout << "版本二 (平方和): " << sum_of_squares << endl; vector<string> words = { "C++", "Standard", "Library" }; string result = accumulate(words.begin(), words.end(), string("Learning"), [](string a, string b) { return a + " -> " + b; }); cout << "版本二 (字符串连接): " << result << endl; return 0; }reduce()（C++17起）
理解了 acumulate() 之后，reduce() 就很好理解
简单理解就是：accumulate 是 严格顺序的，而reduce是 为了并行 而生的
这个可以先了解一下：
std::accumulate的定义决定了它必须从左到右依次累加。这在单核 CPU 上没问题，但在多核时代，如果我们想把一个巨大的数组分给 8 个 CPU 核心同时计算，accumulate的顺序协议就成了瓶颈
版本一：基础规约
template<class ExecutionPolicy, class ForwardIt> T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last); //ExecutionPolicy&& policy (执行策略)：这是 C++17 引入的核心参数， //决定了算法如何运行，告诉编译器，你是想让这段代码在单线程跑，还是想让它利用多核 CPU 并行跑 //常见取值（定义在 <execution> 中）：（这个大家可以先做了解） //execution::seq：顺序执行 // 和 accumulate 类似，但在内部依然不保证操作顺序 //execution::par：并行执行 // 算法会将数据拆分成多个块，利用多线程同时计算 //execution::par_unseq：并行且矢量化 // 最高级的优化，利用多线程的同时还利用 CPU 的 SIMD 指令集 //ForwardIt first, ForwardIt last (迭代器范围)：定义了一个左闭右开区间 [first, last)，即要参与计算的数据范围注意：
accumulate只需要InputIterator（最弱的迭代器），而reduce需要ForwardIt（正向迭代器）这是因为reduce可能需要多次扫描或拆分区间来支持并行化
版本二：带初始值和自定义操作
template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp> T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp binary_op); //T init (初始值)：计算的起点 //注意：它的类型 T 非常重要 // reduce 的结果类型完全取决于 init 的类型 // 如果是 reduce(..., 0)，结果是 int // 如果是 reduce(..., 0.0)，结果是 double // 如果是 reduce(..., 0LL)，结果是 long long //BinaryOp binary_op (二元操作)：定义如何合并两个元素 // 它是一个可调用对象（函数、Lambda、std::plus<> 等）EG：
#include <iostream> #include <vector> #include <numeric> #include <execution> // 并行策略需要这个头文件 (C++17) using namespace std; int main() { vector<int> v(1000000, 1); // 100万个1 //基础用法（类似于 accumulate） int sum = reduce(v.begin(), v.end()); cout << "基础总和: " << sum << endl; //并行用法 (std::execution::par) // 这告诉编译器：请尽量利用多核并行计算 int par_sum = reduce(execution::par, v.begin(), v.end(), 0); cout << "并行总和: " << par_sum << endl; //自定义操作 (计算所有数字乘积的 2 倍起始值) int product = reduce(execution::par, v.begin(), v.end(), 1, [](int a, int b) { return a * b; }); return 0; }inner_product()（C++03起）
对两个等长的序列进行以下操作：
将两个序列中对应位置的元素相乘（或执行自定义操作 A）
将所有乘积相加（或执行自定义操作 B）到初始值上
简单的例子就是：数学中的向量的内积（点积）
版本一
template<class InputIt1, class InputIt2, class T> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init); //InputIt1 first1, InputIt1 last1：第一个序列的起始和结束位置（左闭右开区间 [first1, last1)） // 决定因素：这个区间的长度决定了计算会进行多少轮 //InputIt2 first2：第二个序列的起始位置 // 注意：算法会自动假设第二个序列和第一个序列一样长 // 如果第二个序列太短，程序会崩溃（越界访问） //T init：累加的初始值 // 重要性：它决定了返回值的数据类型。例如传 0 返回 int，传 0.0 返回 double版本二
template<class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 op1, BinaryOp2 op2); //BinaryOp1 op1（外部操作 - 相当于“加法”）：负责把“当前轮次的计算结果”合并到“之前的累计总和”里 //BinaryOp2 op2（内部操作 - 相当于“乘法”）：负责处理“两个序列中对应位置的一对元素”EG：
#include <iostream> #include <vector> #include <numeric> using namespace std; int main() { // 准备两个向量 vector<int> a = { 1, 3, 5 }; vector<int> b = { 2, 4, 6 }; //版本一：默认点积 int dot_product = inner_product(a.begin(), a.end(), b.begin(), 0); cout << "默认内积: " << dot_product << endl; //版本二：自定义操作 bool is_equal = inner_product(a.begin(), a.end(), b.begin(), true, [](bool acc, bool res) { return acc && res; }, // 对应累计操作 [](int x, int y) { return x == y; } // 对应配对操作 ); cout << "两个数组是否完全相等: " << (is_equal ? "是" : "否") << endl; //版本二：复杂一点的逻辑 int total_diff = inner_product(a.begin(), a.end(), b.begin(), 0, plus<int>(), [](int x, int y) { return abs(x - y); }); cout << "对应元素差的绝对值之和: " << total_diff << endl; return 0; }transform_reduce()（C++17起）（简述）
inner_product() + reduce()
这个函数重载版本比较多，并且算法竞赛中使用频率较低，这里我就不过阐述，如有需要了解，可以评论留言 + 私信，看到了我都会回复的，在这里我就写一个例子，便于大家感知和理解
#include <iostream> #include <vector> #include <numeric> #include <execution> // 并行策略 #include <functional> using namespace std; int main() { vector<int> v1 = { 1, 2, 3, 4, 5 }; vector<int> v2 = { 1, 2, 3, 4, 5 }; auto result = transform_reduce( execution::par, // 1. 执行策略：并行 v1.begin(), v1.end(), // 2. 序列1范围 v2.begin(), // 3. 序列2起点 0, // 4. 初始值 plus<>(), // 5. 归约操作 (Reduce): 如何把结果加起来 [](int a, int b) { // 6. 变换操作 (Transform): 对应元素怎么处理 return (a * a) - (b * b); } ); cout << "变换归约结果: " << result << endl; return 0; }差值与前缀和
partial_sum()
前缀和：前缀和是指一个数组中，从第 1 个元素到第 i 个元素的累加和
比如：
假设原数组为 a，前缀和数组为 S：S[0] = a[0]
S[1] = a[0] + a[1]
S[i] = a[0] + a[1] + ... + a[i]
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first ); //first：指向待处理序列的第一个元素 //last：指向待处理元素的最后一个元素的下一个位置 （标准 STL 的左闭右开区间 [first, last)） //d_first：指明计算结果从哪里开始写入 // 它可以是另一个容器的开头（如 res.begin()） // 它也可以就是 first 本身，这样会直接在原数组上更新，覆盖旧值EG：
#include <iostream> #include <vector> #include <numeric> using namespace std; int main() { vector<int> v = { 1, 2, 3, 4, 5 }; vector<int> res(5); partial_sum(v.begin(), v.end(), res.begin()); for (int x : res) cout << x << " "; return 0; }adjacent_difference()
差分：差分数组是指当前元素与前一个元素的差值
比如：
假设原数组为 a ，差分数组为 d：d[0] = a[0]
d[1] = a[1] - a[0]
d[i] = a[i] - a[i-1]
template< class InputIt, class OutputIt > OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first ); //参数所表达意义和 前缀和 函数相同EG：
#include <iostream> #include <vector> #include <numeric> using namespace std; int main() { vector<int> v = { 1, 3, 6, 10, 15 }; vector<int> diff(5); std::adjacent_difference(v.begin(), v.end(), diff.begin()); for (int x : diff) std::cout << x << " "; return 0; }差分与前缀和的关系：
对原数组求差分，再求前缀和，会变回原数组
对原数组求前缀和，再求差分，也会变回原数组