By FunnyAWM

运行环境说明：本章及以后章节换用 Windows 64 位 x86 MinGW GCC 编译器进行编译及运行。

在 C++ 中，我们有一组绝大部分编译器都共有的文件，这些文件被称作标准库。其中 STL 也在标准库的范围内。这一章我们来具体探讨一下 C++ 中的 STL（标准模板库）容器与标准库函数。

在这个仓库中可以找到大量对本章知识的应用。其中大部分容器出于 Qt 的限制改为了使用 Qt 提供的容器版本，与标准 STL 容器可能有部分不同（STL 容器可能缺失了部分方法），仅供参考。

1. STL 容器

1. 有哪些容器？

STL 中包含的常用容器有 string、vector、map、unordered_map 等。受限于文章篇幅，我们在这一章里只重点讲述 string 与 vector 容器，其他容器可能会有提及。

2. string：C++ 的字符串容器

string 容器应该是我们最常用的 STL 容器之一。string 容器可以通过使用 C 字符串、复制、移动、使用有参构造函数等进行初始化。其中类提供的特殊有参构造函数如下：

函数	描述
string(size_type n, char c)	创建一个包含 n 个元素的 string 对象，其中每一个元素都被初始化为字符 c
template<class Iter> string(Iter begin, Iter end)	从迭代器范围创建 string 对象
string(const string & str, string size_type pos = 0, size_type n = npos)	创建 string 对象，数据为从 pos 位置开始的 n 个字符（如果 n 没有指定则为到结尾）
string(initializer_list<char> il)	根据初始化列表创建对象（将在后面详细讲述容器初始化列表）

我们可以直接使用 cin 或 getline 函数来向 string 对象中输入数据。string 对象的长度是可变的，在对象空间不足时会自动扩容。例如：

cpp

std::string str1;
std::cin >> str1;
std::getline(std::cin, str1); // 这种方式同样可以用于从文件流构造字符串

getline 函数的第一个参数是一个 istream 流，它可以从用户键盘或文件中读取数据并初始化对应的对象。我们将在后续章节详细讲解 C++ 的 IO 流。

由于 string 类重载了 [] 运算符，它也可以被当做常规的 C 字符串被访问。

string 类提供了很多功能，包括查找子串、获取字符串长度、删除或替换字符等。STL 类中的所有函数都能够在 Cpp Reference 找到，在这里不再赘述。

3. vector：C++ 的可变长数组

与 string 类似，vector 也具有可变长度特性。vector 属于我们之前提到的泛型类，它接受一个任意类型的模板参数，然后根据模板类型来初始化对象。

vector 同样为我们提供了很多功能，包括获取元素数目、交换容器内容、获取容器的迭代器等。这里我们不再赘述其他方法，重点讲述一下 STL 容器中迭代器的概念。

4. 迭代器

迭代器可以被当做指向容器元素的指针使用，但其并不指向任何实际对象，常用于遍历整个容器。例如：

cpp

void MSTDataSource::updateFavoriteBatch(
    const QList<FavoriteUpdate> &updates) {
    query.exec("BEGIN TRANSACTION");
    for (auto update = updates.begin(); update != updates.end();
         ++update) {
        prepareStatement("UPDATE musicInfo SET favorite = :fav WHERE "
                         "fileName = :fileName");
        bindValue(":fav", update->isFavorite);
        bindValue(":fileName", update->fileName);
        execQuery();
    }
    query.exec("COMMIT");
}

当然，由于 QList 具有迭代器与可迭代特性，上述代码也可以用 C++ 的范围 for 循环进一步简化：

cpp

void MSTDataSource::updateFavoriteBatch(
    const QList<FavoriteUpdate> &updates) {
    query.exec("BEGIN TRANSACTION");
    for (const auto &update : updates) {
        prepareStatement("UPDATE musicInfo SET favorite = :fav WHERE "
                         "fileName = :fileName");
        bindValue(":fav", update.isFavorite);
        bindValue(":fileName", update.fileName);
        execQuery();
    }
    query.exec("COMMIT");
}

几乎所有具有迭代器的容器也都支持反向迭代操作。要实现反向迭代，只需要将 begin () 与 end () 改为 rbegin () 与 rend () 即可。

end () 迭代器指向的对象都是容器中最后一个对象的后一对象。所有涉及到双迭代器的操作（后续用 it1 代表靠前的迭代器，用 it2 代表靠后的），其包含的范围都是 [it1, it2)（包括 it1 指向的元素，但不包含 it2 指向的元素）。

