C++ STL 常用容器与算法笔记

前言

STL 是 C++ 中非常重要的一部分，在算法竞赛、刷题和日常开发中都很常用。熟练掌握 STL，不仅可以减少代码量，也能让程序写得更规范、更高效。

这篇文章整理了算法竞赛中高频使用的几类 STL 容器与常用算法，代码风格以 C++11 / C++17 为主。文中尽量采用现代 C++ 写法，比如 auto、范围 for 循环等，方便理解和实际使用。

---

一、竞赛通用头文件与输入输出优化

在算法竞赛中，通常会使用万能头文件，并通过关闭同步流来提升输入输出速度。

示例代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 代码逻辑

    return 0;
}

说明

• #include <bits/stdc++.h>
  竞赛中常用的万能头文件，基本包含了常见的标准库内容。

• ios::sync_with_stdio(false);
  关闭 cin/cout 与 scanf/printf 的同步，加快输入输出。

• cin.tie(nullptr);
  解除 cin 和 cout 的绑定，进一步提高效率。

---

二、vector，动态数组

vector 是 STL 中最常用的容器之一，可以理解为长度可变的数组，并且支持随机访问。

1. 初始化方式

vector<int> a;              // 空数组
vector<int> b(10);          // 10 个元素，默认值为 0
vector<int> c(10, 5);       // 10 个元素，每个值都是 5
vector<int> d = {1, 2, 3};  // 初始化列表

2. 常用操作

vector<int> a;

a.push_back(1);     // 尾部添加元素
a.pop_back();       // 尾部删除元素

int len = a.size(); // 获取长度
a.clear();          // 清空容器

cout << a[0];       // 下标访问，不检查越界
cout << a.at(0);    // at 访问，会检查越界

3. 遍历方式

写法一：范围 for 循环

这是最推荐的写法，简洁直观。

vector<int> arr = {1, 2, 3, 4, 5};

// 只读遍历
for (int x : arr) {
    cout << x << " ";
}

// 修改元素时，用引用
for (int &x : arr) {
    x *= 2;
}

写法二：迭代器遍历

for (vector<int>::iterator it = arr.begin(); it != arr.end(); ++it) {
    cout << *it << " ";
}

也可以用 auto 简化：

for (auto it = arr.begin(); it != arr.end(); ++it) {
    cout << *it << " ";
}

4. 与算法配合使用

排序

sort(arr.begin(), arr.end());

二分查找

注意，使用二分查找前必须保证数组有序。

auto it = lower_bound(arr.begin(), arr.end(), 3);
int idx = it - arr.begin();

其中：

• lower_bound 返回第一个大于等于目标值的位置
• 迭代器减去首地址可以得到下标

---

三、stack 与 queue

这两类容器属于容器适配器，不支持随机访问，只能在指定位置操作元素。

---

四、stack，栈

栈的特点是 后进先出。

示例代码

#include <stack>

stack<int> st;

st.push(1);
st.push(2);

cout << st.top() << endl; // 2

st.pop();

cout << st.top() << endl; // 1

常用成员函数

• push(x)：入栈
• pop()：出栈
• top()：访问栈顶元素
• empty()：判断是否为空
• size()：返回元素个数

---

五、queue，队列

队列的特点是 先进先出。

示例代码

#include <queue>

queue<int> q;

q.push(1);
q.push(2);

cout << q.front() << endl; // 队首元素
cout << q.back() << endl;  // 队尾元素

q.pop();

常用成员函数

• push(x)：入队
• pop()：出队
• front()：访问队首
• back()：访问队尾
• empty()：判断是否为空
• size()：返回元素个数

---

六、priority_queue，优先队列

优先队列本质上是堆，默认情况下是 大顶堆。

1. 默认大顶堆

#include <queue>

priority_queue<int> pq;

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

cout << pq.top() << endl; // 5

pq.pop();

2. 小顶堆写法

#include <queue>
#include <vector>
#include <functional>

priority_queue<int, vector<int>, greater<int>> pq_small;

pq_small.push(3);
pq_small.push(1);
pq_small.push(5);

cout << pq_small.top() << endl; // 1

