C++ vector 排序与查找

在 C++ 中，我们经常需要对 vector 容器中的数据按大小排序，或者查找某个特定的值是否存在。需要注意的是，vector 自身并没有提供 .sort() 或 .find() 成员函数，而是统一配合标准库 <algorithm> 头文件中的通用算法函数来实现。

用于 vector 排序、查找与统计的常用函数如下表所示。

排序与查找常用函数
函数	说明
std::sort()	对容器中的元素进行排序，默认按从小到大升序排列
std::find()	在容器中查找指定值第一次出现的位置
std::count()	统计指定值在容器中一共出现的次数

和前面学过的数组排序类似，调用这些函数前都需要先引入 <algorithm> 头文件。当我们操作整个容器时，前两个参数固定传入 容器名.begin() 和 容器名.end()，表示把容器从头到尾处理一遍。

std::sort() 排序

在 C++ 中，对 vector 排序使用的是 <algorithm> 头文件中的 std::sort() 函数，它会直接修改原容器中元素的排列顺序。

1. 升序排序

如果不指定额外的排序规则，std::sort() 默认会将元素按照从小到大的升序顺序排列。

语法：

std::sort(容器名.begin(), 容器名.end());

说明：

std::sort() 不仅支持对 int、double 等数值类型的容器按大小排序，也支持对 std::string 字符串类型的容器按英文字母先后顺序（ASCII 码）排序。

之所以设计成传入 begin() 和 end() 两个位置参数，是为了方便我们灵活指定排序范围。平时需要对整个容器排序时，固定传入头尾两个位置即可。

示例 1：vector 升序排序

运行代码

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