迭代器有以下几个不同的类型：

输入迭代器：只读迭代器，单向移动，只能遍历一次，适用于从文件或输入流中读取数据；
输出迭代器：只写迭代器，单向移动，只能遍历一次，适用于将数据输出到文件或输出流中；
前向迭代器：结合了前两种迭代器的特点，同时支持了多次遍历；
双向迭代器：在前向迭代器的基础上实现了双向移动；
随机访问迭代器：在双向迭代器的基础上加入了任意位置跳转的能力。

随机访问迭代器支持常数时间的任意位置跳转（ $O (1)$ ），而其他迭代器只能通过逐步移动来访问元素，从当前位置移动到任意位置的时间复杂度为 $O (n)$ 。

名词解释

时间复杂度：描述了某个算法或操作需要耗费的时间随输入规模的变化趋势。其中 $O (1)$ 代表该算法或操作在使用任意参数时耗费的时间恒定，而 $O (n)$ 代表该算法或操作需要的时间随需要进行该操作的元素数量呈线性增长。相似的表述还有 $O (n^{2})$ （需要的时间随元素数呈二次增长）、 $O (l o g n)$ （需要的时间随元素数呈对数增长）、 $O (n l o g n)$ （需要的时间随元素数呈线性对数增长）、 $O (2^{n})$ （需要的时间随元素数呈指数增长）、 $O (n!)$ （需要的时间随元素数呈阶乘增长）等。

[!ERROR] 警告当容器发生结构性变化（例如 vector 扩容、deque 插入中间元素）时，针对当前容器的迭代器将全部失效，需要重新为其赋值。使用失效的迭代器可能会引起未定义行为。

2. 标准库算法

标准库算法为我们提供了一系列方便的功能，包括以下几方面：

非修改式序列操作（例如 for_each () 与 find () 等）；
修改式序列操作（例如 transform ()、random_shuffle ()、any_of ()、remove_if () 等）；
排序、交换等及其相关操作（例如 sort () 与 swap () 等）；
通用数字运算。

这些函数主要集中在 algorithm 头文件，一些基础数学运算函数则在 numeric 头文件中。

以下我们选取几个典型函数进行详细讲解（所有函数的使用方法都能够在 Cpp Reference 找到）。

关于这些函数实现的说明

any_of 与 remove_if 函数于 C++11 中被实现，而 random_shuffle 函数已在 C++17 中被移除，在 C++11 及以后，更推荐使用 std::shuffle。

1. for_each

该函数接收两个迭代器参数与一个函数指针或 Lambda 表达式，对迭代器范围内的所有对象执行函数或 Lambda 操作。

2. xxx_of 宇宙与 xxx_if 宇宙

这些函数都是从 C++11 开始引入的算法，极大方便了对容器的元素筛选与整体判断操作。

any_of 函数接收两个迭代器参数与一个函数指针或 Lambda 表达式，用于判断迭代器范围中是否有元素满足函数或 Lambda 表达式中描述的条件。其中函数指针或 Lambda 表达式必须满足谓词要求，即要求这个函数的返回类型必须为 bool。

all_of 对参数的要求同 any_of，用于判断迭代器范围中是否所有元素都满足要求。

none_of 对参数的要求同 any_of，用于判断迭代器范围中是否没有元素满足要求。

以上所有函数在满足判断时返回 true，不满足时返回 false。

remove_if 函数对参数的要求同 any_of，但是 remove_if 的作用为：将所有不满足函数或 Lambda 表达式中描述的条件的元素移动到容器尾，并返回一个新范围结尾的尾迭代器。这个函数配合 erase 函数可以用于快速筛选满足指定要求的值，被称为擦除移除手法。例如：

cpp

std::string str = "The quick brown fox jumps over the lazy dog";
str.erase(std::remove_if(str.begin(), str.end(),
                         [](unsigned char ch) {
                             return std::isspace(
                                 ch); // 需要包含cctype以使用isspace函数
                         }),
          str.end()); // 这个操作移除了容器中的所有空格字符

从 C++20 开始，这个操作也可以被直接被 erase_if 替代，直接实现移除擦除手法（~~一步到位~~）。

3. 排序与交换

1. 排序

sort 函数为我们提供了标准库内部支持的排序操作，对于可比较类型，直接调用 sort 函数即可。对于自定义类型，通常需要手动实现 operator < 以满足可比较特性，或手动传入返回 bool 类型的比较函数以满足可比较特性。如果没有实现可比较特性，编译器会在编译时抛出如下报错：

