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

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

事半功倍的算法库

算法模版库

算法 algorithm 是 C++ STL 中的一个重要的组成部分，也是信息学奥赛的重中之重。

毫不夸张的说，除了 NOIP 的初赛考察一些计算机基础知识之外，NOIP 的复赛无论是普及组还是提高组的题目，全部都是在考察算法。

算法是计算机科学的一大领域，从简单到复杂有着非常多的内容。

C++ STL 的算法库提供了很多现成的算法，熟练掌握这些基本算法非常重要，在此基础上我们再去学习更加复杂的算法，可以大大简化复杂算法的解法。

算法与容器和迭代器关联密切，算法一般通过迭代器来操纵容器中的元素。

STL 算法库共有一百多个算法函数，从今天起，我们从 STL 算法库中精选部分常用函数介绍给同学们，希望大家每天学到一些，并实际使用起来，掌握这部分重要内容。

算法的分类

STL 算法库主要由头文件 algorithm、numeric 以及 functional 组成，其中 algorithm 是必须引入的，数值类算法需要引入 numeric，functional 中包含了很多内建函数。

STL 的算法类别有很多种，从大的方向上可以分为四个类别，分别是：

非可变序列算法：不直接修改所操作容器内容的算法。
可变序列算法：可以修改它们所操作的容器内容的算法。
排序算法：排序算法、合并算法、搜索算法和集合操作。
数值算法：对容器内容进行数值运算。

今天，我们从简单的内容开始，学习非可变序列算法中的 count 和 count_if 。

count

算法库中的 count 函数属于一种不可修改序列的操作，其主要作用是在一个容器的给定范围内查找元素，输出这个元素的个数。

这个函数一般接收 3 个参数：

起始元素的输入迭代器 first
终止元素的后一个元素的输入迭代器 last
要统计的元素值 value

这里需要注意的是查找范围是 [first, last) 这个半闭半开区间，last 是要查找的元素的后一个元素。这点需要特别注意。

我们来看一个简单的示例：

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

using namespace std;

int main() {

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

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

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

    // 指定查询的元素值
    int value = 3;

    // 使用 count 输出查询结果
    cout << "count of value: " << count(first, last, value) << endl;

    return 0;
}

/*
 output
    count of value: 3
 */

上述代码查找了整个 vector 中元素 3 的个数，结果是正确的。

想象一下，如果没有 count 算法函数，这个结果怎么计算？

试着做一下，再比较一下，是不是使用算法库更加方便。

count_if

与 count 相比较，count_if 函数也是统计在指定范围内的元素值，不同的是，count_if 可以进一步指定条件，只有满足条件的元素才会进行统计。

这个函数一般接收 3 个参数：

起始元素的输入迭代器 first
终止元素的后一个元素的输入迭代器 last
元素需要满足的条件 pred

什么是 pred?

pred 是英文 predicate 谓词 的简写，那什么又是谓词？

在数理逻辑中，谓词通常被理解为布尔值函数 P : X → {true, false}，称为 X 的谓词。
Wikipedia

根据 count_if 的定义，不难理解，谓词是一个只能返回 true 或 false 的函数，以此对我们要统计的元素进行筛选。

元素值传入这个函数，必须要返回 true，才能被统计。至于这个谓词怎么定义，根据我们的需求来确定。

最后，我们来看下 count_if 的代码示例：

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

using namespace std;

// 定义内联谓词函数
inline bool pred(int x) {
    // 条件为 3 的倍数
    return x % 3 == 0;
}

int main() {

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

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

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

    // 指定查询的元素值
    int value = 3;

    // 使用 count 输出满足谓词 pred 的结果
    cout << "count of pred: " << count_if(first, last, pred) << endl;

    return 0;
}

/*
 output
    count of value: 3
 */

这段代码中，我们首先定义了一个内联函数 pred，它定义的规则是当参数为 3 的倍数时返回 true。

最后在 count_if 中，我们传入 pred，返回满足条件的元素个数，结果虽然跟第一题的一样，但含义是不同的。

信奥竞赛

系列