STL 容器

概念讲解

从底层结构"看见"容器

学习容器不能只背 API，而要在脑子里建立每个容器的"长相"。容器的所有特性——快在哪、慢在哪、是否有序、会不会去重——全部由它的底层数据结构决定。看懂了结构，复杂度表不用背也能推出来。

vector：一排连续的格子。 元素一个紧挨一个放在连续内存里。知道起点和下标就能一步算出元素地址，所以 v[i] 是 O(1)。格子装满后它会另找一块约两倍大的新区域、把旧元素整体搬过去（扩容），因此尾部追加是"均摊 O(1)"；而在中间插入需要挪动后面的所有元素，是 O(n)。

 下标:   0    1    2    3
       +----+----+----+----+
       | 3  | 1  | 4  | 1  |   内存连续，v[2] 一步跳到
       +----+----+----+----+

list：用指针串起来的节点。 每个节点除数据外还存前后两个指针，内存不连续。插入删除只需修改指针（O(1)），但访问第 i 个元素必须沿指针从头走（O(n)），竞赛中很少使用，了解即可。

 +----+    +----+    +----+
 | 3  | -> | 1  | -> | 4  |
 +----+    +----+    +----+

set / map：一棵始终保持平衡的二叉搜索树（红黑树）。 左子树都比根小、右子树都比根大，按"左-根-右"的中序遍历天然得到升序序列；红黑树会自动保持平衡，树高约为 $\log n$，所以增删查都是 O(log n)。

         5
        / \
       3   7        存放 {1,3,5,7,9}
      /     \       中序遍历：1 3 5 7 9（自动有序）
     1       9

unordered_set / unordered_map：一张哈希表。 元素通过哈希函数被分配到一个个"桶"中，理想情况下一次就能定位，平均 O(1)；代价是元素之间没有任何顺序保证。

 桶 0 | -> (k,v) -> (k,v)
 桶 1 |
 桶 2 | -> (k,v)
  ...

priority_queue：用数组表示的完全二叉树（堆）。 下标从 1 开始时，节点 i 的父亲是 i/2，孩子是 2i 和 2i+1。大根堆保证每个父亲都不小于孩子，所以根（数组开头）永远是最大值，取最值只需 O(1)，插入弹出为 O(log n)。

 数组下标:   1    2    3    4    5
          +----+----+----+----+----+
          | 9  | 7  | 5  | 1  | 3  |
          +----+----+----+----+----+
              9            数组表示的大根堆
             / \
            7   5          每个父亲 >= 孩子
           / \               堆顶 9 即最大值
          1   3

stack / queue：包装出来的适配器。 它们本身不负责存储数据，而是套在 deque（默认底层容器）外面，只开放"一端进出"或"两端各管一头"的受限接口。

常用容器与复杂度

如何选择容器

1. 默认首选 vector：需要按下标访问、只在尾部追加的场景占绝大多数，连续内存对缓存也最友好。
2. 需要频繁在头部增删（如 BFS 队列的底层）→ deque。
3. 要求元素始终有序、去重，或按值快速查找且数据量不小 → set / map。
4. 只关心"在不在"或"键对应什么值"，不关心顺序，追求平均 O(1) → unordered_set / unordered_map。
5. 每次都要取当前最大（小）值，如 Top K、Dijkstra → priority_queue。
6. 先进后出（括号匹配、表达式、DFS）用 stack；先进先出（BFS）用 queue。

vector

vector 是竞赛中使用频率最高的容器，相当于长度可以自动增长的数组。

1234567891011#include <vector>

vector<int> v;
v.push_back(1);     // 尾部添加
v.pop_back();       // 尾部删除（不返回被删元素）
v.size();           // 元素个数
v.empty();          // 是否为空
v[i];               // 随机访问，O(1)，注意下标不能越界
v.front();          // 第一个元素，等价 v[0]
v.back();           // 最后一个元素，等价 v[v.size()-1]
v.clear();          // 清空全部元素

常见的构造方式与二维数组：

123456789101112vector<int> a;                  // 空数组
vector<int> b(5);               // 5 个元素，初值均为 0
vector<int> c(5, -1);           // 5 个元素，初值均为 -1
vector<int> d = {3, 1, 4, 1, 5}; // 列表初始化

int n = 4, m = 5;
vector<vector<int>> g(n, vector<int>(m));  // n 行 m 列的二维数组，初值全 0
g[0][0] = 1;

for (int i = 0; i < n; i++)            // 按下标遍历
    for (int j = 0; j < m; j++) { ... }
for (int x : d) cout << x << ' ';      // 范围 for 遍历，只读

reserve 与 resize 是初学者最容易混淆的一对：

1234vector<int> v;
v.reserve(100);  // 只预留容量（capacity），size 仍是 0，不能访问 v[0]
v.resize(10);    // 改变元素个数：多出的元素补 0，此时 v[0..9] 都可访问
v.resize(20, -1); // 新增的 10 个元素填 -1，原有元素不变

如果事先知道要放入多少元素，先 reserve(n) 可以避免 push_back 过程中反复扩容、整体搬家的开销。