这里需要完整写出三个模板参数：

• 数据类型
• 底层容器类型
• 比较器

3. 自定义结构体排序

struct Node {
    int val;

    bool operator<(const Node &other) const {
        return val > other.val;
    }
};

priority_queue<Node> custom_pq;

这段代码表示 val 越小，优先级越高。

---

七、set，集合

set 用来存储不重复元素，并且会自动按升序排列。

示例代码

#include <set>

set<int> s;

s.insert(3);
s.insert(1);
s.insert(3); // 重复元素不会插入

s.erase(3);

if (s.find(1) != s.end()) {
    cout << "Found 1" << endl;
}

for (int x : s) {
    cout << x << " ";
}

特点总结

• 自动排序
• 自动去重
• 插入、删除、查找复杂度通常为 O(log n)

---

八、map，映射

map 用于存储键值对，键自动排序，且键唯一。

示例代码

#include <map>

map<string, int> mp;

mp["apple"] = 5;
mp["banana"] = 3;
mp.insert({"orange", 4});

if (mp.find("apple") != mp.end()) {
    cout << "Price: " << mp["apple"] << endl;
}

遍历方式

写法一：普通范围 for

for (auto &p : mp) {
    cout << p.first << " " << p.second << endl;
}

写法二：结构化绑定

需要 C++17 支持。

for (auto &[key, val] : mp) {
    cout << key << " => " << val << endl;
}

注意事项

mp[key] 在键不存在时会自动创建该键，并赋一个默认值。
做查询时，更推荐使用：

mp.find(key)
mp.count(key)

---

九、pair，二元组

pair 可以把两个数据放在一起保存，map 中的每个元素本质上就是一个 pair。

示例代码

#include <utility>

pair<int, string> p1(1, "student");
pair<int, string> p2 = {2, "teacher"};

cout << p1.first << " " << p1.second << endl;

常见用途

1. 作为容器元素

set<pair<int, int>> sp;
sp.insert({1, 2});

2. 作为函数返回值

pair<int, int> getPos() {
    return {3, 5};
}

---

十、algorithm 常用算法

使用这些算法时，通常需要包含头文件：

#include <algorithm>

1. sort，排序

vector<int> v = {5, 2, 9, 1};

sort(v.begin(), v.end());                 // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序

sort 的平均时间复杂度一般为 O(n log n)。

2. unique，去重

vector<int> v = {1, 2, 2, 3, 3, 3, 4};

sort(v.begin(), v.end());

auto last = unique(v.begin(), v.end());
v.erase(last, v.end());

说明：

• unique 不会真正删除元素
• 它会把重复元素挪到后面，并返回新的逻辑结尾
• 通常要和 erase 搭配使用

3. next_permutation，全排列

vector<int> v = {1, 2, 3};

do {
    for (int x : v) cout << x << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

如果希望从最小字典序开始生成全部排列，建议先排序：

sort(v.begin(), v.end());

---

十一、常见注意事项

1. 迭代器失效

在 vector 中插入或删除元素后，原来的迭代器、引用、指针有可能失效。
修改容器之后，不要继续使用旧迭代器。

2. map 下标访问风险

mp[key] 会在键不存在时自动插入。
查询时建议优先用：

mp.find(key)
mp.count(key)

3. 模板参数要写完整

像 priority_queue 这种模板类，自定义排序时要把模板参数写完整。
类型比较复杂时，使用 auto 能减少不少手误。

---

十二、总结

STL 是算法竞赛中的高频工具。对于初学者来说，先熟练掌握下面这些内容就已经很够用了：

• vector
• stack
• queue
• priority_queue
• set
• map
• pair
• sort
• unique
• lower_bound
• next_permutation

把这些内容练熟之后，再去学习 deque、unordered_map、unordered_set、multiset 等扩展容器，会顺畅很多。

---

结语

STL 的价值不只是会用，更重要的是知道它们适合什么场景、时间复杂度大概是多少、使用时有哪些坑。写题时能熟练选对容器和算法，效率会提升很多。

如果你刚开始学 C++ STL，建议边看边敲代码，把每个容器的常见操作都自己试一遍，这样印象会更深。