Hanwan Space

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

充分利用 C++ 的 STL,可以让你做编程题事半功倍。


前言

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

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

容器的引入

「栈」的引入。

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

cpp
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 中的栈呢?

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

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

代码补全
代码补全

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

cpp
st.push(x);

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

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

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

stack 提供的方法列表

方法功能返回
empty()判断栈是否为空bool(空为 true,不空为 false
size()返回栈的大小size_type(可以理解成 int 这种数值类型)
top()返回栈顶元素value_type(就是当初定义时候,栈存储的值的类型)
push(value_type val)将某个元素 val 入栈void
pop()弹出栈顶元素void

还有两个 C++11 标准提供的方法 emplaceswap

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

stack 相似的容器还有 queue(队列)、deque(双端队列),在此不再赘述。

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

迭代器的使用

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

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

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

cpp
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,因为内存空间也许不是连续的。

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

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

plaintext
4
3
2
1

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

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

反向迭代器

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

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

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

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

利用算法(Algorithm)偷懒

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

cpp
#include <algorithm>
 
using namespace std;

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

sort 排序的使用

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

基本用法

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

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

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

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

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

自定义比较器

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

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

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

排序时需要这样写:

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

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

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

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

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

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

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

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

cpp
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() 的第三个参数来按照上述规则排序,可以这样写:

cpp
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):

cpp
sort(s, s + 50);

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

Algorithm 中的其他实用函数

下面的 beginend 都是指针(迭代器)变量,值为一个地址。

函数功能
swap(a, b)顾名思义,交换变量 ab 的值。
fill(begin, end, val)将区间 [begin, end) 填充值 val,适合用来填充数组/容器。
reverse(begin, end)将区间 [begin, end) 进行反转,比如把字符串反转一下,判断是不是回文串。
min(a, b) / max(a, b)顾名思义,返回 ab 中较小/较大的值。
min_element(begin, end) / max_element(begin, end)返回区间 [begin, end) 中最小/最大值的地址。
lower_bound(begin, end, val)返回有序区间 [begin, end),首个值为 val 的地址。
upper_bound(begin, end, val)返回有序区间 [begin, end),最后一个值为 val 的地址的下一个元素的地址。
unique(begin, end)对区间 [begin, end) 进行去重。

参考手册

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

C++ 头文件参考:cppreference (和上面的网站有相似的内容,但支持中文)

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

中英文名字功能
栈(stack)先进后出
队列(queue)先进先出
双端队列(deque)兼有栈和队列特性
链表(list)双向链表
向量(vector)动态数组
字符串(string)char* 更好用的字符串
优先队列(priority_queue)堆,内部有序
映射(map)构造键到值的映射
集合(set)不允许重复值,内部有序

  • STL
© hawa130转载请注明出处
License: CC BY-NC-SA 4.0

上一篇

全新的开始

这个建立于我高二时的博客,又在我大二时获得了新生。
下一篇

STL 使用指南 — 丰富实用的容器

各种各样的 STL 容器,承担着各式各样的使命。