int main() {
    std::vector<int> nums = {42, 15, 88, 23, 60};

    std::sort(nums.begin(), nums.end());    // 默认升序排序

    for (int num : nums) {
        std::cout << num << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

15 23 42 60 88

分析：

在这个例子中，我们调用 std::sort(nums.begin(), nums.end())，直接把 nums 里原本无序的 5 个整数按从小到大的顺序重新排列。

2. 降序排序

如果我们希望把 vector 中的元素按照从大到小的降序顺序排列，可以在 std::sort() 的第 3 个参数位置传入 std::greater<数据类型>()。

语法：

std::sort(容器名.begin(), 容器名.end(), std::greater<数据类型>());

说明：

std::greater 定义在 <functional> 头文件中，其中 greater 是 “更大” 的意思，表示让较大的值排在前面。尖括号 <> 里需要填写与容器一致的元素类型，末尾的一对空小括号 () 属于固定语法，不能省略。

示例 2：vector 降序排序

运行代码

#include <algorithm>
#include <functional>    // 提供 std::greater
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {42, 15, 88, 23, 60};

    // 按从大到小降序排序
    std::sort(nums.begin(), nums.end(), std::greater<int>());

    for (int num : nums) {
        std::cout << num << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

88 60 42 23 15

分析：

由于容器的类型是 std::vector<int>，因此第 3 个参数对应写成 std::greater<int>()，排序后输出结果为从大到小的 88 60 42 23 15。

初学的小伙伴在写降序排序时，很容易漏掉 std::greater<int>() 末尾的小括号，从而导致编译报错。

// 正确方式
std::sort(nums.begin(), nums.end(), std::greater<int>());

// 错误方式
std::sort(nums.begin(), nums.end(), std::greater<int>);

如果需要按自定义规则对复杂数据排序，我们会在后面的 “C++ sort 排序” 一节中展开介绍。

提示如果只是想把容器中当前的元素顺序首尾倒过来，我们可以使用 <algorithm> 头文件中的 std::reverse(容器名.begin(), 容器名.end())。注意它不会比较元素大小，不要把单纯的 “首尾反转” 当成降序排序。

std::find() 查找元素

如果我们想知道 vector 里面有没有某个特定的值，或者想知道它排在第几个下标位置，可以使用 <algorithm> 头文件中的 std::find() 函数。

1. 判断元素是否存在

调用 std::find() 时，程序会从容器的第 1 个元素开始，从左往右逐个与目标值比对。

语法：

auto it = std::find(容器名.begin(), 容器名.end(), 目标值);

说明：

std::find() 返回的不是整数下标，而是一个表示位置的迭代器，不能直接使用 std::cout << it; 打印出来。为了省去手写复杂类型的麻烦，平时我们直接配合 auto 关键字定义变量 it 来接收即可，现阶段只需掌握用它判断元素是否存在和计算下标。

那应该怎样根据 it 判断有没有找到呢？你可以把 容器名.begin() 看作第 1 个元素的位置，而把 容器名.end() 想象成 “最后一个元素再往后一格的终点线”。判断标准如下：

it != 容器名.end()：说明在走到终点线之前就停下来了，也就是找到了目标值，容器中存在该元素。
it == 容器名.end()：说明从头到尾找了一遍都没碰上，一直走到了终点线，容器中不存在该元素。

示例 3：判断元素是否存在

运行代码

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

int main() {
    std::vector<int> ids = {1001, 1002, 1003, 1004};

    // 查找元素 1003
    auto it = std::find(ids.begin(), ids.end(), 1003);

    if (it != ids.end()) {
        std::cout << "找到了目标编号 1003\n";
    } else {
        std::cout << "未找到目标编号\n";
    }
    return 0;
}

运行结果如下。

找到了目标编号 1003

分析：

在这个例子中，我们在 ids 容器里查找整数 1003。由于 1003 存在于容器中，返回的 it 不等于 ids.end()，因此程序进入 if 分支输出提示。

对于这个例子来说，如果把查找目标改为不存在的 1009，返回的 it 就会等于 ids.end()，程序便会进入 else 分支输出 “未找到目标编号”。

2. 计算查找到的元素下标

很多时候，我们不仅想知道元素存不存在，还想知道它在 vector 中的具体下标。

语法：

auto index = it - 容器名.begin();

说明：

确认 it != 容器名.end() 成立之后，我们只需要用查找到的位置 it 减去起点位置 容器名.begin()，算出来的差值就是该元素从 0 开始计算的下标。如果容器中有多个相同的值，std::find() 返回的是第 1 个匹配元素的位置。

示例 4：查找元素并计算下标

运行代码

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

int main() {
    std::vector<std::string> langs = {"C", "C++", "Go"};

    auto it = std::find(langs.begin(), langs.end(), "Go");

    if (it != langs.end()) {
        auto index = it - langs.begin();    // 计算元素下标
        std::cout << "找到 Go，下标为：" << index << '\n';
    } else {
        std::cout << "未找到目标字符串\n";
    }
    return 0;
}

运行结果如下。

找到 Go，下标为：2

分析：

在 langs 容器中，"C" 的下标是 0，"C++" 的下标是 1，"Go" 的下标是 2。从起点 langs.begin() 往后走 2 步正好到达 "Go" 的位置，因此 it - langs.begin() 算出来的结果就是 2。

拿到下标 index 后，我们就可以直接通过 langs[index] 读写该位置的元素。这里小伙伴们要注意，计算下标前一定要先判断 it != langs.end()。如果目标元素不存在，此时 it 等于终点线 langs.end()，相减得到的结果会等于容器长度 3，并不是有效下标。

std::count() 统计次数

由于 std::find() 每次只返回第 1 个匹配元素的位置，如果我们想知道某个值在 vector 中一共出现了多少次，可以使用 <algorithm> 头文件中的 std::count() 函数。

语法：

auto times = std::count(容器名.begin(), 容器名.end(), 目标值);

说明：

std::count() 会从头到尾扫描整个容器，统计并返回等于 “目标值” 的元素个数。如果容器中不存在该元素，则返回 0。

示例 5：统计元素出现次数

运行代码

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

int main() {
    std::vector<int> scores = {85, 90, 85, 95, 85, 100};

    auto count85 = std::count(scores.begin(), scores.end(), 85);
    auto count60 = std::count(scores.begin(), scores.end(), 60);

    std::cout << "85 出现的次数：" << count85 << '\n';
    std::cout << "60 出现的次数：" << count60 << '\n';
    return 0;
}

运行结果如下。

85 出现的次数：3
60 出现的次数：0

分析：

在 scores 容器中，85 一共出现了 3 次，因此 count85 的结果为 3。而 60 在容器中从未出现过，因此 count60 的结果为 0。