前言
最近因为刷题和实际业务的开发，在重新整理 C++ 的笔记。
发现 STL 这东西平时一直在用，但很多时候只是依赖 AI 或者自动补全，没有认真了解过他们的特性。
比如 vector 为什么默认这么常用，map 和 unordered_map 到底该怎么选，list 又为什么看起来很强但实际出场率不高，这些东西如果只是记住几个接口，过一阵子还是会混。
所以这篇文章干脆把我目前最常碰到的一批 STL 类型先汇总一下。本文不追求把每个类的所有接口都列完，而是重点整理：
- 它一般适合拿来干什么
- 平时该怎么初始化
- 最常用的方法有哪些
- 这些方法的复杂度大概是什么水平
- 遇到题目或者实际业务时，为什么会优先想到它
顺序上我没有按字母排，而是按“通常上手时比较容易理解的，和我觉得更常先学到的”来排。
string
介绍与使用场景
std::string 用来保存和处理字符串。严格来说它是 std::basic_string<char> 的常用别名，但平时基本直接把它当作字符串类型来用就行。
- 业务开发里，一般用它保存用户名、文件路径、配置项、日志文本和各种普通文本。相比手写字符数组，它会自动管理内存，省心很多。
- 算法题里，一般用它处理回文串、子串、字符统计、模拟题和各种字符串匹配问题。它支持随机访问，和 STL 算法也很好配合。
- 如果要在头部或中间频繁插入、删除字符，就要注意它后面的字符通常需要整体移动。
初始化方式
#include <string>
using namespace std;
// 定义一个空字符串
string text;
// 用字符串字面量 "hello" 初始化字符串
string text1 = "hello";
// 用字符串字面量 "hello" 直接构造字符串
string text2("hello");
// 构造一个包含 5 个字符 'a' 的字符串，即 "aaaaa"
string text3(5, 'a');
// 复制 text1，构造一个内容相同的字符串
string text4(text1);
// 从 text1 的下标 1 开始复制 3 个字符，即 "ell"
string text5(text1, 1, 3);
// 复制区间 [text1.begin(), text1.begin() + 3) 内的字符，即 "hel"
string text6(text1.begin(), text1.begin() + 3);
字符和字符串别写混：
// 定义一个字符，内容是 'a'
char ch = 'a';
// 定义一个字符串，内容是 "abc"
string text = "abc";
常用方法
设原字符串长度为 n，参与操作的新内容长度为 m：
查看与访问
| 方法 | 作用与复杂度 |
|---|---|
size()、length()、empty() |
size() 和 length() 返回字符串的字符数量，empty() 判断字符串是否为空。时间复杂度都是 O(1)。 |
operator[]、at()、front()、back() |
分别用于按下标访问字符、按下标安全访问字符、访问第一个字符和访问最后一个字符，都是 O(1)。at() 会检查越界，operator[] 不会。 |
修改内容
| 方法 | 作用与复杂度 |
|---|---|
push_back(ch) |
在字符串末尾追加一个字符。不重新分配内存时是 O(1)；连续追加时均摊 O(1)；单次最坏 O(n)。 |
pop_back() |
删除字符串末尾的一个字符，复杂度是 O(1)。 |
append()、operator+= |
把新的字符或字符串追加到末尾。至少要复制新增内容，最坏 O(n + m)。 |
operator+ |
拼接字符串并返回一个新字符串。因为需要创建新字符串并复制内容，时间复杂度是 O(n + m)。 |
insert() |
在指定位置插入字符或字符串。在中间插入通常需要移动后续字符，最坏 O(n + m)。 |
erase(pos, count) |
从下标 pos 开始删除最多 count 个字符。删除后可能需要搬移剩余字符，最坏 O(n)。 |
clear() |
删除全部字符，使字符串变为空字符串。通常按 O(n) 理解更安全，不要假设它一定是常数时间。 |
查找、截取与底层数据
| 方法 | 作用与复杂度 |
|---|---|
find()、rfind() |
分别从前向后、从后向前查找字符或子串；没有找到时返回 string::npos。如果是查找单个字符，最坏一般按 O(n) 理解；如果是查找长度为 m 的子串，标准最坏上界可按 O(nm) 理解，具体实现可能更快。 |
substr(pos, count) |
从下标 pos 开始截取最多 count 个字符，并返回一个新字符串。复杂度和实际复制的字符数成正比。 |
c_str()、data() |
返回指向底层连续字符数据的指针，复杂度是 O(1)。字符串内容一改，之前拿到的指针可能失效。 |
示例
拼接一个简单的问候语：
#include <iostream>
#include <string>
using namespace std;
int main() {
string name = "小明";
string message = "你好，";
message += name;
message.push_back('！');
// 输出 "你好，小明！"
cout << message << '\n';
}
截取文件扩展名：
#include <iostream>
#include <string>
using namespace std;
int main() {
string filename = "notes.md";
string::size_type pos = filename.rfind('.');
if (pos != string::npos) {
string ext = filename.substr(pos + 1);
cout << "扩展名：" << ext << '\n';
}
}
substr() 很方便，但它会生成一个新字符串。
如果只是临时看一段内容，而且特别在意性能，后面可以再去了解 string_view。
pair
介绍与使用场景
pair 用来把两个值组合成一个整体。它不是完整容器，更像一个很轻量的“二元打包工具”。
- 业务开发里，一般用它临时表示“键和值”、“名字和编号”、“坐标和状态”这类成对数据。要是字段含义已经很稳定，通常还是自己写结构体更清楚。
- 算法题里，用得非常多。比如坐标、边权与节点、数值与下标、函数返回两个结果，这些都很适合用
pair。 - 它的优点是省事，缺点也很明显：
first和second的语义不如成员名直观。
初始化方式
#include <string>
#include <utility>
// 默认构造一个 pair，first 为 0，second 为空字符串
std::pair<int, std::string> p1;
// 构造一个 pair，first 为 1，second 为 "apple"
std::pair<int, std::string> p2(1, "apple");
// 使用列表初始化构造一个 pair，first 为 2，second 为 "banana"
std::pair<int, std::string> p3{2, "banana"};
// 构造一个 pair，并由参数自动推导出两个成员的类型
auto p4 = std::make_pair(3, std::string("orange"));
C++17 开始还可以让编译器推导模板参数：
// 由初始值推导出 pair<int, string>
std::pair p5{4, std::string("pear")};
常用方法
pair 就两个成员，所以很多操作都可以直接按常数时间理解：
访问与构造
| 方法 | 作用与复杂度 |
|---|---|
first、second |
分别访问 pair 中的第一个成员和第二个成员，复杂度是 O(1)。 |
std::make_pair(a, b) |
根据 a 和 b 构造一个 pair，并自动推导成员类型。结构本身可按 O(1) 理解，实际成本取决于成员构造或移动。 |
交换与比较
| 方法 | 作用与复杂度 |
|---|---|
swap(other) |
交换当前 pair 和另一个 pair 的两个成员。结构层面是 O(1)，具体成本取决于成员类型。 |
| 比较运算 | 按字典序比较两个 pair，先比较 first，只有无法据此确定结果时才比较 second。最多比较两个成员；若成员比较本身都是 O(1)，整体可按 O(1) 理解；如果成员本身是 string 这类对象，实际成本还要把成员比较开销算进去。 |
示例
用 pair 保存商品名和数量：
#include <iostream>
#include <string>
#include <utility>
using namespace std;
int main() {
pair<string, int> item{"apple", 5};
cout << "商品：" << item.first << '\n';
cout << "数量：" << item.second << '\n';
item.second += 2;
cout << "更新后的数量：" << item.second << '\n';
}
如果数据语义已经比较复杂，pair 就会开始别扭：
struct Student {
string name;
int age;
};
这种时候通常不如直接写结构体。
array
介绍与使用场景
array 是对固定长度数组的封装，长度必须在编译期确定。
它和 C 风格的数组一样使用连续内存，但接口更现代一些。
- 业务开发里，一般适合长度固定、含义明确的数据，比如一周 7 天的统计值、固定数量的传感器数据、固定字段的协议内容。
- 算法题里，一般适合字母计数、方向数组、固定维度状态等场景。尤其是“长度就是 26、4、8、10 这种写死的值”时，它会比
vector更直接。 - 如果元素数量需要运行时变化，就别用
array，该换vector。
初始化方式
#include <array>
using namespace std;
// 定义一个长度为 5 的固定数组，所有元素初始化为 0
array<int, 5> nums{};
// 定义一个长度为 5 的固定数组，并依次初始化全部元素
array<int, 5> nums1{1, 2, 3, 4, 5};
// 定义一个长度为 5 的固定数组，前两个元素为 1、2，其余元素初始化为 0
array<int, 5> nums2{1, 2};
// C++17 起可根据初始值推导为 array<int, 3>
array nums3{1, 2, 3};
要注意，长度是类型的一部分：
// 定义一个长度为 3 的固定数组，所有元素初始化为 0
array<int, 3> a{};
// 定义一个长度为 5 的固定数组，所有元素初始化为 0
array<int, 5> b{};
这两个不是同一种类型。
常用方法
设数组长度为 N：
查看与访问
| 方法 | 作用与复杂度 |
|---|---|
size()、empty() |
size() 返回数组的固定长度，empty() 判断数组长度是否为 0，复杂度都是 O(1)。 |
operator[]、at()、front()、back() |
分别用于按下标访问元素、按下标安全访问元素、访问第一个元素和访问最后一个元素，都是 O(1)。at() 会检查越界，operator[] 不会。 |
data() |
返回指向底层连续内存中第一个元素的指针，复杂度是 O(1)。 |
begin()、end() |
分别返回指向第一个元素和末尾后一位置的迭代器，复杂度是 O(1)。 |
修改与交换
| 方法 | 作用与复杂度 |
|---|---|
fill(value) |
把数组中的所有元素都改成 value，复杂度是 O(N)。 |
swap(other) |
逐个交换当前数组和另一个同类型数组的元素，复杂度是 O(N)。 |
array 不提供 push_back()、pop_back()、resize()，因为数组长度是类型的一部分，创建后根本不能修改。
示例
统计小写字母出现次数：
#include <array>
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "banana";
array<int, 26> counts{};
for (char ch : text) {
++counts[ch - 'a'];
}
cout << "a 出现了 " << counts['a' - 'a'] << " 次\n";
cout << "b 出现了 " << counts['b' - 'a'] << " 次\n";
cout << "n 出现了 " << counts['n' - 'a'] << " 次\n";
}
这个场景里，字符种类固定就是 26 个，用 array<int, 26> 会比 vector<int>(26) 更能体现“长度不会变”。
vector
介绍与使用场景
vector 是动态数组，我觉得它应该是用得最多的 STL 容器之一。
它的元素放在连续内存里，支持下标访问，也能在运行时动态扩容。
终于不用纠结怎么实现动态数组了！你说是吧，C 语言？
- 业务开发里，一般适合保存数量会变、又经常需要遍历或随机访问的数据。因为连续内存对缓存友好，所以很多时候性能表现也不错。
- 算法题里，几乎到处都能见到它。输入数组、邻接表、动态规划状态、离散化后的结果，很多都用
vector。 - 它不适合频繁在头部或中间插入、删除元素，因为这往往需要整体搬移后面的元素。
初始化方式
#include <vector>
using namespace std;
// 定义一个空的动态数组
vector<int> nums;
// 定义一个包含 5 个 int 元素的动态数组，元素均初始化为 0
vector<int> nums1(5);
// 定义一个包含 5 个 int 元素的动态数组，每个元素均为 10
vector<int> nums2(5, 10);
// 使用初始化列表定义动态数组，依次保存 1、2、3、4、5
vector<int> nums3{1, 2, 3, 4, 5};
// 复制 nums3 的全部元素，定义一个新的动态数组
vector<int> nums4(nums3);
// 使用 nums3 的前 3 个元素定义动态数组
vector<int> nums5(nums3.begin(), nums3.begin() + 3);
下面两种写法一定要分清：
// 定义一个包含 5 个 int 元素的动态数组，元素均初始化为 0
vector<int> a(5);
// 定义一个只包含元素 5 的动态数组
vector<int> b{5};
这里的 (5) 表示创建 5 个实际存在的元素，因此 a.size() 是 5。如果只是想提前预留能容纳 5 个元素的空间，而不创建元素，应该使用 reserve(5)。
常用方法
设当前元素数量为 n：
查看与访问
| 方法 | 作用与复杂度 |
|---|---|
size()、empty() |
分别获取当前元素数量、判断容器是否为空。复杂度都是 O(1)。 |
operator[]、at()、front()、back() |
分别通过下标访问元素、进行带越界检查的下标访问、访问第一个元素、访问最后一个元素。复杂度都是 O(1)。 |
添加与删除
| 方法 | 作用与复杂度 |
|---|---|
push_back()、emplace_back() |
在末尾添加一个元素；emplace_back() 会直接在容器末尾构造元素。连续使用时均摊 O(1)；单次扩容时最坏 O(n)。 |
pop_back() |
删除最后一个元素，不会返回被删除的元素。复杂度为 O(1)。 |
insert()、emplace() |
在指定位置插入元素；emplace() 会直接在指定位置构造元素。末尾追加可参考 push_back()；头部或中间插入通常最坏 O(n)。 |
erase() |
删除指定位置的元素，或者删除一段范围内的元素。删除中间或头部元素通常最坏 O(n)，因为后面的元素要前移。 |
clear() |
删除并销毁全部元素，使容器变为空。复杂度为 O(n)。 |
容量与大小
| 方法 | 作用与复杂度 |
|---|---|
reserve() |
提前预留至少能容纳指定数量元素的空间，但不会改变元素数量。如果触发重新分配，需要搬移已有元素，复杂度为 O(n)。 |
capacity() |
查看当前已经分配的空间最多能容纳多少个元素。复杂度为 O(1)。 |
resize() |
把元素数量调整为指定值；缩小时删除多余元素，增大时补充新元素。缩小要销毁元素，增大要补新元素，还可能触发重分配；最坏可按 O(n + k) 理解，k 是新增元素数。 |
示例
保存一组成绩并求总分：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> scores{80, 92, 75};
scores.push_back(88);
scores.push_back(95);
int total = 0;
for (int score : scores) {
total += score;
}
cout << "人数：" << scores.size() << '\n';
cout << "总分：" << total << '\n';
}
如果已知大概要塞很多元素，先 reserve() 往往更舒服：
vector<int> nums;
nums.reserve(1000);
for (int i = 0; i < 1000; ++i) {
nums.push_back(i);
}
反过来，如果一直从头删元素，vector 就不太合适：
while (!nums.empty()) {
nums.erase(nums.begin());
}
这种写法每次都可能移动大量元素，需要频繁操作两端时通常更适合 deque。
deque
介绍与使用场景
deque 是双端队列，可以在头部和尾部都高效地插入、删除，同时也支持下标访问。
- 业务开发里，一般适合两端都可能进出数据的场景，比如任务缓冲、消息缓冲、窗口数据维护。
- 算法题里，很常见于 BFS、单调队列、滑动窗口最大值、0-1 BFS 这类题。
- 它和
vector最大的区别之一，就是头部操作更自然；但它通常不是一整段连续内存，所以缓存局部性一般不如vector。
初始化方式
#include <deque>
using namespace std;
// 定义一个空的双端队列
deque<int> nums;
// 定义一个包含 5 个 int 元素的双端队列，元素均初始化为 0
deque<int> nums1(5);
// 定义一个包含 5 个 int 元素的双端队列，每个元素均为 10
deque<int> nums2(5, 10);
// 使用初始化列表定义双端队列，依次保存 1、2、3、4、5
deque<int> nums3{1, 2, 3, 4, 5};
// 复制 nums3 的全部元素，定义一个新的双端队列
deque<int> nums4(nums3);
// 使用 nums3 的前 3 个元素定义双端队列
deque<int> nums5(nums3.begin(), nums3.begin() + 3);
常用方法
设当前元素数量为 n：
查看与访问
| 方法 | 作用与复杂度 |
|---|---|
size()、empty() |
分别获取当前元素数量、判断容器是否为空。复杂度都是 O(1)。 |
operator[]、at()、front()、back() |
分别通过下标访问元素、进行带越界检查的下标访问、访问第一个元素、访问最后一个元素。复杂度都是 O(1)。 |
两端操作
| 方法 | 作用与复杂度 |
|---|---|
push_front()、emplace_front()、push_back()、emplace_back() |
分别在头部或尾部添加元素；emplace_front() 和 emplace_back() 会直接在对应位置构造元素。复杂度都是 O(1)。 |
pop_front()、pop_back() |
分别删除第一个或最后一个元素，都不会返回被删除的元素。复杂度都是 O(1)。 |
中间操作与清空
| 方法 | 作用与复杂度 |
|---|---|
insert()、emplace() |
在指定位置插入元素；emplace() 会直接在指定位置构造元素。中间插入通常最坏 O(n)。 |
erase() |
删除指定位置的元素，或者删除一段范围内的元素。中间删除通常最坏 O(n)；删两端元素时更建议直接用 pop_front() 或 pop_back()。 |
clear() |
删除并销毁全部元素，使容器变为空。复杂度为 O(n)。 |
deque 不适合拿来当“一整块连续数组”使用，因为它不保证所有元素排在同一段连续内存里。
示例
模拟一个两端都可能来人的队伍：
#include <deque>
#include <iostream>
#include <string>
using namespace std;
int main() {
deque<string> passengers;
passengers.push_back("小明");
passengers.push_back("小红");
passengers.push_front("工作人员");
cout << "队首：" << passengers.front() << '\n';
cout << "队尾：" << passengers.back() << '\n';
passengers.pop_front();
cout << "工作人员离开后，队首是：" << passengers.front() << '\n';
}
在 BFS 这类场景里，pop_front() 的优势也很明显：
deque<int> nodes;
nodes.push_back(0);
while (!nodes.empty()) {
int current = nodes.front();
nodes.pop_front();
// 处理 current，并把下一批节点塞到队尾
}
如果你只是想从头删元素，又顺手用了 vector::erase(begin())，那大概率就是该换 deque 了。
queue
介绍与使用场景
queue 是队列容器适配器，遵循先进先出，也就是 FIFO。
- 业务开发里，一般用它保存等待处理的任务、消息或请求，让它们按进入顺序依次处理。
- 算法题里，一般用它做 BFS、层序遍历、模拟排队过程。
- 它默认底层通常是
deque，但平时更关心的是它暴露出来的队列接口，而不是底层细节。
初始化方式
#include <deque>
#include <list>
#include <queue>
// 定义一个空队列，使用默认的 deque 作为底层容器
std::queue<int> q1;
// 定义一个空队列，指定使用 list 作为底层容器
std::queue<int, std::list<int>> q2;
// 定义一个 deque，依次保存 10、20、30
std::deque<int> data{10, 20, 30};
// 复制 data 中的元素定义队列，队首为 10，队尾为 30
std::queue<int> q3(data);
它不能直接像顺序容器那样写成初始化列表形式。
常用方法
以下复杂度按默认底层容器 deque 来理解：
入队与出队
| 方法 | 作用与复杂度 |
|---|---|
push(value) |
把一个元素加入队尾。复杂度为 O(1)。 |
emplace(args...) |
使用传入的参数直接在队尾构造一个元素。复杂度为 O(1)。 |
pop() |
删除队首元素，但不会返回被删除的元素，通常先用 front() 取得队首内容，再调用 pop()。复杂度为 O(1)。 |
查看队列
| 方法 | 作用与复杂度 |
|---|---|
front() |
访问队首元素，也就是下一个将被移除的元素。复杂度为 O(1)。 |
back() |
访问队尾元素，也就是最后加入的元素。复杂度为 O(1)。 |
empty()、size() |
分别判断队列是否为空、获取当前元素数量。复杂度都是 O(1)。 |
如果你改了底层容器，复杂度要跟着底层容器的对应操作一起看。
示例
按进入顺序处理任务：
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> tasks;
tasks.push("读取配置");
tasks.push("连接服务器");
tasks.push("加载数据");
while (!tasks.empty()) {
cout << "正在处理：" << tasks.front() << '\n';
tasks.pop();
}
}
queue 的优势是语义非常直接，但限制也明显：它不能随机访问中间元素。要是你还想按下标看内容，那就该考虑 deque 或 vector。
stack
介绍与使用场景
stack 是栈容器适配器，遵循后进先出，也就是 LIFO。
- 业务开发里，一般用来保存撤销记录、页面返回路径、表达式解析过程、需要倒着处理的临时状态。
- 算法题里，常见于括号匹配、单调栈、模拟递归、深度优先搜索。
- 它默认底层通常也是
deque，但使用时一般只通过push、pop、top这些栈接口来操作。
初始化方式
#include <deque>
#include <stack>
#include <vector>
// 定义一个空栈，使用默认的 deque 作为底层容器
std::stack<int> s1;
// 定义一个空栈，指定使用 vector 作为底层容器
std::stack<int, std::vector<int>> s2;
// 定义一个 deque，依次保存 1、2、3
std::deque<int> data{1, 2, 3};
// 复制 data 中的元素定义栈，此时栈顶元素是 3
std::stack<int> s3(data);
和 queue 一样，它也不支持直接写初始化列表。
常用方法
以下复杂度按默认底层容器 deque 来理解：
入栈与出栈
| 方法 | 作用与复杂度 |
|---|---|
push(value) |
把一个元素压入栈顶。复杂度为 O(1)。 |
emplace(args...) |
使用传入的参数直接在栈顶构造一个元素。复杂度为 O(1)。 |
pop() |
删除栈顶元素，但不会返回被删除的元素，通常先用 top() 取得栈顶内容，再调用 pop()。复杂度为 O(1)。 |
查看栈
| 方法 | 作用与复杂度 |
|---|---|
top() |
访问栈顶元素，也就是最后压入的元素。复杂度为 O(1)。 |
empty()、size() |
分别判断栈是否为空、获取当前元素数量。复杂度都是 O(1)。 |
如果换了底层容器，复杂度还是要跟着底层容器走。
示例
用栈判断括号是否匹配：
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isValid(const string& str) {
stack<char> brackets;
for (char ch : str) {
if (ch == '(' || ch == '[' || ch == '{') {
brackets.push(ch);
continue;
}
if (ch != ')' && ch != ']' && ch != '}') {
continue;
}
if (brackets.empty()) {
return false;
}
char left = brackets.top();
brackets.pop();
if ((ch == ')' && left != '(') ||
(ch == ']' && left != '[') ||
(ch == '}' && left != '{')) {
return false;
}
}
return brackets.empty();
}
int main() {
cout << boolalpha;
cout << isValid("{[()]}") << '\n';
cout << isValid("{[(])}") << '\n';
}
这里最关键的地方就是：遇到右括号时，要优先处理最近那个还没配对的左括号，这正好就是栈擅长的顺序。
map
介绍与使用场景
map 用来保存键值对，键不能重复，并且会自动按键排序。它通常可以理解成一棵平衡搜索树。
- 业务开发里，一般用它做“键到值”的映射，而且还希望最终遍历时是有序的，比如按编号输出数据。
- 算法题里，常用来统计频率、记录状态、维护动态有序映射，或者查找某个键附近的位置。
- 如果你完全不关心顺序，只关心查找快不快，那通常还得再和
unordered_map比一比。
初始化方式
#include <map>
#include <string>
#include <utility>
#include <vector>
// 定义一个键为 string、值为 int 的空映射
std::map<std::string, int> m1;
// 使用初始化列表创建映射，包含 apple 和 banana 两组键值对
std::map<std::string, int> m2{
{"apple", 3},
{"banana", 5}
};
// 定义一个保存键值对的 vector
std::vector<std::pair<std::string, int>> items{
{"pen", 2},
{"book", 4}
};
// 使用 items 的全部元素创建映射
std::map<std::string, int> m3(items.begin(), items.end());
也可以指定比较规则：
#include <functional>
#include <map>
// 使用 greater<int> 让键按从大到小排列
std::map<int, int, std::greater<int>> m{
{1, 10},
{3, 30},
{2, 20}
};
常用方法
设容器里有 n 组键值对：
插入与更新
| 方法 | 作用与复杂度 |
|---|---|
insert({key, value})、emplace(key, value) |
插入一组键值对；如果键已经存在，则不会覆盖原来的值。复杂度为 O(log n)。 |
insert_or_assign(key, value) |
键不存在时插入，键已经存在时覆盖对应的值。复杂度为 O(log n)，需要 C++17。 |
查询与访问
| 方法 | 作用与复杂度 |
|---|---|
find(key)、count(key)、contains(key) |
按键查询；find() 返回迭代器，count() 返回该键的数量（这里只会是 0 或 1），contains() 直接返回是否存在。复杂度都是 O(log n)，contains() 需要 C++20。 |
at(key) |
按键访问对应的值，不会插入新元素。复杂度为 O(log n)；键不存在会抛异常。 |
operator[](key) |
访问或修改指定键对应的值。复杂度为 O(log n)；键不存在时会插入该键，并为它创建一个默认值。 |
lower_bound(key)、upper_bound(key) |
在默认升序规则下，lower_bound() 查找第一个键不小于 key 的元素，upper_bound() 查找第一个键大于 key 的元素。复杂度都是 O(log n)。 |
删除与状态
| 方法 | 作用与复杂度 |
|---|---|
erase(key) |
删除指定键及其对应的值。复杂度为 O(log n)。 |
erase(iterator) |
删除迭代器指向的单个节点。均摊复杂度为 O(1)。 |
size()、empty() |
分别获取键值对数量、判断容器是否为空。复杂度都是 O(1)。 |
clear() |
删除全部键值对，使容器变为空。复杂度为 O(n)。 |
map 里负责排序的是键，所以键本身不能直接改；值是可以改的。
示例
统计单词出现次数：
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
int main() {
vector<string> words{
"apple", "banana", "apple", "orange", "banana", "apple"
};
map<string, int> counts;
for (const string& word : words) {
++counts[word];
}
for (const auto& [word, count] : counts) {
cout << word << ": " << count << '\n';
}
}
这个写法很顺手，但也要记得：operator[] 会在键不存在时自动插入。如果你只是想查一下有没有，不想顺手把键塞进去，更适合用 find()、contains() 或 at()。
set
介绍与使用场景
set 用来保存不重复元素，并且会自动排序。可以把它看成“只有键、没有值的有序集合”。
- 业务开发里，一般适合需要去重、又希望最终结果保持有序的数据。
- 算法题里，常用来维护动态有序集合。除了判重，还能顺手做
lower_bound()、upper_bound()这类“找附近元素”的操作。 - 如果你只需要去重和快速查询，不需要有序性，那也常常会拿它和
unordered_set做选择。
初始化方式
#include <set>
#include <vector>
// 定义一个保存 int 的空集合
std::set<int> s1;
// 使用初始化列表创建集合，重复的 2 只会保留一个，元素按从小到大排列
std::set<int> s2{3, 1, 2, 2};
// 定义一个包含重复元素的 vector
std::vector<int> nums{4, 2, 5, 2};
// 使用 nums 的全部元素创建集合，重复元素会被去掉
std::set<int> s3(nums.begin(), nums.end());
指定降序比较：
#include <functional>
#include <set>
// 使用 greater<int> 创建按从大到小排列的集合
std::set<int, std::greater<int>> s{1, 3, 2};
常用方法
设集合里有 n 个元素：
插入与查询
| 方法 | 作用与复杂度 |
|---|---|
insert(value)、emplace(args...) |
插入一个元素；如果相同元素已经存在，则不会重复插入。复杂度为 O(log n)。 |
find(value)、count(value)、contains(value) |
查询元素；find() 返回迭代器，count() 返回元素数量（这里只会是 0 或 1），contains() 直接返回是否存在。复杂度都是 O(log n)，contains() 需要 C++20。 |
删除与清空
| 方法 | 作用与复杂度 |
|---|---|
erase(value) |
删除指定元素。复杂度为 O(log n)。 |
erase(iterator) |
删除迭代器指向的单个节点。均摊复杂度为 O(1)。 |
clear() |
删除全部元素，使集合变为空。复杂度为 O(n)。 |
顺序与状态
| 方法 | 作用与复杂度 |
|---|---|
lower_bound(value)、upper_bound(value) |
在默认升序规则下，lower_bound() 查找第一个不小于 value 的元素，upper_bound() 查找第一个大于 value 的元素。复杂度都是 O(log n)。 |
begin()、end() |
分别返回指向第一个元素和末尾后一位置的迭代器。取迭代器本身是 O(1)，从 begin() 开始遍历时元素天然有序。 |
size()、empty() |
分别获取元素数量、判断集合是否为空。复杂度都是 O(1)。 |
需要注意，set 里的元素本身就是排序关键字，所以不能直接改值。真要改，只能删了再插。
示例
先去重，再按从小到大输出：
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
vector<int> nums{4, 2, 4, 1, 3, 2};
set<int> uniqueNums(nums.begin(), nums.end());
for (int num : uniqueNums) {
cout << num << ' ';
}
}
查找第一个不小于目标值的元素：
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> scores{60, 70, 85, 90};
auto it = scores.lower_bound(80);
if (it != scores.end()) {
cout << *it << '\n';
}
}
unordered_map
介绍与使用场景
unordered_map 用哈希表保存键值对，不按键排序，遍历顺序也不该依赖。
- 业务开发里，一般适合通过某个键高频查值，比如通过用户 ID 找用户信息、通过配置名找配置内容。
- 算法题里，更是常客。频率统计、记录下标、缓存结果、做哈希判定，很多题第一反应就是它。
- 它平均复杂度很好，但不是稳定的最坏复杂度保证；要是你还需要有序遍历或者范围查询，就该回去考虑
map。
初始化方式
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
// 定义一个空的 unordered_map，键为 string，值为 int
std::unordered_map<std::string, int> m1;
// 使用初始化列表定义 unordered_map，初始包含 apple 和 banana 两组键值对
std::unordered_map<std::string, int> m2{
{"apple", 3},
{"banana", 5}
};
// 定义一个 vector，保存两组由 string 和 int 组成的键值对
std::vector<std::pair<std::string, int>> items{
{"pen", 2},
{"book", 4}
};
// 使用 [items.begin(), items.end()) 范围内的键值对构造 unordered_map
std::unordered_map<std::string, int> m3(items.begin(), items.end());
如果键是自定义类型，还得自己提供相等比较和哈希函数。
常用方法
设容器里有 n 组键值对：
插入与更新
| 方法 | 作用与复杂度 |
|---|---|
insert({key, value})、emplace(key, value) |
插入一组键值对；如果键已经存在，不会覆盖原来的值。平均 O(1)，最坏 O(n)。 |
insert_or_assign(key, value) |
键不存在时插入，键已经存在时覆盖对应的值。平均 O(1)，最坏 O(n)，需要 C++17。 |
查询与访问
| 方法 | 作用与复杂度 |
|---|---|
find(key)、count(key)、contains(key) |
按键查询；find() 返回迭代器，count() 返回该键的数量（这里只会是 0 或 1），contains() 直接返回是否存在。平均 O(1)，最坏 O(n)。contains() 需要 C++20。 |
at(key) |
访问指定键对应的值，不会插入新元素。平均 O(1)，最坏 O(n)；键不存在会抛异常。 |
operator[](key) |
访问或修改指定键对应的值。平均 O(1)，最坏 O(n)；键不存在会插入该键，并为它创建一个默认值。 |
删除与清空
| 方法 | 作用与复杂度 |
|---|---|
erase(key) |
按键删除对应的键值对。平均 O(1)，最坏 O(n)。 |
erase(iterator) |
删除迭代器指向的键值对。平均 O(1)，最坏 O(n)。 |
clear() |
删除全部键值对，使容器变为空。复杂度为 O(n)。 |
桶与状态
| 方法 | 作用与复杂度 |
|---|---|
reserve(count) |
调整桶的数量，使容器能在当前最大负载因子下容纳至少 count 个元素，常用来减少后续插入时的重哈希次数。如果触发重哈希，平均复杂度可按 O(n) 理解，最坏可能到 O(n^2)。 |
load_factor() |
返回当前负载因子，也就是平均每个桶中有多少个元素。复杂度为 O(1)。 |
size()、empty() |
分别获取键值对数量、判断容器是否为空。复杂度都是 O(1)。 |
哈希容器最要命的一点就是：平均很快，但别把“平均 O(1)”误记成“永远 O(1)”。
示例
经典的“两数之和”：
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
vector<int> nums{2, 7, 11, 15};
int target = 9;
unordered_map<int, int> positions;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
int needed = target - nums[i];
auto it = positions.find(needed);
if (it != positions.end()) {
cout << "下标：" << it->second << " 和 " << i << '\n';
break;
}
positions[nums[i]] = i;
}
}
这个例子不需要有序性，只需要快速查有没有，因此 unordered_map 就很顺手。
unordered_set
介绍与使用场景
unordered_set 是哈希版的集合，用来保存不重复元素，但不保证有序。
- 业务开发里，一般适合保存“只需要去重和判断是否存在”的数据，比如已处理请求 ID、黑名单用户、访问过的资源。
- 算法题里，经常用它做快速判重、访问标记、哈希去重。
- 如果你后面还得按顺序遍历，或者做区间/邻近查找，那通常还是
set更合适。
初始化方式
#include <unordered_set>
#include <vector>
// 定义一个空的 unordered_set
std::unordered_set<int> s1;
// 使用初始化列表定义 unordered_set，重复的 2 只会保留一个
std::unordered_set<int> s2{3, 1, 2, 2};
// 定义一个包含重复元素的 vector
std::vector<int> nums{4, 2, 5, 2};
// 使用 [nums.begin(), nums.end()) 范围内的元素构造 unordered_set，重复元素会被去除
std::unordered_set<int> s3(nums.begin(), nums.end());
自定义类型做键时，也一样需要自己准备比较和哈希逻辑。
常用方法
设集合里有 n 个元素：
插入与查询
| 方法 | 作用与复杂度 |
|---|---|
insert(value)、emplace(args...) |
插入一个元素；如果相同元素已经存在，不会重复插入。平均 O(1)，最坏 O(n)。 |
find(value)、count(value)、contains(value) |
查询元素；find() 返回迭代器，count() 返回元素数量（这里只会是 0 或 1），contains() 直接返回是否存在。平均 O(1)，最坏 O(n)。contains() 需要 C++20。 |
删除与清空
| 方法 | 作用与复杂度 |
|---|---|
erase(value) |
删除指定值的元素。平均 O(1)，最坏 O(n)。 |
erase(iterator) |
删除迭代器指向的元素。平均 O(1)，最坏 O(n)。 |
clear() |
删除全部元素，使集合变为空。复杂度为 O(n)。 |
桶与状态
| 方法 | 作用与复杂度 |
|---|---|
reserve(count) |
调整桶的数量，使集合能在当前最大负载因子下容纳至少 count 个元素，常用来减少后续插入时的重哈希次数。如果触发重哈希，平均复杂度可按 O(n) 理解，最坏可能到 O(n^2)。 |
load_factor() |
返回当前负载因子，也就是平均每个桶中有多少个元素。复杂度为 O(1)。 |
size()、empty() |
分别获取元素数量、判断集合是否为空。复杂度都是 O(1)。 |
和 unordered_map 一样，它的“快”也是平均意义上的快，不是最坏情况保证。
示例
判断数组里有没有重复元素：
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
vector<int> nums{1, 4, 2, 3, 4};
unordered_set<int> seen;
for (int num : nums) {
if (seen.find(num) != seen.end()) {
cout << "发现重复元素：" << num << '\n';
break;
}
seen.insert(num);
}
}
这个问题只关心“有没有出现过”，完全不关心顺序，所以 unordered_set 很合适。
tuple
介绍与使用场景
tuple 可以把多个不同类型的值打包在一起。你可以把它理解成 pair 的“多元素版本”。
- 业务开发里，一般用它让函数一次返回多个结果，或者临时传递几项不同类型但彼此相关的数据。要是这些字段有长期业务含义，还是定义结构体更清楚。
- 算法题里，常用它组合状态、排序关键字、优先队列里的复合元素，比如“距离、点编号、父节点”这种东西。
- 它方便是方便，但一旦层数深、元素多，可读性会掉得很快。
初始化方式
#include <string>
#include <tuple>
using namespace std;
// 使用初始化列表定义 tuple，依次保存编号、姓名和分数
tuple<int, string, double> a{1, "Alice", 95.5};
// 使用 make_tuple 创建一个依次保存编号、姓名和分数的 tuple
tuple<int, string, double> b = make_tuple(2, "Bob", 88.0);
// 定义一个 int 变量，作为用户编号
int id = 3;
// 定义一个 string 变量，作为用户名
string name = "Carol";
// 创建一个保存 id 和 name 引用的 tuple，通过 c 修改元素会影响原变量
auto c = tie(id, name);
C++17 起，结构化绑定也很常用：
// 把 a 的三个元素分别复制到三个新变量中
auto [userId, userName, score] = a;
如果想直接引用原对象，可以写引用绑定：
// 让三个变量分别引用 a 中对应的元素，修改变量也会修改 a
auto& [refId, refName, refScore] = a;
常用方法
访问与构造
| 方法 | 作用与复杂度 |
|---|---|
get<I>(t) |
按照编译期下标 I 访问第 I 个元素，下标从 0 开始。通常按 O(1) 理解。 |
get<T>(t) |
按照类型 T 访问元素，前提是这个类型在 tuple 里只出现一次。通常按 O(1) 理解。 |
make_tuple(...) |
根据传入的值推导元素类型并创建 tuple。若把元素个数记作 k，结构层面的工作量可按 O(k) 理解，实际成本还要考虑各元素的构造。 |
tie(...) |
创建一个保存各变量引用的 tuple，常用来接收多个返回值或进行批量赋值。若把元素个数记作 k，工作量可按 O(k) 理解。 |
类型、比较与交换
| 方法 | 作用与复杂度 |
|---|---|
tuple_size<T>::value、tuple_element<I, T>::type |
分别在编译期取得 tuple 的元素数量、取得第 I 个元素的类型，不涉及运行时遍历。 |
| 比较运算 | 按字典序逐项比较两个 tuple。若把元素个数记作 k，最多比较 k 个成员；如果各成员比较本身都是 O(1)，整体可按 O(k) 理解，否则还要把成员自己的比较成本算进去。 |
swap |
逐项交换两个 tuple 中对应的元素。若把元素个数记作 k，最坏 O(k)，具体还看每个元素的交换成本。 |
示例
函数一次返回多个结果：
#include <iostream>
#include <string>
#include <tuple>
using namespace std;
tuple<int, string> findUser() {
return {1001, "Alice"};
}
int main() {
auto [id, name] = findUser();
cout << id << ' ' << name << '\n';
}
保存一个复合状态：
#include <iostream>
#include <tuple>
using namespace std;
int main() {
tuple<int, int, int> state{5, 2, 3};
auto [distance, row, column] = state;
cout << "距离：" << distance
<< "，位置：(" << row << ", " << column << ")\n";
}
list
介绍与使用场景
list 是双向链表。它最大的特点不是“快”，而是“已知位置时，插删节点很稳”，并且不会像 vector 那样因为搬移元素把整段数据挪来挪去。
- 业务开发里，一般适合需要长期保留迭代器、并且经常在已知位置插入或删除节点的场景。
- 算法题里，实际使用频率通常没有
vector、deque、queue那么高，但在需要链表语义、稳定迭代器、节点级操作时还是有价值。 - 如果你只是需要头尾增删并且还想随机访问，通常
deque更顺手；如果你只是普通顺序存储，通常vector还是首选。
初始化方式
#include <list>
using namespace std;
// 定义一个空的双向链表
list<int> nums;
// 定义一个包含 5 个 int 元素的双向链表，元素均初始化为 0
list<int> nums1(5);
// 定义一个包含 5 个 int 元素的双向链表，每个元素均为 10
list<int> nums2(5, 10);
// 使用初始化列表定义双向链表，元素依次为 1、2、3、4、5
list<int> nums3{1, 2, 3, 4, 5};
// 复制 nums3，构造一个内容相同的双向链表
list<int> nums4(nums3);
// 使用 [nums3.begin(), nums3.end()) 范围内的元素构造双向链表
list<int> nums5(nums3.begin(), nums3.end());
常用方法
设当前元素数量为 n：
查看与访问
| 方法 | 作用与复杂度 |
|---|---|
size()、empty() |
分别获取元素数量、判断链表是否为空。复杂度都是 O(1)。 |
front()、back() |
分别访问第一个元素和最后一个元素。复杂度都是 O(1)。 |
查找某个值、走到第 i 个位置 |
list 不支持随机访问，需要使用迭代器沿链表逐个查找或移动，最坏 O(n)。 |
两端操作
| 方法 | 作用与复杂度 |
|---|---|
push_front()、emplace_front()、push_back()、emplace_back() |
分别在链表头部或尾部添加元素；emplace 系列会直接在节点中构造元素。复杂度都是 O(1)。 |
pop_front()、pop_back() |
分别删除第一个元素和最后一个元素，都不会返回被删除的元素。复杂度都是 O(1)。 |
指定位置操作
| 方法 | 作用与复杂度 |
|---|---|
insert(pos, value)、emplace(pos, ...) |
在 pos 指向的位置之前插入元素；emplace() 会直接在节点中构造元素。如果已经有位置迭代器，插入单个元素是 O(1)。 |
erase(pos) |
删除 pos 指向的元素。如果已经有目标位置迭代器，删除单个元素是 O(1)。 |
链表专用操作
| 方法 | 作用与复杂度 |
|---|---|
remove(value) |
遍历链表，删除所有等于 value 的元素。复杂度为 O(n)。 |
reverse() |
原地反转链表中的元素顺序。复杂度为 O(n)。 |
sort() |
对链表中的元素排序，默认按升序排列。复杂度为 O(n log n)。 |
clear() |
删除链表中的全部元素，使容器变为空。复杂度为 O(n)。 |
这里最容易记错的一点就是：list 的插删是 O(1)，前提是你已经拿到了正确位置的迭代器。如果你还得先遍历半天找到那个位置，整体就不便宜了。
示例
已知位置时在中间插入：
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> nums{10, 20, 30};
auto pos = nums.begin();
++pos;
nums.insert(pos, 15);
for (int value : nums) {
cout << value << ' ';
}
}
输出会是：
10 15 20 30
但如果你每次都得先一路走过去找到位置：
auto pos = nums.begin();
for (int i = 0; i < 100; ++i) {
++pos;
}
那前面的查找本身就已经是 O(n) 了。所以大多数普通场景下，我反而会先考虑 vector 或 deque，而不是急着上 list。
总结
这一篇博客我记录了一下我刷 hot 100 中经常遇到的一些 STL 类。
我感觉其实最核心的不是把接口一个个硬背下来，而是先分清楚几个问题：
- 它的数据在内存里大概怎么放
- 它擅长的是随机访问、两端操作，还是按键查找
- 它的常见操作复杂度大概是什么水平
- 它为什么适合当前题目，而不是“也能用但不知道为什么要用”
如果只是给自己一个很粗的经验版结论，我目前会先这样记：
- 普通顺序存储，先想
vector - 固定长度，先想
array - 字符串处理，先想
string - 两端都要高效操作，先想
deque - 先进先出用
queue，后进先出用stack - 要有序映射/集合，看
map、set - 只想平均意义上的快速查找，看
unordered_map、unordered_set - 临时打包两个值用
pair，多个值用tuple list不少人刚学时觉得很厉害，但真正常规开发和算法题里，很多时候并不是第一选择
后续的话我大概会补充一下关于 priority_queue、multiset、multimap 之类的。
至于迭代器、算法库之类的我应该会单独再开一篇博客编写。那部分和这些容器放在一起看，感觉会更完整一些。