C++STL 中的數值演算法(iota、accumulate、adjacent_difference、inner_product、partial_sum）

2022 年 4 月 7 日
筆記
STL

以下演算法均包含在頭文件 numeric 中

1.iota

該函數可以把一個範圍內的序列從給定的初始值開始累加
先看用法。
例：
假設我需要一個長度為10，從5開始遞增的序列

    vector<int> a(10);
    iota(begin(a), end(a), 5);

    for (auto x : a) {
        cout << x << " ";
    }

輸出：
5 6 7 8 9 10 11 12 13 14
這樣就可以很方便的創建一個遞增的序列，~~而不用使用for循環~~
此外，該函數是使用連續的支援 operator++()的 T 類型值填充序列
也就是說double類型也可以使用，string類型也可以使用。
只要是重載了++運算符的類型都可以使用。

2.accumulate

曾經在演算法比賽中看見別人使用accumulate函數計算出了一個數組的和。
覺得特別的優雅，像這樣：

    vector<int> a(10);
    iota(begin(a), end(a), 1);

    cout << accumulate(begin(a), end(a), 0) << "\n";  // 計算從1加到10的和，從0開始加

輸出：
55
從那天起，每當我要求一個序列的和的時候，我都會使用這個方法…
但是今天，當我看到accumulate的源碼之後：

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

注意看這裡：

哇哦，它竟然還支援二元仿函數，C++ functional庫中的仿函數
於是，我有了一個大膽的想法。
求一個數組的乘積

    vector<int> a(10);
    iota(begin(a), end(a), 1);

    cout << accumulate(begin(a), end(a), 1, multiplies<int>()) << "\n";  // 計算從1加到10的乘積，從1開始乘

輸出：
3628800
同理，還可以求數組的減，數組的除，數組的模😁

3.partial_sum

這個函數可以用來求前綴和，前綴和指一個數組的某下標之前的所有數組元素的和（包含其自身）。
例如，1、2、3、4、5的前綴和數組為 1 3 6 10 15

    vector<int> a(5);
    iota(begin(a), end(a), 1);

    partial_sum(begin(a), end(a), begin(a)); // 求a的前綴和，賦值給a數組（第三個參數）

    for (auto x : a) {
        cout << x << " ";
    }

輸出：
1 3 6 10 15
有了上一個函數的經驗，我們還可以求一個數組的前綴乘、除等
例：

    partial_sum(begin(a), end(a), begin(a), multiplies<int>());

輸出：
1 2 6 24 120

4.adjacent_difference

這個函數可以對一個序列里相鄰兩個元素進行運算，通過differerce這個詞可以看出來，默認是計算相鄰兩元素的差

vector<int> a{1, 4, 5, 100, 40};

adjacent_difference(begin(a), end(a), begin(a)); // 求a數組相鄰元素的差，賦值給a數組（第三個參數）

for (auto x : a) {
    cout << x << " ";
}

輸出：
1 3 1 95 -60

今天我想計算相鄰兩元素的乘積

adjacent_difference(begin(a), end(a), begin(a), multiplies<int>());

輸出：
1 4 20 500 4000

5.inner_product

這個函數默認情況下可以求序列中每個元素的內積之和：

    vector<int> a(3);
    iota(begin(a), end(a), 1);

    cout << inner_product(begin(a), end(a), begin(a), 10) << "\n"; // 從初值10開始加上序列各元素的內積

輸出：
24

還可以用來求兩個序列元素兩兩相乘再相加的結果

    vector<int> a{1, 2, 3};
    vector<int> b{2, 3, 4};

    // 1 * 2 + 2 * 3 + 3 * 4
    cout << inner_product(begin(a), end(a), begin(b), 0) << "\n";

輸出：
20

此外，還可以通過仿函數來替代上述的兩個操作符 + 和 *

    vector<int> a{1, 2, 3};
    vector<int> b{2, 3, 4};

    cout << inner_product(begin(a), end(a), begin(b), 1
                        , multiplies<int>(), minus<int>()) << "\n";
                            // 原來的加法 +  // 原來的乘法 *
                            // 計算 (1 - 2) * (2 - 3) * (3 - 4) = -1

輸出：
-1

Tags: STL