deque

deque（双端队列）支持在头部和尾部都 O(1) 增删，同时也支持 [i] 随机访问；代价是内存分段连续、额外开销比 vector 略大。

1234567891011#include <deque>

deque<int> dq;
dq.push_back(2);    // 尾部加
dq.push_front(1);   // 头部加
dq.pop_back();      // 尾部删
dq.pop_front();     // 头部删
dq.front();         // 队首
dq.back();          // 队尾
dq[0];              // 支持随机访问 O(1)
dq.clear();

stack 与 queue

它们是容器适配器，默认基于 deque 实现，接口刻意做得很小。

1234567891011121314#include <stack>
#include <queue>

stack<int> st;
st.push(1);         // 入栈
st.top();           // 查看栈顶（不弹出）
st.pop();           // 弹出栈顶（pop 不返回元素！）
st.empty(); st.size();

queue<int> q;
q.push(1);          // 入队（尾部）
q.front();          // 队首
q.back();           // 队尾
q.pop();            // 队首出队

stack 是先进后出（LIFO），用于括号匹配、表达式求值、DFS 的手动栈；queue 是先进先出（FIFO），用于 BFS。两者都不能遍历、不能按下标访问。

set

set 自动完成排序与去重：重复插入同一个值不会产生第二份拷贝，遍历结果总是从小到大。

12345678910111213141516#include <set>

set<int> s;
s.insert(3);        // 插入，重复插入无效
s.insert(1);
s.insert(5);
s.erase(1);         // 按值删除
s.count(3);         // 存在返回 1，不存在返回 0（set 中只有这两种结果）
s.find(3);          // 返回指向该元素的迭代器；不存在时返回 s.end()
s.size();           // 大小
s.empty(); s.clear();

for (int x : s) cout << x << ' ';   // 输出 3 5，自动升序

auto it = s.lower_bound(3);  // 第一个 >= 3 的元素
auto it2 = s.upper_bound(3); // 第一个 > 3 的元素

判断元素是否存在，推荐用 s.find(x) != s.end() 或 s.count(x)。lower_bound / upper_bound 是 set 的高频考点，可以在 O(log n) 内找到区间边界。

如果要让自定义类型放进 set，必须为它定义比较规则（红黑树需要靠它排序）：

12345678struct Student {
    int id;
    string name;
    bool operator<(const Student& o) const {
        return id < o.id;      // 按 id 排序、去重
    }
};
set<Student> ss;

map

map 存储"键 → 值"的映射，键自动排序且不重复。最常用的场景是计数。

12345678910111213#include <map>

map<string, int> mp;
mp["key"] = 1;      // 插入/修改
mp.erase("key");    // 删除
mp.count("key");    // 键是否存在
mp.find("key");     // 查找，不存在返回 mp.end()
mp.size();          // 大小

// 遍历（按键升序输出）
for (auto& [k, v] : mp) {
    cout << k << ": " << v << endl;
}

特别注意 mp[key] 的副作用：键不存在时会自动插入一个默认值（int 为 0）。这正好让计数写法 mp[x]++ 成立（第一次出现时先创建 0 再加 1）；但如果只想查询、不想增加元素，应使用 find 或 count。

1234567map<char, int> cnt;
cnt['a']++;         // 'a' 不存在：先自动创建为 0，再自增为 1
cnt['a']++;         // 已存在：直接自增为 2

if (cnt.count('z')) { ... }        // 只判断，不插入
auto it = cnt.find('z');           // 只查找，不插入
if (it != cnt.end()) cout << it->second;

unordered_set 与 unordered_map

接口与 set/map 几乎完全相同，区别只在于底层是哈希表：平均 O(1) 查找，但不保证遍历顺序。

12345678910111213#include <unordered_map>
#include <unordered_set>

unordered_map<string, int> cnt;
cnt["apple"]++;
cnt["banana"]++;
for (auto& [k, v] : cnt) {
    cout << k << ": " << v << endl;  // 输出顺序不确定，不要依赖
}

unordered_set<int> us;
us.insert(3);
if (us.count(3)) { ... }            // O(1) 平均

选择建议：只需要快速查找且不关心顺序时用 unordered 版本，速度通常更快；需要按序遍历、找前驱后继（lower_bound），或担心哈希冲突被卡时，用 set/map 更稳妥。

list（了解）

双向链表，头尾增删 O(1)，但不支持 [i] 随机访问。竞赛中绝大多数场景都被 vector + deque 覆盖，了解即可。

1234567#include <list>

list<int> l;
l.push_front(1);
l.push_back(2);
l.pop_front();
l.pop_back();

pair

pair 把两个值捆绑成一个整体，在坐标、边权、多关键字排序中极其常用。

123456789#include <utility>   // <bits/stdc++.h> 已包含

pair<int, string> p = {1, "abc"};
cout << p.first << ' ' << p.second;   // 1 abc

vector<pair<int, int>> points;
points.push_back({3, 5});             // 也可用 make_pair(3, 5)

