C++中的数值算法与特殊容器

### C++ 中的数值算法与特殊容器 #### 1. 数值算法 在 C++ 里，数值算法是为数值处理提供的 STL 算法，但也能处理非数值类型，像用 `accumulate()` 来处理多个字符串的和。要使用这些数值算法，需包含头文件 `<numeric>`： ```cpp #include <numeric> ``` ##### 1.1 处理结果 ###### 1.1.1 计算一个序列的结果 `accumulate()` 函数有两种形式： ```cpp T accumulate (InputIterator beg, InputIterator end, T initValue); T accumulate (InputIterator beg, InputIterator end, T initValue, BinaryFunc op); ``` - 第一种形式：计算并返回 `initValue` 与范围 `[beg, end)` 内所有元素的和，对每个元素执行 `initValue = initValue + elem`。 - 第二种形式：对 `initValue` 和范围 `[beg, end)` 内的所有元素调用 `op` 函数，并返回结果，对每个元素执行 `initValue = op(initValue, elem)`。 以下是使用 `accumulate()` 处理范围元素和与积的示例代码： ```cpp // algo/accumulate1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll); // 处理元素的和 cout << "sum: " << accumulate (coll.cbegin(), coll.cend(), 0) << endl; // 处理元素和并减去 100 cout << "sum: " << accumulate (coll.cbegin(), coll.cend(), -100) << endl; // 处理元素的积 cout << "product: " << accumulate (coll.cbegin(), coll.cend(), 1, multiplies<int>()) << endl; // 以 0 为初始值处理元素的积 cout << "product: " << accumulate (coll.cbegin(), coll.cend(), 0, multiplies<int>()) << endl; } ``` 输出结果如下： ``` 1 2 3 4 5 6 7 8 9 sum: 45 sum: -55 product: 362880 product: 0 ``` 最后一个输出为 0，是因为任何值乘以 0 都为 0。 下面用 mermaid 流程图展示 `accumulate()` 第一种形式的执行流程： ```mermaid graph TD; A[开始] --> B[初始化 initValue]; B --> C{是否到达 end}; C -- 否 --> D[取当前元素 elem]; D --> E[initValue = initValue + elem]; E --> C; C -- 是 --> F[返回 initValue]; F --> G[结束]; ``` ###### 1.1.2 计算两个序列的内积 `inner_product()` 函数也有两种形式： ```cpp T inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue); T inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue, BinaryFunc op1, BinaryFunc op2); ``` - 第一种形式：计算并返回 `initValue` 与范围 `[beg1, end1)` 内元素和从 `beg2` 开始的对应元素的内积，对每个对应元素执行 `initValue = initValue + elem1 * elem2`。 - 第二种形式：对 `initValue` 和范围 `[beg1, end1)` 内的元素与从 `beg2` 开始的对应元素调用 `op1` 和 `op2` 函数，并返回结果，对每个对应元素执行 `initValue = op1(initValue, op2(elem1, elem2))`。 以下是使用 `inner_product()` 的示例代码： ```cpp // algo/innerproduct1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,6); PRINT_ELEMENTS(coll); // 处理所有乘积的和 cout << "inner product: " << inner_product (coll.cbegin(), coll.cend(), coll.cbegin(), 0) << endl; // 处理 1*6 ... 6*1 的和 cout << "inner reverse product: " << inner_product (coll.cbegin(), coll.cend(), coll.crbegin(), 0) << endl; // 处理所有和的乘积 cout << "product of sums: " << inner_product (coll.cbegin(), coll.cend(), coll.cbegin(), 1, multiplies<int>(), plus<int>()) << endl; } ``` 输出结果如下： ``` 1 2 3 4 5 6 inner product: 91 inner reverse product: 56 product of sums: 46080 ``` ##### 1.2 相对值与绝对值的转换 有两个算法可实现相对值序列与绝对值序列的相互转换。 ###### 1.2.1 相对值转换为绝对值 `partial_sum()` 函数有两种形式： ```cpp OutputIterator partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg); OutputIterator partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op); ``` - 第一种形式：计算源范围 `[sourceBeg, sourceEnd)` 内每个元素的部分和，并将结果写入从 `destBeg` 开始的目标范围。 - 第二种形式：对源范围 `[sourceBeg, sourceEnd)` 内的每个元素与之前的所有值调用 `op` 函数，并将结果写入从 `destBeg` 开始的目标范围。 以下是使用 `partial_sum()` 的示例代码： ```cpp // algo/partialsum1.cpp #in ```