cpp

// 示例代码
#include <list>
using namespace std;

struct MyStruct {
    int a;
};

int main() {
    std::list<MyStruct> list;
    list.sort(); // 这里使用的是list容器的sort成员函数而非std::sort，这是因为list无法满足标准sort函数的随机访问迭代器要求（list只有双向迭代器）
}

text

In file included from E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c++/list:65,
                 from C:/Users/11429/CLionProjects/toturial/main.cpp:2:
E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c++/bits/stl_list.h: In instantiation of 'bool std::__detail::_Scratch_list::_Ptr_cmp<_Iter, void>::operator()(std::__detail::_List_node_base*, std::__detail::_List_node_base*) const [with _Iter = std::_List_iterator<MyStruct>]':
E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c++/bits/stl_list.h:203:18:   required from 'void std::__detail::_Scratch_list::merge(std::__detail::_List_node_base&, _Cmp) [with _Cmp = _Ptr_cmp<std::_List_iterator<MyStruct>, void>]'
E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c++/bits/list.tcc:515:23:   required from 'void std::__cxx11::list<_Tp, _Alloc>::sort() [with _Tp = MyStruct; _Alloc = std::allocator<MyStruct>]'
C:/Users/11429/CLionProjects/toturial/main.cpp:11:14:   required from here
E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c++/bits/stl_list.h:188:34: error: no match for 'operator<' (operand types are 'MyStruct' and 'MyStruct')
  188 |           { return *_Iter(__lhs) < *_Iter(__rhs); }
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

这里的报错原因是：由于我们既没有实现 operator<，也没有实现自定义比较函数，sort 函数由于无法建立严格弱序关系而报错。

DLC：从离散数学角度解释排序为什么要实现正确比较

STL 的排序算法要求元素上存在一种严格弱序关系，从数学上讲，这要求 operator < 函数或自定义比较函数必须定义该集合上的一个二元关系 $R (a < b)$ 。

STL 要求这样的 $R$ 必须满足以下三条公理：

非自反性（Irreflexive）：对于集合中的任意元素 $a$ , $a < a$ 恒为假。即任何元素都不能小于自身;
非对称性（Asymmetric）：对于任意元素 $a, b$ ，如果 $a < b$ 为真，那么 $b < a$ 必然为假。不能出现 “相互小于” 这种左右脑互搏的情况。
传递性（Transitive）：对于任意元素 $a, b, c$ ，如果 $a < b$ 且 $b < c$ ，那么 $a < c$ 必然为真。

如果其中的任意一条公理无法满足，就会导致该 $R$ 在集合上的关系不再是一个偏序关系。这将导致排序算法无法保证满足其不变式，进而导致算法结果不可预测。假设我们有以下代码：

cpp

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

struct Broken {
    int value;
};

int main() {
    auto broken_compare = [](const Broken &a, const Broken &b) {
        if (a.value % 2 == 0 && b.value % 2 == 1)
            return true;
        if (a.value % 2 == 1 && b.value % 2 == 0)
            return false;
        return a.value < b.value;
    };

    std::vector<Broken> vec = {{2}, {3}, {5}, {1}, {4}};
    std::sort(vec.begin(), vec.end(), broken_compare);

    // 结果不可预测，可能死循环或错误排序
    for (const auto &x : vec) {
        std::cout << x.value << " ";
    }
    return 0;
}

很明显上述代码中的 broken_compare 函数不满足偏序关系中要求的传递性，进而导致 sort 函数的结果不可预测，甚至导致未定义行为。

2. 交换

swap 函数能够实现对任意相同类型变量的值交换操作，这要求元素必须实现可复制特性（即有能够使用的复制构造函数，即便它是默认的）。从 C++11 开始，swap 函数会优先使用移动构造函数实现交换行为，如移动构造函数不可用，则会退化到复制行为。

对于 STL 容器，部分容器实现了自己的 swap 成员函数，用于快速交换整个容器，而不需要逐个交换元素。

1. STL 容器 ​

1. 有哪些容器？ ​

2. string：C++ 的字符串容器 ​

3. vector：C++ 的可变长数组 ​

4. 迭代器 ​

2. 标准库算法 ​

1. for_each ​

2. xxx_of 宇宙与 xxx_if 宇宙 ​

3. 排序与交换 ​

1. 排序 ​

DLC：从离散数学角度解释排序为什么要实现正确比较 ​

2. 交换 ​