剑指信奥 | C++ 之 STL - 算法 acumulate

剑指信奥｜C++ 之 STL - 算法 accumulate

求和简单又不简单

数值算法

我们已经学习了 STL 非可变序列算法中的几个常用的算法函数，今天，我们换一个算法类别。

STL 的算法有一个类别是数值算法，这一类别下的算法主要是对容器进行数值运算，我们就从一个比较简单的算法 accumulate 求和 切入，了解一下数值算法的基本含义和使用。

首先需要注意的是，数值相关算法的使用需要代码头部引入类库 numeric ，别忘了这一点：

#include <numeric>

accumulate 的作用

accumulate 算法的作用是计算容器范围 [first, last) 元素与一个初始值 init 的总和，所以我们称之为求和算法。

accumulate 的使用

accumulate() 函数一般接收 3 个参数：

起始元素的输入迭代器 first
终止元素的后一个元素的输入迭代器 last
一个初始值 init

代码示例：

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

using namespace std;

int main() {

    vector<int> vi = {1, 2, 3};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 计算范围是 [first, last)
    first = vi.begin();
    last = vi.end();

    // 使用 accumulate 进行计算
    int result = accumulate(first, last, 0);

    cout << "vi 所有元素的和：" << result << endl;

    return 0;
}

/*
 output
    vi 所有元素的和：6
 */

由于我们给定的初始值是 0，所以计算的结果就是整个 vector 内所有元素的和。

accumulate 的内部原理

我们简单介绍一下求和算法 accumulate 的内部原理，先来看一份 accumulate 可能的内部实现：

template<class InputIt, class T>
constexpr
T accumulate(InputIt first, InputIt last, T init)
{
    for (; first != last; ++first) {
        init = std::move(init) + *first;
    }
    return init;
}

我们已经学过了模版函数，这个实现的代码就是一个模版函数的典型实例。

注意 for 循环中，累加的计算是以 init 作为初始值的，返回的结果也是 init，而在模版中，init 的类型是 T，于是就引发了一个可能会忽视的问题。

我们再来看一份代码：

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

using namespace std;

int main() {

    vector<double> vd = {1.1, 2.2, 3.3};

    // 声明迭代器
    vector<double>::iterator first, last;

    // 计算范围是 [first, last)
    first = vd.begin();
    last = vd.end();

    // 使用 accumulate 进行计算
    int result = accumulate(first, last, 0);

    cout << "vd 所有元素的和：" << result << endl;

    return 0;
}

/*
 output
    vd 所有元素的和：6
 */

同样是计算 vector 内所有元素的和，但这次 vector 内存放的是 double 值，3 个元素的和应该是 6.6，结果明显是不对的。

原因就在于求和函数是以 init 初始值决定最后和的数据类型，所以在这一次求和过程中，每个 double 类型的元素都被强制转换成了 int，造成了精度损失，这一点一定要注意。

再来看一份代码：

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

using namespace std;

int main() {

    vector<string> vs = {"abc", "def"};

    // 声明迭代器
    vector<string>::iterator first, last;

    // 计算范围是 [first, last)
    first = vs.begin();
    last = vs.end();

    string init = "xyz";

    // 使用 accumulate 进行计算
    string result = accumulate(first, last, init);

    cout << "vs 所有元素的和：" << result << endl;

    return 0;
}

没有运行，根据我们上面谈到的 accumulate 函数的内部实现原理，大家推算一下，这段程序的输出结果应该是什么？

accumulate 的进阶

求和运算还有一个很实用的重载函数，这个函数的参数有 4 个：

起始元素的输入迭代器 first
终止元素的后一个元素的输入迭代器 last
一个初始值 init
一个二元函数对象 op

这个重载的 accumulate() 函数的返回值是初始值与给定范围元素在 op 函数上 一元左折叠 unary left fold 的结果。

什么是一元左折叠？

一元左折叠是 C++ 语言四种折叠表达式之一，而折叠表达式是 C++ 17 版本的语言新特性。

我们只关注一下一元左折叠的展开方式：

一元左折叠 (... op E) 展开成为 (((E₁ op E₂) op ...) op E_N)

所以折叠表达式是一种简化参数处理的方式。

有了以上定义，我们来看一份关于重载的 accumulate 函数的代码示例：

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

using namespace std;

// 定义二元函数 op
inline int op (int x, int y) {
    return x * y;
}

int main() {

    vector<int> vi = {1, 2, 3};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 计算范围是 [first, last)
    first = vi.begin();
    last = vi.end();

    // 使用 accumulate 进行计算
    int result = accumulate(first, last, 4, op);

    cout << "vi 所有元素的和：" << result << endl;

    return 0;
}

/*
 output
    vi 所有元素的和：24
 */

这段代码里，我们首先定义了一个二元函数 op，它是计算两个参数的乘积。

所以，在把 op 这个函数对象传入 accumulate() 时，就是把初始值以及容器所有的元素进行乘积左折叠的结果，虽然我们写的是 vi 所有元素的和...，但这结果已经不是简单的和了。

最后，思考一下，如果二元函数是这样定义的，程序的输出结果应该是什么？

inline int op (int x, int y) {
    return x - y;
}

信奥竞赛

系列