STL
- STL是C++标准库；
- 除了operator new和delete之外，所有库实体都定义在命名空间std或者嵌套在命名空间std内的命名空间中。
STL常用库
| 分类 | 头文件 | 说明 | 常见内容 |
|---|---|---|---|
| 通用多用途头文件 | <cstdlib> | 通用头文件 | size_t、abort、malloc、atoi 等 |
| 语言支持库 | <climits> | 整数类型限制 | INT_MIN,INT_MAX |
| 内存管理库 | <memory> | 内存管理工具 | 智能指针（shared_ptr）及相关操作函数 |
| 容器库 | <vector> <list> <set> <map> <unordered_map> <uorrdered_set> <stack> <forward_list> <queue> | 常用容器 | 见下方详细说明 |
| 算法库 | <algorithm> | 范围操作算法 | 见下方详细说明 |
| 字符串库 | <string> <cstring> | 字符串模板及字符串相关算法 | 见下方详细说明 |
| 迭代器库 | <iterator> | 遍历容器中的元素 | 允许以统一的方式访问容器中的元素，而不用关心容器的内部实现细节。STL 提供了多种类型的迭代器，包括随机访问迭代器、双向迭代器、前向迭代器和输入输出迭代器等 |
容器
- 容器是可以承载元素的器件；
vector
- 可变长度的连续数组。
- 连续存储、尾部高效，自动扩缩容；
- 使用场景：（1）动态增长和缩小的数组；（2）可以根据下标访问；（3）频繁在末尾添加/删除元素；
- 不适用场景：频繁在中间增删元素（每次都涉及元素移动）；
#include <iostream>
#include <vector>
int main() {
// vector常见方法
// 1. 创建vector
std::vector<int> v;
std::vector<int> v2(10, 1);
// 2. 添加元素
v.push_back(1);
v.emplace_back(2);
// 获取大小
std::cout << v.size() << std::endl;
// 获取容量
std::cout << v.capacity() << std::endl;
// 3. 下标访问元素
std::cout << v[0] << std::endl;
// 通过迭代器访问第一个元素
std::cout << *v.begin() << std::endl;
// 迭代器遍历
for (auto it = v.begin(); it != v.end(); it++) {
std::cout << *it << std::endl;
}
// 访问最后一个元素
std::cout << v.back() << std::endl;
// 4. 删除末尾元素
v.pop_back();
// 删除指定位置元素
v.erase(v.begin() + 1);
// 删除指定范围元素
v.erase(v.begin() + 1, v.end() - 1);
// 删除指定值元素
v.erase(std::remove(v.begin(), v.end(), 1), v.end());
// 5. 获取元素个数
std::cout << v.size() << std::endl;
// 6. 清空vector
v.clear();
std::cout << v.size() << std::endl;
// 交换两个vector
v.swap(v2);
return 0;
}
| 功能分类 | 方法名称 | 功能说明 | 时间复杂度 |
|---|---|---|---|
| 容量与大小 | size() | 返回容器中元素的个数 | O(1) |
capacity() | 返回容器在不扩容的情况下总共能容纳的元素量 | O(1) | |
empty() | 如果容器为空返回 true | O(1) | |
reserve(n) | 预留空间。提前申请内存，避免多次搬家（扩容） | O(n) | |
resize(n) | 改变容器有效大小。可能会创建新元素或销毁旧元素 | O(n) | |
| 访问元素 | operator[] | 下标访问（如 v[0]）。速度最快，但不检查越界 | O(1) |
at(pos) | 强力访问。如果越界会抛出异常，更安全 | O(1) | |
front() | 返回第一个元素的引用 | O(1) | |
back() | 返回最后一个元素的引用 | O(1) | |
| 修改容器 | push_back(val) | 在容器末尾添加一个元素 | 均摊 O(1) |
emplace_back(args) | 原地构造。比 push_back 更高效（直接在末尾内存构造对象，不需要多进行一次临时对象拷贝或移动） | 均摊 O(1) | |
pop_back() | 删除末尾的元素 | O(1) | |
insert(pos, val) | 在迭代器指定位置插入元素 | O(n) | |
erase(pos) | 删除迭代器指向的一个或一段元素 | O(n) | |
clear() | 清空所有元素，但通常不会减小 capacity | O(n) | |
| 迭代器 | begin() / end() | 返回指向第一个元素 / 最后一个元素之后的迭代器 | O(1) |
reservevsresize：- -如果知道要存 100 个数，先
reserve(100)。这样vector就不会在增加元素时频繁地“申请内存 $\rightarrow$ 拷贝旧数据 $\rightarrow$ 释放旧内存”，性能提升显著。 resize则是真的改变了size()，你会发现里面多了很多默认初始化的元素。
- -如果知道要存 100 个数，先
- 迭代器失效：
- 失效场景：引发扩容、 元素挪动位置
- 失效原因：（1）扩容时需要开辟新的内存并把旧数据全部搬到新内存，此时所有旧的迭代器都会失效；（2）如果往中间insert元素，插入点之后的所有迭代器都会因为元素后移而失效；
// 引发扩容导致失效
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 如果触发扩容，it 瞬间变成野指针
std::cout << *it; // ❌ 这里的行为不可预测，可能直接崩溃
// 删除元素导致的失效
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it % 2 == 0) {
v.erase(it); // ❌ 后面元素前移，it 指向的内容变了，且下次循环 ++it 会跳过一个元素
}
}
| 操作 | 失效范围 | 根本原因 | 安全建议 |
|---|---|---|---|
push_back | 可能导致全部失效 | 内存重新分配（扩容） | 操作后不再使用旧迭代器，重新从begin位置开始遍历 |
insert | 插入点之后的迭代器失效 | 元素向后挪动 | 使用 it = v.insert(pos, val) 更新 |
erase | 删除点之后的迭代器失效 | 元素向前挪动 | 使用 it = v.erase(pos) 更新 |
reserve | 可能导致全部失效 | 内存重新分配 | 尽量在程序初始化阶段执行 |
resize | 可能导致全部失效 | 内存重新分配 | 修改大小后重新获取迭代器 |
- 总结：在使用vector的迭代器时，一旦进行了可能改变元素位置的操作，就默认迭代器已经过期；
queue
- （1）先进先出；（2）只能通过队头/队尾访问；
- queue是一个容器适配器，意思是它自己不负责维护内存，而是像一个壳子套在其它基础容器外；queue默认底层是用
std::deque实现的，但你也可以换成std::list； - 不支持迭代器；
- 常用方法：
| 功能分类 | 方法名称 | 说明 | 时间复杂度 |
|---|---|---|---|
| 基础信息 | empty() | 检查队列是否为空，返回 bool 值 | O(1) |
size() | 返回队列中当前元素的个数 | O(1) | |
| 元素访问 | front() | 核心方法：返回队头（最早进去的）元素 | O(1) |
back() | 返回队尾（最后进去的）元素 | O(1) | |
| 修改操作 | push(val) | 在队尾插入新元素 | O(1) |
emplace(args) | 在队尾原位构造元素，效率比 push 高 | O(1) | |
pop() | 核心方法：移除队头元素（注意：不返回它） | O(1) |
- 使用场景及注意事项
- 使用时要先判队列是否为空；
- BFS、层序遍历二叉树是queue最经典的使用场景；
- 任务调度时可以使用queue来按照接收顺序处理任务；
- 当消费不及时时可以使用queue来实现缓冲池；
priority_queue
- 优先队列
- priority_queue是一个容器适配器，底层默认是vector；
- 受限访问：只能访问到优先级最高的那个元素（堆顶），无法遍历整个队列；
- 不支持迭代器；
- 适合处理加权任务；
- 常用方法：
| 方法名称 | 功能说明 | 时间复杂度 |
|---|---|---|
push(val) | 将元素插入队列并重新排序 | O(log n) |
emplace(args) | 在队列中原位构造元素，效率更高 | O(log n) |
pop() | 删除优先级最高（堆顶）的元素 | O(log n) |
top() | 返回优先级最高（堆顶）元素的引用 | O(1) |
empty() | 检查队列是否为空 | O(1) |
size() | 返回队列中元素的个数 | O(1) |
- 大顶堆与小顶堆的定义方式
| 堆类型 | 声明方式 | 优先级规则 |
|---|---|---|
| 大顶堆（默认） | priority_queue<int> pq; | 数值越大，优先级越高 |
| 小顶堆 | 需要传入三个参数：数据类型、底层容器、比较函数。priority_queue<int, vector<int>, greater<int>> pq; | 数值越小，优先级越高 |
#include <iostream>
#include <queue>
#include <vector>
int main() {
// 定义一个小顶堆（数值越小越优先）
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
// 此时 10 是最小的，排在堆顶
std::cout << "当前队头元素: " << pq.top() << std::endl; // 输出 10
// 依次弹出，会发现输出是升序的
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// 输出: 10 20 30 50
return 0;
}
- 常用场景：任务调度、Dijkstra 算法；
- 自定义排序算法
auto cmp = [](int a,int b){return a>b;};// 小的优先
// 注意：这里需要 decltype(cmp) 来获取类型，并在构造函数中传入 cmp
std::priority_queue<int,std::vector<int>,decltype(cmp)> pq(cmp);
“左真右在后”原则：在 STL 的比较逻辑中，如果比较函数返回
true，意味着第一个参数的优先级较低，会被排在后面。这就是为什么实现“小顶堆”时要用>号的原因。
map
- 有序性：它内部会自动根据“键”的大小进行排序（默认是升序）。你遍历
map时，结果永远是有序的。 - 唯一性：每个键只出现一次，不能重复；
- 低层实现：红黑树，它的查找、插入、删除操作的时间复杂度都是稳定的 O(log n)。
- 常用方法：
| 功能分类 | 方法名称 | 说明 | 时间复杂度 |
|---|---|---|---|
| 基础信息 | size() | 返回键值对的数量 | O(1) |
empty() | 检查是否为空 | O(1) | |
| 修改操作 | insert({k, v}) | 插入一个键值对（如果键已存在则失败） | O(log n) |
operator[] | 核心：访问/修改。如果键不存在，会自动创建一个 | O(log n) | |
erase(key) | 根据键删除元素 | O(log n) | |
clear() | 清空所有元素 | O(n) | |
| 查找操作 | find(key) | 查找键，返回指向该元素的迭代器；若没找到返回 end() | O(log n) |
count(key) | 返回键出现的次数（对于 map 只有 0 或 1） | O(log n) | |
at(key) | 访问键对应的值，若不存在则抛出异常 | O(log n) | |
| 边界查找 | lower_bound(k) | 返回指向第一个大于或等于 k 的元素的迭代器 | O(log n) |
upper_bound(k) | 返回指向第一个大于 k 的元素的迭代器 | O(log n) |
- std:map vs std::unordered_map:
| 特性 | std::map | std::unordered_map |
|---|---|---|
| 底层实现 | 红黑树 (有序) | 哈希表 (无序) |
| 查找复杂度 | O(log n) | 平均 O(1)，最差 O(n) |
| 内存占用 | 较低 | 较高（需要维护哈希桶） |
| 适用场景 | 需要元素有序、需要范围查找 | 追求极致的查找速度、不需要排序 |
set
- 唯一性：集合中不允许出现重复元素；
- 有序性：所有集合中的元素按照大小排列（默认是升序）；
- 低层实现：红黑树；
- 使用场景：有序去重
- 常用方法：
| 功能分类 | 方法名称 | 说明 | 时间复杂度 |
|---|---|---|---|
| 基础信息 | size() | 返回集合中元素的个数 | O(1) |
empty() | 检查是否为空 | O(1) | |
| 修改操作 | insert(val) | 插入元素。若已存在则插入失败 | O(log n) |
erase(val/it) | 根据值或迭代器删除元素 | O(log n) | |
clear() | 清空集合 | O(n) | |
| 查找操作 | find(val) | 查找元素，返回迭代器。若没找到返回 end() | O(log n) |
count(val) | 返回元素出现次数（由于唯一性，结果只能是 0 或 1） | O(log n) | |
| 边界查找 | lower_bound(v) | 返回第一个 大于或等于 v 的元素的迭代器 | O(log n) |
upper_bound(v) | 返回第一个 大于 v 的元素的迭代器 | O(log n) |
unordered_map
- 无序
- 快速查找；
- 低层实现：哈希表；
- 唯一性：每个键只存在一次；
- 常用方法：
| 功能分类 | 方法名称 | 说明 | 时间复杂度 |
|---|---|---|---|
| 基础信息 | size() | 返回键值对的数量 | O(1) |
empty() | 检查是否为空 | O(1) | |
| 访问与修改 | operator[] | 访问/修改。如果键不存在，会自动创建一个；如果key已经存在则修改其值 | 平均 O(1) |
at(key) | 访问。如果键不存在，抛出 std::out_of_range | 平均 O(1) | |
insert({k, v}) | 插入键值对，返回键值对pair<iterator, bool>，当key已经存在时，拒绝插入，保留旧值 | 平均 O(1) | |
emplace(k, v) | 推荐：在容器中直接构造，性能更好；返回键值对pair<iterator, bool>，当key已经存在时，拒绝插入，保留旧值 | 平均 O(1) | |
| 查找与删除 | find(key) | 返回迭代器，若没找到返回 end() | 平均 O(1) |
count(key) | 返回键出现的次数（0 或 1） | 平均 O(1) | |
erase(key) | 根据键删除元素 | 平均 O(1) | |
| 哈希特有 | bucket_count() | 返回底层哈希桶的数量 | O(1) |
load_factor() | 返回负载因子（元素数/桶数），用于衡量哈希冲突概率 | O(1) | |
- 哈希冲突：两个不同的key经过哈希计算后指向了同一个下标；stl一般通过拉链法解决哈希冲突；
- 重哈希：当负载因子达到容器的最大拥挤限度时（一般是1），就会开始重哈希；
$$\text{Load Factor负载因子} (\alpha) = \frac{\text{Current Elements Count（元素数量）}}{\text{Current Buckets Count（桶数量）}}}$$
- 重哈希的步骤：（1）申请新内存：通常将桶的数量翻倍；（2）重新分配：遍历旧表里的每一个元素，根据新的桶数量重新计算哈希值。（3）搬迁：把元素放进新地址，并释放旧内存。
- unordered_map 的 Key 支持哪些类型：
- 要成为unordered_map的key要满足以下条件：（1）可哈希；（2）可比较；
- 支持的常见key：
| 类型分类 | 是否默认支持 | 备注 |
|---|---|---|
| 基础类型 | 支持 | 如 int, float, double, bool, char 等 |
| 指针类型 | 支持 | 原生指针（如 int*, void*）和智能指针均支持 |
| 标准库字符串 | 支持 | std::string, std::wstring 等 |
| 容器类型 | 不支持 | std::vector, std::pair, std::tuple 默认没有哈希实现 |
| 自定义结构体/类 | 不支持 | 需要手动提供 std::hash 特化和 operator== |
stack
- 先进后出；
- 受限访问：只能看top的元素；
- 底层实现：stack也是个容器适配器，其底层默认基于std::deque实现，但也可以指定为vector或list；
- 不支持迭代器；
- 常用方法：
| 功能分类 | 方法名称 | 说明 | 时间复杂度 |
|---|---|---|---|
| 基础信息 | empty() | 检查栈是否为空 | O(1) |
size() | 返回栈中元素的个数 | O(1) | |
| 访问元素 | top() | 核心：返回栈顶元素的引用（不删除） | O(1) |
| 修改容器 | push(val) | 在栈顶压入一个元素 | O(1) |
emplace(args) | 在栈顶原位构造元素，效率更高 | O(1) | |
pop() | 核心：移除栈顶元素（注意：不返回该元素） | O(1) |
容器总结
| 容器类型 | 容器名称 | 查找 (查找值) | 随机访问 (下标) | 插入/删除 (两端) | 插入/删除 (中间) | 底层结构 |
|---|---|---|---|---|---|---|
| 序列容器 | vector | O(n) | O(1) | 尾部 O(1) | O(n) | 动态连续数组 |
deque | O(n) | O(1) | 两端 O(1) | O(n) | 分段连续数组 | |
list | O(n) | O(n) | O(1) | O(1) | 双向链表 | |
| 关联容器 | map/set | O(log n) | 不支持 | O(log n) | O(log n) | 红黑树 |
unordered_map/set | O(1) | 不支持 | O(1) | O(1) | 哈希表 | |
| 容器适配器 | stack | 不支持 | 不支持 | O(1) (栈顶) | 不支持 | 默认 deque |
queue | 不支持 | 不支持 | O(1) (头尾) | 不支持 | 默认 deque | |
priority_queue | 不支持 | 不支持 | O(log n) | 不支持 | 二叉堆 |
算法
<algorithm>头文件
常用算法
| 分类 | 算法名称 | 返回类型 | 功能说明 | 支持的容器 | 时间复杂度 |
|---|---|---|---|---|---|
| 查找与计数 | std::find | Iterator | 查找第一个匹配元素 | 所有容器 | O(n) |
std::count | difference_type | 统计匹配值的个数 | 所有容器 | O(n) | |
std::any_of | bool | 是否有任一元素满足条件 | 所有容器 | O(n) | |
| 排序与搜索 | std::sort | void | 原地排序 | 仅限随机访问: vector, deque | O(n log n) |
std::lower_bound | Iterator | 返回第一个 $\ge$ 给定值的位置 | 有序序列: vector, deque, set*, map* | O(log n) | |
std::upper_bound | Iterator | 返回第一个 $>$ 给定值的位置 | 有序序列: vector, deque, set*, map* | O(log n) | |
std::binary_search | bool | 告知目标是否存在 | 有序序列: vector, deque, set, map | O(log n) | |
| 修改与转换 | std::copy | OutputIterator | 复制区间到目标位置 | 所有序列容器 | O(n) |
std::transform | OutputIterator | 对区间元素做变换 | 所有序列容器 | O(n) | |
std::replace | void | 原地替换元素值 | 所有序列容器 | O(n) | |
| 生成与删除 | std::fill | void | 用指定值填充区间 | 所有序列容器 | O(n) |
std::unique | Iterator | 返回去重后的逻辑末尾 | 序列容器 (通常先 sort) | O(n) | |
std::reverse | void | 原地反转区间 | 双向访问容器: vector, list, deque | O(n) |
sort
- sort底层使用内省排序，可以根据数据量和分布情况在快排、堆排和插入排序中切换；
- sort不是稳定排序（相同元素的相对位置不变），如果想要稳定排序可以使用
std::stable_sort，但效率会有所降低，stable_sort的底层是归并排序； - 排序算法选择标准：
- 1、快排：数据量较大时，主要选择快排，因为它平均速度较快；
- 2、堆排序：当快排的递归深度超过一定阈值（发现数据分布极不均匀，快排可能退化）时，它会果断切换到堆排，保证最坏情况下的复杂度依然是
O(n \log n); - 3、插入排序：当数据量缩减到很小（通常是 16 个元素以内）时，由于插入排序在小规模数据上具有极佳的缓存局部性，它会切换到插入排序来收尾；
- 自定义排序函数：
- 使用lamda函数；
#include <iostream>
#include <vector>
#include <algorithm>
struct Student {
std::string name;
int score;
};
int main() {
std::vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 95}};
// 需求：按分数从高到低排序 (降序)
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
return a.score > b.score; // 如果 a 的分更高，a 排在前面
});
for (const auto& s : students) std::cout << s.name << ":" << s.score << " ";
// 输出: Charlie:95 Alice:90 Bob:85
return 0;
}
常见排序算法
- 快速排序：选一个基准值，左边全比它小，右边全比它大；
// 核心分区函数
int partition(std::vector<int>& v, int low, int high) {
int pivot = v[high]; // 选最后一个作为基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (v[j] < pivot) {
i++;
std::swap(v[i], v[j]);
}
}
std::swap(v[i + 1], v[high]);
return i + 1;
}
void quickSort(std::vector<int>& v, int low, int high) {
if (low < high) {
int pi = partition(v, low, high);
quickSort(v, low, pi - 1); // 递归左半部分
quickSort(v, pi + 1, high); // 递归右半部分
}
}
- 归并排序：递归二分到最底层，再合并
void merge(std::vector<int>& v, int l, int m, int r) {
std::vector<int> L(v.begin() + l, v.begin() + m + 1);
std::vector<int> R(v.begin() + m + 1, v.begin() + r + 1);
int i = 0, j = 0, k = l;
while (i < L.size() && j < R.size()) {
v[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
}
while (i < L.size()) v[k++] = L[i++]; // 补齐剩余部分
while (j < R.size()) v[k++] = R[j++];
}
void mergeSort(std::vector<int>& v, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(v, l, m);
mergeSort(v, m + 1, r);
merge(v, l, m, r);
}
}