STL 入门指南 — 数据结构作业 & 考试利器

前言

STL（Standard Template Library，标准模板库） 对我这种经常用 C++ 的人来说是个很熟悉的东西了，毕竟它也是陪伴我 OI 生涯的老熟人了。不过，对于刚接触编程还是在大一的 C 语言课的同学来说，C++ 是似乎个遥不可及的东西；至于 C++ 的库？那就是个更遥远的东西了。可能新人对学习 STL 有着畏惧的心理，但是别担心，这种工具只是为了程序员的方便而创造出来的，它只会便利你。

本文将以简单的方式带你入门 STL，领略 STL 的强大之处。要注意这只是一篇用于入门的文章，不是参考手册。如果你有一定的 STL 基础，想要了解更多容器的用法，请看下篇。

容器的引入

「栈」的引入。

假如你正在做「括号匹配判断」这道题，需要用到「栈」这个数据结构。于是你手写了几个栈相关的函数，定义了几个变量来存储栈。就像下面这样。

char stack[100];
int pos = 0;
 
void push(char x) { stack[++pos] = x; } // 入栈
 
void pop() { pos--; }                   // 出栈
 
char top() { return stack[pos]; }       // 栈顶

看似这样也很简单？那如果这道题需要两个「栈」结构呢，你会怎么写？也许是直接复制一份现有的代码，或者是给函数增加参数，把指定的 stack 及其 pos 传入。然而这样一份代码就难以复用了。而且当你做到新的题目，又要用到「栈」这个数据结构，还要再复制一遍，并根据题目情况修改变量名以及新增一些函数，十分麻烦。

这时候，STL 的作用便体现出来了。STL 有许多的容器（Container），栈（stack）也是其中的一种。更多的容器我们后面再来解释。

如何使用 STL 中的栈呢？

#include <stack>        // 引入「栈」头文件
 
using namespace std;    // 使用 std 命名空间（STL 都在这个命名空间里）
 
stack<char> st;         // 定义一个栈，存储字符（char）类型，名为 st

这样你便定义了一个 STL 里的栈。那么如何调用它的功能呢？只需要在这个栈后面输入 .（与访问结构体里的变量一致），就能输入函数名调用它提供的方法（Method）了。并且，在有代码补全的编辑器（比如 VS Code）中，你在敲下 . 后，会有一个完整的方法列表显示出来。就像这样：

如果这时，你想要把 x 这个变量入栈，就像这样写：

st.push(x);

如果此时需要两个栈就简单了，直接定义一个新的栈即可。

stack<char> st2;
st2.push(y);

这两个 push 相互独立，互不干扰（这也是面向对象编程的好处）。所以，你想要几个容器就定义几个。

stack 提供的方法列表

还有两个 C++11 标准提供的方法 emplace 和 swap。

前者可以传入一个数组，将这个数组的元素导入栈（等同于依次 push）；后者在许多其他 STL 容器中也能见到，用于交换两个容器中的内容，比如使用 st1.swap(st2) 就能把 st1 和 st2 里的内容相互交换。

与 stack 相似的容器还有 queue（队列）、deque（双端队列），在此不再赘述。

更多更全的容器可以看看下面的参考手册推荐。

迭代器的使用

看完第一部分的内容，你应该不免有疑惑：要是我想知道栈里面的内容该怎么办？这时就该迭代器出场了。

「迭代器」听起来是一个高大上的名词，但其实它只是解决一个实际问题的趁手工具。你可以把它理解为一种特殊的指针，当然，即使不会指针也能用。

比如我想要输出 st 这个栈里的所有元素，就像这样写：

for (stack<char>::iterator it = st.begin(); it != st.end(); it++) {
    cout << *it << endl; // C++ 的标准输出流语法
    // 等同于
    printf('%c\n', *it);
}

1. stack<char>::iterator it 定义了一个名为 it 的迭代器。注意双冒号前面，正好就是我们定义 st 时它的类型。
2. it = st.begin() 给 it 赋了一个值，这个值是 st 这个容器的起始位置（头迭代器）。
3. st.end() 表示 st 最后一个元素的位置的下一个位置（尾迭代器），因此要用 it != st.end() 作为循环条件，当 it 指到 st.end() 这个位置时，循环就该结束了。
4. it++ 在每一次循环后，it 会指向当前元素的下一个元素的位置。++ 是它内部实现的方法，用于跳转到下一个元素的位置。它不等同于普通指针的 +=1，因为内存空间也许不是连续的。

学过指针的同学应该知道，*it 是 it 指向元素的值。如果你不了解指针，记得输出时带上星号 * 就行。

如果我们入栈元素的依次是 1 2 3 4，那么上面这段代码的输出应该是：

4
3
2
1

