STL速查

通用提示：

所有容器均需 using namespace std;。

所有容器都有 .size() (大小) 和 .empty() (判空)，复杂度均为 $O(1)$，下文不再赘述。

这里的 $N$ 指容器当前元素个数。

一、顺序容器 (动态数组与字符串)

1. `vector` (动态数组)

头文件: <vector>

特点: 尾部操作 $O(1)$，中间插入/删除 $O(N)$，随机访问 $O(1)$。

声明与初始化

C++

vector<int> v;              // 空数组
vector<int> v(n);           // 大小为 n，默认值为 0
vector<int> v(n, val);      // 大小为 n，初值为 val
vector<int> v = {1, 2, 3};  // 列表初始化
vector<vector<int>> mat(n, vector<int>(m)); // n*m 二维数组

访问

C++

v[i];           // 下标访问 (不检查越界)
v.at(i);        // 下标访问 (越界抛异常，慢)
v.front();      // 第一个元素
v.back();       // 最后一个元素

修改

C++

v.push_back(val);   // 尾插
v.pop_back();       // 尾删
v.clear();          // 清空
v.resize(n, val);   // 重置大小为 n，新增部分补 val

迭代器与算法配合

C++

1
2
3

sort(v.begin(), v.end());                   // 排序
reverse(v.begin(), v.end());                //哪怕翻转
v.erase(unique(v.begin(), v.end()), v.end()); // 去重模板

2. `string` (字符串)

头文件: <string>

特点: 功能类似 vector<char>，但提供丰富的文本处理方法。

声明与拼接

C++

string s = "hello";
string s(n, 'c');    // n 个字符 'c'
s += "world";        // 拼接 $O(len)$
s = s + t;

截取与查找 (重点)

C++

1
2
3

s.substr(pos, len);       // 返回从 pos 开始长为 len 的子串 (不写 len 截取到末尾)
s.find(str, pos);         // 从 pos 开始找 str，返回下标；找不到返回 string::npos
s.rfind(str);             //以此类推，反向查找

修改

C++

1
2
3

s.insert(pos, str);       // 在 pos 处插入
s.erase(pos, len);        // 删除从 pos 开始 len 个字符
s.replace(pos, len, str); // 替换

类型转换

C++

1 2	to_string(123); // int/long long -> string stoi(s); stoll(s); // string -> int / long long

二、双端队列与容器适配器

3. `deque` (双端队列)

头文件: <deque>

特点: 头尾增删均为 $O(1)$，支持随机访问（比 vector 慢），常数较大。

操作

C++

dq.push_front(val);  // 头插
dq.push_back(val);   // 尾插
dq.pop_front();      // 头删
dq.pop_back();       // 尾删
dq[i];               // 随机访问

4. `stack` (栈)

头文件: <stack>

特点: LIFO (后进先出)，不支持迭代器和随机访问。

操作

C++

1
2
3

st.push(val);   // 入栈
st.pop();       // 出栈 (无返回值)
st.top();       // 获取栈顶元素

5. `queue` (队列)

头文件: <queue>

特点: FIFO (先进先出)，不支持迭代器。

操作

C++

q.push(val);    // 入队
q.pop();        // 出队 (无返回值)
q.front();      // 队首元素
q.back();       // 队尾元素

6. `priority_queue` (优先队列/堆)

头文件: <queue>

特点: 自动排序，插入/删除 $O(\log N)$，查看堆顶 $O(1)$。

声明

C++

1
2
3

priority_queue<int> pq;                            // 大根堆 (默认)
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
// 自定义结构体需重载 < 运算符，或者写 struct cmp

操作

C++

1
2
3

pq.push(val);   // 入堆
pq.pop();       // 堆顶元素出堆
pq.top();       // 查看堆顶

三、关联容器 (有序，红黑树实现)

复杂度: 增删查均为 $O(\log N)$。

注意: multiset / multimap 允许键值重复。

7. `set` / `multiset` (集合)

头文件: <set>

特点: set 去重且有序，multiset 不去重但有序。

操作

C++

s.insert(val);          // 插入
s.erase(val);           // set: 删除值为 val 的元素; multiset: 删除所有值为 val 的元素
s.erase(iterator);      // 删除迭代器指向的元素 (multiset 删单个常用技巧)
s.find(val);            // 返回迭代器，找不到返回 s.end()
s.count(val);           // 返回出现次数 (set 只有 0 或 1)

二分查找 (核心)

注意：必须用成员函数，用 std::lower_bound 会退化为 $O(N)$

C++

1 2	s.lower_bound(val); // 返回首个 >= val 的迭代器 s.upper_bound(val); // 返回首个 > val 的迭代器

遍历

C++

1 2	for(auto it = s.begin(); it != s.end(); ++it) { cout << it; } // 访问最大值: s.rbegin()

8. `map` / `multimap` (映射)

头文件: <map>

特点: Key-Value 对，按 Key 排序。

访问与插入

C++

1
2
3

mp[key] = val;          // (仅 map) 下标访问，若 key 不存在会自动创建，初值为 0
mp.at(key);             // 访问，不存在抛异常
mp.insert({key, val});  // 插入 pair

查找与删除

C++

mp.find(key);           // 返回迭代器 (pair 指针)，it->first 是键, it->second 是值
mp.count(key);          // 判断 key 是否存在
mp.erase(key);          // 删除
mp.erase(iterator);

二分

C++

1	mp.lower_bound(key); // 针对 Key 查找 >= 的迭代器

四、无序关联容器 (哈希表实现)

复杂度: 增删查平均 $O(1)$，最坏 $O(N)$。

注意: 内部无序，不支持 lower_bound/upper_bound。

9. `unordered_set` / `unordered_map`

头文件: <unordered_set>, <unordered_map>

特点: 语法几乎同 set/map，但通常更快。

差异点
- 没有 lower_bound, upper_bound。
- 没有自动排序。
- 自定义类型作为 Key 需要手写 Hash 函数。

用法示例

C++

1
2
3

unordered_map<int, int> ump;
ump[5] = 10;
if (ump.count(5)) { ... }

五、链表 (较少用)

10. `list` (双向链表)

头文件: <list>

特点: 任意位置插入删除 $O(1)$ (需已知迭代器)，不支持随机访问。

操作

C++

lst.push_back(val);
lst.push_front(val);
lst.insert(it, val);    // 在迭代器 it 前插入
lst.erase(it);          // 删除迭代器 it 处元素

特殊接合 (Splice)

C++

1	lst.splice(pos_it, other_list); // 将 other_list 所有元素移动到 pos_it 之前 (O(1))

专用算法 (比 std:: 快)

C++

lst.sort();             // 必须用成员函数 sort，不能用 std::sort
lst.remove(val);        // 删除所有值为 val 的元素
lst.unique();           // 去除相邻重复
lst.reverse();          // 翻转

一、 顺序容器 (动态数组与字符串)

1. vector (动态数组)

2. string (字符串)

二、 双端队列与容器适配器

3. deque (双端队列)

4. stack (栈)

5. queue (队列)

6. priority_queue (优先队列/堆)

三、 关联容器 (有序，红黑树实现)

7. set / multiset (集合)

8. map / multimap (映射)

四、 无序关联容器 (哈希表实现)

9. unordered_set / unordered_map

五、 链表 (较少用)

10. list (双向链表)