初赛专题（一）：STL 容器与线性结构 —— vector、string、stack、queue

本讲定位：CSP-J 初赛系列的第一讲。初赛的阅读程序和完善程序大量使用 STL 容器，看不懂 v.push_back(x)、不知道 s.size() 返回什么类型。本讲把四个最常用的容器讲透：每个容器”是什么线性结构、怎么用、初赛怎么考、哪里有坑”。

前置知识：数组、for 循环、函数。

适合对象：CSP-J 初赛。全部内容都在考纲的入门级范围内。

1. STL 是什么，初赛为什么考它

STL（Standard Template Library，标准模板库）是 C++ 自带的一批现成的数据结构和算法。别人已经把”会自动变长的数组”“栈”“队列”写好、测好了，我们 #include 一下就能用。

初赛考它的方式有三种：

阅读程序：程序里直接用 vector、string，你得知道每个函数干什么、复杂度多少；
完善程序：挖掉的空常常就是 s.push(x)、q.front() 这类调用；
选择题：考容器操作的时间复杂度、栈的出栈序列、字符串的字典序比较。

四个容器和线性结构的对应关系，先记住这张总表：

容器	对应的线性结构	一句话概括	头文件
`vector`	顺序表（动态数组）	会自动变长的数组	`<vector>`
`string`	字符的顺序表	专门装字符的 `vector`，附赠字符串功能	`<string>`
`stack`	栈	只开放一端：后进先出（LIFO）	`<stack>`
`queue`	队列	一端进另一端出：先进先出（FIFO）	`<queue>`

所谓线性结构，就是元素排成一条线、每个元素最多一个前驱一个后继。vector 和 string 是”什么位置都能访问”的线性表；stack 和 queue 是操作受限的线性表——限制换来了清晰的语义，也换来了初赛爱考的性质（比如出栈序列）。

2. vector：会自动变长的数组

2.1 声明与初始化

#include<vector>
using namespace std;

vector<int> a;              // 空的，长度 0
vector<int> b(10);          // 长度 10，每个元素初始化为 0
vector<int> c(10, -1);      // 长度 10，每个元素都是 -1
vector<string> words;       // 装什么类型都行，包括装另一个容器
vector<vector<int>> g(n);   // n 行、每行可以不一样长的"二维数组"（邻接表就是它）

尖括号里写元素类型——这就是”模板”的含义：同一套容器，装任何类型。

2.2 常用操作与复杂度

vector<int> v;
v.push_back(5);       // 尾部追加一个元素             均摊 O(1)
v.pop_back();         // 删掉最后一个元素（不返回它）   O(1)
v.size();             // 当前元素个数                  O(1)
v.empty();            // 是否为空，等价于 size() == 0   O(1)
v[i];                 // 按下标访问，和数组一样          O(1)
v.back();             // 最后一个元素，即 v[v.size()-1]
v.front();            // 第一个元素，即 v[0]
v.clear();            // 清空                          O(n)
v.resize(m);          // 把长度改成 m（变长部分补 0）

vector 底层仍然是一段连续内存：装满了就整体搬家到一块两倍大的空间。所以它的性格和数组完全一样——随机访问 $O(1)$，尾部追加均摊 $O(1)$，但在中间 insert/erase 要挪动后面所有元素，$O(n)$。初赛选择题问”vector 在头部插入一个元素的时间复杂度”，答案是 $O(n)$，不是 $O(1)$。