看到这里，你应该明白了如何去使用迭代器遍历容器内的元素。利用它不仅能输出容器里面的元素，还能对元素依次进行操作。要注意 iterator 这个单词的拼写哦。

不过如果你用的 C++11 或更高版本的标准，stack<char>::iterator it = st.begin() 可以偷懒写成 auto it = st.begin()，这是因为 C++11 标准增加了 auto 关键字，能够自动推断赋值的类型。不过很多学校的 OJ 还是老标准，很可能不支持这个新特性。

反向迭代器

一般我们用正向迭代器，不过 STL 也提供了反向迭代器。

顾名思义，就是用来反向遍历一个容器的。

看下面的代码你应该就懂了。

for (stack<char>::reverse_iterator it = st.rbegin(); it != st.rend(); it++) { // 做些什么 }

利用算法（Algorithm）偷懒

algorithm 这个头文件提供了许多实用的函数。只需要这样引入即可使用。

#include <algorithm>
 
using namespace std;

那么它有哪些奇妙的功能呢？它的功能实在是有点多，我们只挑几个常见的来看。

sort 排序的使用

手写排序无疑是痛苦的体验了。还好 STL 内置了一个排序用的函数，而且是它的效率极高的。

基本用法

比如你有一个数组 a，里面存了 50 个不同的、乱序的 int 值，下标区间是 1～50。

想要把这 50 个值从小到大排列，只需要这样：

sort(a + 1, a + 51);
// 等价于
sort(&a[1], &a[51]);

第一个参数是首元素的地址，第二个参数是末元素的下一个元素的地址（可以理解成左闭右开区间，是不是和 end() 设计很像）。

细心的你应该会发现，首末位置相减正好是要排序的序列长度，所以第二个参数还是很好想到的。所以，如果是 n 个元素排序（下标从 1～n）就应该写 sort(a + 1, a + n + 1); 了。

自定义比较器

如果你想要把这 50 个元素从大到小排序呢？这时候就需要自定义比较器了。

sort() 这个函数其实还可以传入第三个参数，这个参数便是自定义比较器。想要从大到小排序，只需要这样定义一个返回类型为 bool 的函数作为比较比较器。

bool compare(int x, int y)
{
    return x > y;
}

排序时需要这样写：

sort(a + 1, a + 51, compare);

这样运行过后，a 数组就是从大到小排序的了。

可以这么理解比较器函数：返回 true，第一个参数排前面，返回 false，第二个参数排前面。

如果你喜欢更简洁的写法，可以使用 C++11 标准新增的 Lambda 表达式（匿名函数）作为第三个参数，这样一行就写完了。

sort(a + 1, a + 51, [](int x, int y) -> bool { return x > y; });

比较器函数同样很适用于结构体排序。比如像这样定义一个结构体。

struct Student
{
    char* name;
    int chinese;    // 语文成绩
    int math;       // 数学成绩
    int english;    // 英语成绩
}

想要把 50 个学生按照语文成绩的顺序从高到低排序，语文成绩一样时按照数学成绩排序，最后按照英语。比较器应该像这样写：

bool cmp(Student a, Student b)
{
    if (a.chinese > b.chinese) {
        return true;
    } else if (a.chinese == b.chinese) {  // 语文成绩一样
        if (a.math > b.math) {            // 先比数学
            return true;
        } else if (a.math == b.math) {    // 数学成绩一样
            return a.english > b.english; // 最后比较英语
        } else {
            return false;
        }
    }
    return false;
}

重载运算符的妙用

重载 < 小于运算也是一个优雅的让 sort 函数安自己预期工作的好办法。重载运算符也是 C++ 的特性，简单来说就是自己去给某个结构体/类定义运算。

比如上面的 Student 结构体，想要不通过 sort() 的第三个参数来按照上述规则排序，可以这样写：

struct Student
{
    char* name;
    int chinese;
    int math;
    int english;
 
    bool operator < (const Student& other) const
    {
        if (chinese > other.chinese) {
            return true;
        } else if (chinese == other.chinese) {
            if (math > other.math) {
                return true;
            } else if (math == other.math) {
                return english > other.english;
            } else {
                return false;
            }
        }
        return false;
    }
}

下面的主程序只需要这样写（假设有 50 个学生存到数组 s，下标 0～49）：

sort(s, s + 50);

这样执行过后，s 就按照规则排序了。

Algorithm 中的其他实用函数

下面的 begin 和 end 都是指针（迭代器）变量，值为一个地址。

参考手册

STL 容器参考：cplusplus.com Algorithm 功能参考：cplusplus.com （虽然这个网站界面很古典，但是例子和解释相当全。对英语水平要求不高。）

C++ 头文件参考：cppreference （和上面的网站有相似的内容，但支持中文）

下篇：STL 容器指南。这篇文章介绍了各种 STL 容器的用法，适合有基础的人食用。介绍了以下容器。