sort(points.begin(), points.end());   // 默认先比 first，相同再比 second

优先队列

优先队列（堆）每次弹出的都是当前优先级最高的元素。默认是大根堆，堆顶为最大值；需要最小值优先时要手动改成小根堆。

123456789101112#include <queue>

// 大根堆（默认）
priority_queue<int> maxHeap;

// 小根堆：第二个参数指定底层容器，第三个参数指定比较方式
priority_queue<int, vector<int>, greater<int>> minHeap;

maxHeap.push(1);    // 插入，O(log n)
maxHeap.top();      // 查看堆顶，O(1)
maxHeap.pop();      // 弹出堆顶，O(log n)
maxHeap.empty(); maxHeap.size();

三个模板参数的写法是固定套路，记忆方法是：小根堆就加 vector<int>, greater<int>。

让自定义类型进优先队列，需要提供比较规则——注意比较方向与直觉相反：返回 a 排在 b 后面 为真时，b 优先出堆。

123456789struct Node {
    int id, dist;
};
struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.dist > b.dist;   // dist 小的排前面（小根堆），用于 Dijkstra
    }
};
priority_queue<Node, vector<Node>, Cmp> pq;

priority_queue<pair<int,int>> 可以直接使用：默认先按 first、再按 second 取大值。

bitset（位数组，入门）

bitset 把一个固定长度的 0/1 序列当作容器操作，可以按下标访问每一位，常用于状态压缩与调试时打印变量的二进制形式。

1234567#include <bitset>

bitset<8> b(42);          // 用整数 42 构造：00101010
cout << b << endl;        // 直接输出二进制
b.set(0);                 // 第 0 位置 1
b.flip();                 // 全部取反
cout << b.count() << endl; // 其中 1 的个数

bitset 的完整用法（打印补码、位运算、突破 64 位状态压缩等）在「位运算进阶」一节有专门讲解。

考点分析

初赛考查方式

1. 选择题： 容器特性
2. 程序阅读： STL 操作
3. 编程题： 容器应用

常见考点

• 根据底层结构推导容器特性与时间复杂度
• 根据题目场景选择合适容器
• set / map 的有序性、去重与 lower_bound
• map 的 [] 自动插入语义
• 大根堆 / 小根堆的写法与自定义比较
• 迭代器失效与边遍历边删除

例题精讲

例题 1：set 去重

题目： 对数组去重并排序。

解答：

123set<int> s;
for (int i = 0; i < n; i++) s.insert(a[i]);
for (int x : s) cout << x << " ";

例题 2：map 计数

题目： 统计字符串中每个字符出现次数。

解答：

12345map<char, int> mp;
for (char c : s) mp[c]++;
for (auto& [c, cnt] : mp) {
    cout << c << ": " << cnt << endl;
}

例题 3：小根堆求 Top K

题目： 不断读入数字，最后保留最大的 3 个并按升序输出。

解答： 维护一个大小始终不超过 3 的小根堆：新元素入堆后，若堆超过 3 个就弹掉堆顶（当前最小值）。最后堆里剩下的恰好是全局最大的 3 个数。

123456789101112131415161718#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {5, 1, 9, 3, 7, 2, 8};
    priority_queue<int, vector<int>, greater<int>> pq;  // 小根堆

    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > 3) pq.pop();  // 弹走最小的，保留最大的 3 个
    }

    while (!pq.empty()) {                   // 依次弹出 7 8 9（升序）
        cout << pq.top() << ' ';
        pq.pop();
    }
    return 0;
}

练习题

1. vector 和 deque 的区别是什么？

2. set 和 unordered_set 的区别是什么？

3. 如何创建小根堆？

12345678910#include <queue>

// 小根堆
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(3);
pq.push(1);
pq.push(2);

cout << pq.top();  // 输出 1

4. 如何求一个数组中第 k 大的数？

12345678int kthLargest(vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

易错点

⚠️ 注意：

1. set 自动排序和去重，遍历总是升序；unordered_set 既不排序也不保证遍历顺序。
2. map 用 [] 访问不存在的 key 会自动插入默认值 0，纯查询要用 find/count。
3. priority_queue 默认是大根堆，取最小值要写 priority_queue<int, vector<int>, greater<int>>；取 top 前先确认堆非空。
4. vector 扩容会使原先的迭代器、引用全部失效；reserve 只预留容量，不改变 size，不能访问还没 resize 出来的元素。
5. 边遍历 set/map 边删除时，要用 it = s.erase(it) 接收返回的下一个迭代器，先 erase(it++) 或直接 ++it 再删都是常见错误。
6. stack/queue 的 pop() 不返回元素，取值得先调 top()/front()。
7. size() 返回的是无符号整数，与 int 做减法或比较时建议先强转 (int)v.size()，避免下溢成巨大的数。
8. unordered 容器平均 O(1) 但最坏 O(n)，且自定义类型作 key 需额外提供哈希函数；int、string 等内置类型可直接使用。
9. 自定义类型放入 set/map/priority_queue 必须定义明确的比较规则，否则编译报错。