Appearance
STL
vector 底层是什么？
一句话理解：std::vector 底层是“连续动态数组”。它像一个可以自动扩容的数组：元素连续存放，支持快速下标访问；容量不够时，会重新申请更大的连续内存，把旧元素搬过去。
vector 对象本身通常很小
比如：
c
std::vector<int> v;v 这个对象本身通常只保存一些管理信息，常见实现类似：
begin：指向第一个元素
end：指向最后一个元素的下一个位置
end_capacity：指向容量末尾也可以理解成：
data 指针
size 当前元素数量
capacity 当前可容纳数量注意：具体内部布局是实现细节，不同编译器不一定完全一样。 但标准保证：vector 的元素是连续存储的。
元素通常在堆上连续存放
c
#include <vector>
using namespace std;
int main()
{
vector<int> nums;
nums.push_back(10);
nums.push_back(20);
nums.push_back(30);
return 0;
}逻辑上像这样：
c
nums 对象本身：
data ────────┐
size = 3 │
capacity = 6 │
↓
堆上连续数组：
[10][20][30][空][空][空]所以：
c
nums[0]
nums[1]
nums[2]访问很快。
为什么 vector 随机访问快
因为元素连续。
c
nums[i]底层大概就是：
c
data + i * sizeof(T)所以随机访问复杂度是：
c
O(1)这也是 vector 比链表更适合大量遍历和随机访问的原因。
size 和 capacity 区别
c
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.reserve(5);
v.push_back(10);
v.push_back(20);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
return 0;
}可能输出：
c
size = 2
capacity = 5意思是：
size：当前真的有几个元素。
capacity：当前这块内存最多能放几个元素。reserve(5) 只是提前申请容量，不会创建 5 个元素。
reserve 和 resize 区别
c
vector<int> v;
v.reserve(10);意思是：
容量至少变成 10。
size 还是 0。
没有真正创建 10 个 int 元素。
v.resize(10);意思是：
size 变成 10。
真的创建 10 个元素。面试里要说清楚：
reserve 改 capacity。
resize 改 size。vector 扩容过程
当：
c
size == capacity此时再 push_back，容量不够，就要扩容。
扩容通常做这些事：
1. 申请一块更大的连续内存
2. 把旧元素移动或拷贝到新内存
3. 析构旧内存里的元素
4. 释放旧内存
5. 更新 data、size、capacity示例：
c
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);如果容量不够，它可能从：
[1][2]搬到：
[1][2][3][空]原来的那块内存会失效。
扩容倍数是多少
常见实现可能是：
1.5 倍
2 倍但 C++ 标准不规定具体倍数。
所以面试不要说死：
vector 一定 2 倍扩容更稳的说法是：
vector 通常按某个增长因子扩容，例如 1.5 倍或 2 倍，具体取决于标准库实现。为什么 push_back 是均摊 O(1)
大多数 push_back：
容量够，直接放到末尾，O(1)偶尔一次扩容：
申请新内存，搬所有旧元素，O(n)但扩容不是每次都发生。 平均摊下来，push_back 是：
c
amortized O(1)也就是均摊常数时间。
中间插入和删除为什么慢
c
vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin() + 2, 99);插入后：
c
[1][2][99][3][4][5]为了保持连续存储，3、4、5 都要往后移动。
所以中间插入复杂度是：
c
O(n)删除也是：
c
v.erase(v.begin() + 2);后面的元素要往前补位，也是：
c
O(n)迭代器、指针、引用失效
这是 vector 高频坑。
c
vector<int> v;
v.push_back(1);
v.push_back(2);
int* p = &v[0];
// 如果这次 push_back 导致扩容
v.push_back(3);
// p 可能已经失效
// 因为旧内存已经被释放扩容后：
旧 data 指向的内存没了
新 data 指向另一块更大的内存所以这些都可能失效：
指针
引用
迭代器常见规则：
发生扩容：全部迭代器、引用、指针失效。
未扩容 push_back：end 迭代器失效，已有元素引用通常仍有效。
insert/erase：插入/删除位置及其后面的迭代器和引用可能失效。为什么 vector 缓存友好
因为连续内存适合 CPU cache。
遍历：
c
for (int x : v)
{
// 处理 x
}CPU 读到一个元素时，通常会顺便把后面的连续数据也加载进缓存。 所以 vector 遍历通常很快。
链表虽然插入删除节点方便，但节点分散在内存各处，缓存命中率差。 很多实际场景下，vector 比 list 更快。
vector 和普通数组区别
普通数组：
大小固定，不能自动扩容。
vector：
动态大小，容量不够会自动扩容。普通数组：
c
int arr[3] = {1, 2, 3};vector：
c
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);vector 更灵活，但扩容时有搬迁成本。
vector<T> 和 vector<bool> 的坑
vector<bool> 是特殊版本。
它不是普通意义上的：
一个 bool 占一个元素位置很多实现会把多个 bool 压缩到 bit 位里。
所以：
c
vector<bool> flags;它的行为和普通 vector<T> 有些不同，比如元素访问返回的可能不是普通 bool&，而是代理对象。
面试可以补一句：
vector<bool> 是特化版本，不完全像普通 vector<T>，工程里要小心。代码观察扩容
c
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
for (int i = 0; i < 10; i++)
{
v.push_back(i);
cout << "size = " << v.size()
<< ", capacity = " << v.capacity()
<< endl;
}
return 0;
}你会看到 capacity 不是每次都加 1，而是隔一段增长一次。 这就是为了避免每次 push_back 都重新分配内存。
实际开发建议
如果提前知道数量，用 reserve。
经常随机访问和遍历，用 vector 很合适。
经常在中间插入删除大量元素，vector 不一定合适。
不要长期保存 vector 元素指针后又继续 push_back。
需要传给 C API，可以用 v.data()。例子：
c
vector<int> v;
v.reserve(1000); // 提前申请，减少扩容次数
for (int i = 0; i < 1000; i++)
{
v.push_back(i);
}这样比不 reserve 更稳定。
面试高分回答
TIP
std::vector 底层是连续动态数组。vector 对象本身通常保存指向堆上连续内存的指针，以及 size、capacity 相关信息。常见实现可以理解为 begin、end、end_capacity 三个指针，但具体布局是标准库实现细节。
因为元素连续存储，所以 vector 支持 O(1) 随机访问，遍历时缓存友好，也可以通过 data() 拿到连续内存给 C API 使用。
当 size 达到 capacity 后继续插入，vector 会重新申请一块更大的连续内存，然后把旧元素移动或拷贝过去，再释放旧内存。扩容倍数标准不固定，常见是 1.5 倍或 2 倍。因此 push_back 平均是均摊 O(1)，但某次扩容可能是 O(n)。
缺点是中间插入和删除需要移动后续元素，所以是 O(n)。另外扩容会导致原来的迭代器、引用和指针失效，这是使用 vector 的高频坑。
最短记忆版
vector = 连续动态数组。
对象里存 data/size/capacity，元素在堆上连续内存。
随机访问 O(1)，尾插均摊 O(1)，中间插删 O(n)。
扩容会搬家，迭代器/指针/引用可能失效。vector 扩容后迭代器为什么会失效？
一句话理解：vector 扩容后迭代器会失效，是因为 vector 底层是连续数组。容量不够时，它会重新申请一块更大的连续内存，把旧元素搬过去，再释放旧内存。旧迭代器还指向旧地址，所以就失效了。
零基础理解
你可以把 vector 想成一排连续座位。
一开始有 3 个座位：
c
[10][20][30]你保存了一个迭代器：
c
auto it = v.begin();它指向第一个座位，也就是 10。
后来你继续 push_back，座位不够了。 vector 没法在原地变大，就会换一个更大的地方：
c
旧地方：[10][20][30]
新地方：[10][20][30][40][空][空]然后旧地方被释放。 但你的旧迭代器 it 还记着旧地方的地址。
所以再用它就危险了。
代码例子
c
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
// 保存一个迭代器，指向第一个元素
auto it = v.begin();
// 保存扩容前的容量
size_t oldCapacity = v.capacity();
// 不断 push，直到触发扩容
while (v.capacity() == oldCapacity)
{
v.push_back(100);
}
// 这里 it 很可能已经失效
// cout << *it << endl; // 危险：未定义行为
// 正确：扩容后重新获取迭代器
it = v.begin();
cout << *it << endl;
return 0;
}重点是这句：
c
cout << *it << endl;如果 it 已经失效，再解引用就是未定义行为。 可能崩溃，也可能看起来正常，但都是错的。
为什么旧迭代器不能自动更新
因为迭代器通常可以理解成“指向元素位置的对象”。 对 vector 来说，它很多实现里接近一个原始指针。
比如：
it → 旧数组第 0 个元素地址扩容后：
旧数组被释放
新数组地址变了旧的 it 不会自动知道 vector 搬家了。 它还拿着旧地址。
所以它就成了：
c
悬空迭代器 dangling iterator和悬空指针很像。
扩容时具体发生什么
当：
c
size == capacity继续插入元素时，可能触发扩容。
大概流程：
c
1. 申请一块更大的连续内存
2. 把旧元素移动或拷贝到新内存
3. 在新内存里构造新元素
4. 析构旧内存里的元素
5. 释放旧内存
6. 更新 vector 内部 data / begin / end / capacity也就是：
vector 自己知道新地址了
但你外面保存的旧迭代器不知道哪些东西会失效
扩容后，这些通常都会失效：
旧迭代器
旧指针
旧引用比如：
c
vector<int> v = {1, 2, 3};
int* p = &v[0];
int& r = v[1];
auto it = v.begin();
v.push_back(4); // 如果触发扩容
// p 可能失效
// r 可能失效
// it 可能失效原因一样： 它们都和旧内存地址有关。
没扩容时会不会失效
如果 push_back 没有触发扩容：
已有元素的引用、指针、迭代器通常仍然有效。但是：
end() 迭代器会失效。因为 end() 表示最后一个元素的下一个位置。 插入新元素后，end() 位置变了。
所以更稳的记法：
push_back 触发扩容：全部失效。
push_back 未触发扩容：end 失效，已有元素通常不失效。insert 和 erase 也会导致失效
vector 中间插入：
c
vector<int> v = {1, 2, 3, 4};
auto it = v.begin() + 1; // 指向 2
v.insert(v.begin(), 99);插入后，为了保持连续存储，元素要往后移动。 所以插入位置及其后面的迭代器、引用、指针都可能失效。
删除也是：
c
vector<int> v = {1, 2, 3, 4};
auto it = v.begin() + 2; // 指向 3
v.erase(v.begin());删除后，后面的元素往前移动，原来的位置含义变了。
怎么避免迭代器失效问题
1. 提前 reserve
如果你大概知道要放多少元素：
c
vector<int> v;
// 提前申请容量，减少扩容次数
v.reserve(1000);
for (int i = 0; i < 1000; i++)
{
v.push_back(i);
}这样中途就不容易反复扩容。
2. 修改 vector 后重新获取迭代器
c
auto it = v.begin();
v.push_back(10);
// 不要继续用旧 it
it = v.begin();3. 保存下标，不长期保存迭代器
有时保存下标更安全：
c
vector<int> v = {10, 20, 30};
size_t index = 1;
v.push_back(40);
// 扩容后重新用下标访问
cout << v[index] << endl;但也要注意： 如果你做了 insert/erase，下标对应的元素也可能变了。
4. 不要保存 vector 元素地址后继续 push_back
危险：
c
int* p = &v[0];
v.push_back(100);
// p 可能失效安全一点：
c
v.reserve(1000);
int* p = &v[0];
// 只要后续不超过 capacity，push_back 不触发扩容
// p 才比较稳定但工程里还是要谨慎长期保存 vector 元素地址。
面试高分回答
NOTE
vector 的底层是连续动态数组。迭代器通常可以理解为指向数组中某个元素的位置。
当 vector 的 size 达到 capacity 后继续插入元素时，它需要扩容。扩容时会重新申请一块更大的连续内存，然后把旧元素移动或拷贝到新内存，再释放旧内存。
因为元素的内存地址整体变了，原来指向旧内存的迭代器、指针和引用就变成了悬空引用，所以会失效。继续使用这些旧迭代器属于未定义行为。
如果 push_back 没有触发扩容，已有元素的迭代器和引用通常还有效，但 end 迭代器会失效。insert 和 erase 则会使插入或删除位置及其后面的迭代器、引用失效。
实际开发中可以通过 reserve 提前申请容量，或者在修改 vector 后重新获取迭代器，避免长期保存 vector 元素地址。
最短记忆版
vector 扩容 = 重新申请大数组 + 搬元素 + 释放旧数组。
旧迭代器还指向旧数组，所以失效。
解决：reserve、重新获取迭代器、少长期保存元素地址。list 和 vector 怎么选择？
一句话理解： 默认优先选 vector。只有你确实需要频繁在中间插入/删除，并且已经拿到了目标位置的迭代器，还需要迭代器稳定时，才考虑 list。
先看底层区别
vector 底层是连续动态数组：
c
[10][20][30][40][50]特点：
内存连续
随机访问快
遍历快
CPU 缓存友好
尾部插入快
中间插入删除要移动元素list 底层是双向链表：
c
[A] <-> [B] <-> [C]特点：
节点不连续
每个节点有 prev / next 指针
不支持下标随机访问
已知位置插入删除快
遍历缓存不友好
内存开销更大为什么默认选 vector
很多人背复杂度会说：
vector 中间插删 O(n)
list 中间插删 O(1)
所以插删多用 list这句话太粗了。
因为 list 的插入删除虽然是 O(1)，但前提是：
你已经拿到了要插入/删除的位置迭代器。如果你要先找位置：
c
auto it = find(lst.begin(), lst.end(), target);
lst.erase(it);查找本身还是 O(n)。
而且 list 节点分散在内存里，CPU 缓存命中差。 实际工程里，中小规模数据下，vector 经常比 list 更快。
vector 适合什么场景
适合：
需要下标访问
经常遍历
经常排序
经常查找
主要在尾部 push_back
元素数量中小规模
希望内存紧凑
性能敏感，重视 CPU cache例子：
c
#include <vector>
using namespace std;
struct Enemy
{
int hp;
int attack;
};
int main()
{
vector<Enemy> enemies;
enemies.reserve(1000);
enemies.push_back({100, 20});
enemies.push_back({150, 30});
// 随机访问很快
enemies[0].hp -= 10;
// 遍历也很快，因为内存连续
for (Enemy& enemy : enemies)
{
enemy.hp -= 1;
}
return 0;
}游戏开发里，很多对象列表、组件列表、渲染数据、任务数据都更适合 vector。
list 适合什么场景
适合：
频繁在中间插入删除
已经持有插入/删除位置的迭代器
不需要随机访问
需要插入删除后其他元素迭代器尽量稳定
需要 splice 把节点从一个 list 转移到另一个 list
元素对象很大，不想频繁搬动例子：
c
#include <list>
using namespace std;
int main()
{
list<int> nums = {1, 2, 3, 4};
auto it = nums.begin();
++it; // 指向 2
// 已经知道位置时，插入很快
nums.insert(it, 99);
// 删除当前节点也很快
nums.erase(it);
return 0;
}注意： list 快的是“已知位置后的插入删除”，不是“查找 + 插入删除”。
随机访问对比
vector：
c
vector<int> v = {10, 20, 30};
int x = v[2]; // O(1)list：
c
list<int> lst = {10, 20, 30};
// list 没有 lst[2]
// 只能从头走到目标位置
auto it = lst.begin();
advance(it, 2); // O(n)
int x = *it;所以如果你需要频繁通过下标访问，选 vector。
插入删除对比
vector 中间插入：
c
vector<int> v = {1, 2, 3, 4};
v.insert(v.begin() + 1, 99);结果：
c
[1][99][2][3][4]2、3、4 都要往后移动，所以是 O(n)。
list 中间插入：
c
list<int> lst = {1, 2, 3, 4};
auto it = lst.begin();
++it;
lst.insert(it, 99);只需要改几个指针：
c
前节点 next
新节点 prev/next
后节点 prev如果已经有 it，插入是 O(1)。
迭代器失效对比
vector：
扩容后，所有迭代器、指针、引用都可能失效。
insert/erase 后，位置及其后的迭代器可能失效。list：
插入不会让已有迭代器失效。
删除只会让被删除节点的迭代器失效。
其他节点迭代器仍然有效。所以如果你需要长期保存迭代器，并且频繁插删，list 有优势。
内存开销对比
vector<int> 每个元素就是一个 int，连续放：
c
int int int int intlist<int> 每个节点除了 int，还要保存指针：
c
prev 指针
next 指针
int 数据在 64 位系统里，一个指针通常 8 字节。 所以 list<int> 的节点开销可能远大于数据本身。
这也是为什么 list 不一定省。
缓存友好性
vector 连续：
CPU 读 v[0] 时，可能顺便把 v[1]、v[2]、v[3] 加载进缓存。list 分散：
读完一个节点，要跟着 next 指针跳到另一个内存位置。这会导致缓存不命中。 所以即使理论复杂度相同，vector 实际也可能更快。
选择建议
c
默认：vector
需要队头队尾操作：deque
需要有序查找：set / map
需要哈希查找：unordered_map / unordered_set
需要稳定迭代器 + 已知位置频繁插删：list大多数时候：
先用 vector。
性能不满足，再测量和替换。常见误区
1. 以为插删多就一定用 list。
2. 忘了 list 查找位置通常也是 O(n)。
3. 忽略 CPU cache，导致 list 理论好看但实际慢。
4. 用 list 存大量小对象，内存开销很大。
5. vector 扩容后继续用旧迭代器。
6. 不提前 reserve，导致 vector 频繁扩容。面试高分回答
WARNING
vector 和 list 的选择不能只看插入删除复杂度。
vector 底层是连续动态数组，随机访问 O(1)，遍历缓存友好，尾部 push_back 是均摊 O(1)，所以大多数场景默认优先使用 vector。缺点是中间插入删除需要移动元素，扩容会导致迭代器、指针、引用失效。
list 底层是双向链表，不支持随机访问，查找位置需要 O(n)，而且节点分散在内存中，缓存不友好，每个节点还有额外指针开销。它的优势是：在已经有目标迭代器的情况下，中间插入删除是 O(1)，并且插入删除对其他节点的迭代器影响小。
所以如果主要是随机访问、遍历、排序、尾插，我选 vector。如果确实需要频繁在中间插删，已经持有位置迭代器，并且需要迭代器稳定，我才考虑 list。工程里还要结合数据规模和实际性能测试。
最短记忆版
默认 vector：连续内存，随机访问快，遍历快，缓存友好。
慎用 list：已知位置插删快，但查找慢、缓存差、内存开销大。
选择看访问模式，不只看 Big-O。map 和 unordered_map 区别是什么？
一句话理解：map 是“自动排序的字典”，底层通常是红黑树；unordered_map 是“不排序但查找通常更快的字典”，底层是哈希表。
零基础理解： 它们都用来存“键值对”：
c
// key 是名字，value 是分数
Tom -> 90
Bob -> 80
Alice -> 95区别在于：
map 会按照 key 自动排序，比如字符串 key 会按字典序排列。 unordered_map 不保证顺序，它关心的是“怎么尽快根据 key 找到 value”。
底层区别：
map 底层通常是红黑树。 红黑树是一种自平衡二叉搜索树，所以数据天然有序，查找、插入、删除通常都是：
c
O(log n)unordered_map 底层是哈希表。 它会把 key 通过哈希函数算成一个数字，再映射到桶里：
c
hash(key) -> 桶下标 -> 找到 value平均情况下查找、插入、删除是：
c
O(1)但是如果哈希冲突很多，最坏可能退化到：
c
O(n)代码对比：
c
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
int main() {
map<string, int> orderedScores;
unordered_map<string, int> fastScores;
orderedScores["Tom"] = 90;
orderedScores["Bob"] = 80;
orderedScores["Alice"] = 95;
fastScores["Tom"] = 90;
fastScores["Bob"] = 80;
fastScores["Alice"] = 95;
cout << "map 遍历结果：" << endl;
for (auto& item : orderedScores) {
// map 会按照 key 自动排序
cout << item.first << " = " << item.second << endl;
}
cout << "unordered_map 遍历结果：" << endl;
for (auto& item : fastScores) {
// unordered_map 的遍历顺序不保证固定
cout << item.first << " = " << item.second << endl;
}
return 0;
}你可能看到：
c
map:
Alice = 95
Bob = 80
Tom = 90因为它按 key 排序。
但 unordered_map 可能是：
c
Tom = 90
Alice = 95
Bob = 80也可能下次顺序又不一样，因为它不负责排序。
什么时候用 map？
当你需要“有序”时，用 map：
c
map<int, string> students;
students[1003] = "Tom";
students[1001] = "Alice";
students[1002] = "Bob";
// 遍历时会自动按学号从小到大输出
for (auto& p : students) {
cout << p.first << " " << p.second << endl;
}适合场景：
key 必须有序。 需要范围查询，比如找 [10, 50] 之间的 key。 需要 lower_bound、upper_bound。 希望性能稳定，最坏也大致是 O(log n)。
什么时候用 unordered_map？
当你只关心“根据 key 快速查值”，不关心顺序时，用 unordered_map：
c
unordered_map<string, int> bag;
// 统计每种道具数量
bag["coin"]++;
bag["coin"]++;
bag["sword"]++;
cout << bag["coin"] << endl; // 2适合场景：
统计频率。 缓存数据。 根据 id 快速找对象。 游戏里根据角色 ID、配置 ID、资源名查数据。 不需要排序，只要快。
重要区别表：
| 对比点 | map | unordered_map |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 是否有序 | 有序 | 无序 |
| 查找复杂度 | O(log n) | 平均 O(1)，最坏 O(n) |
| 插入复杂度 | O(log n) | 平均 O(1) |
| 范围查询 | 支持 | 不适合 |
| 内存占用 | 节点有左右指针、颜色 | 桶数组 + 节点，通常也不低 |
| key 要求 | 能比较大小 | 能计算 hash，能判断相等 |
| 常用场景 | 有序、范围、稳定 | 快速查找、统计、缓存 |
key 类型要求不同：
map 需要 key 能比较大小：
c
map<int, string> m; // int 可以比较大小，没问题
map<string, int> m2; // string 也可以比较大小，没问题本质上它需要类似：
c
a < bunordered_map 需要 key 能哈希，并且能判断相等：
c
unordered_map<string, int> m; // string 标准库已经支持 hash本质上它需要：
c
hash(key)
a == b面试容易加分的点：
不要只说 unordered_map 一定比 map 快。更准确的说法是：
unordered_map 平均查找是 O(1)，通常比 map 快；但它依赖哈希函数质量，如果哈希冲突严重，最坏会退化到 O(n)。而 map 是红黑树，查找是稳定的 O(log n)，并且天然有序，适合范围查询和有序遍历。
还有一个坑：rehash。
unordered_map 元素越来越多时，桶不够用了，会扩容并重新分配桶，这叫 rehash。
c
unordered_map<int, string> m;
m[1] = "A";
m[2] = "B";
// 提前预留空间，减少 rehash 次数
m.reserve(1000);rehash 可能导致迭代器失效，所以如果你一边保存迭代器，一边大量插入，要小心。
面试回答模板：
TIP
map 和 unordered_map 都是 C++ 的关联容器，都是存 key-value。map 底层通常是红黑树，key 自动有序，查找、插入、删除是 O(log n)，适合有序遍历和范围查询。unordered_map 底层是哈希表，不保证顺序，平均查找插入是 O(1)，适合根据 key 快速查值，比如统计频率、缓存、ID 映射。但 unordered_map 依赖哈希函数，哈希冲突严重时可能退化，而且 rehash 可能导致迭代器失效。所以默认追求查找速度用 unordered_map，需要顺序或范围查询用 map。
set 和 unordered_set 区别是什么？
一句话理解：set 和 unordered_set 都是“集合”，只存 key，不存 value，并且元素不能重复。区别是：set 会自动排序，unordered_set 不排序但平均查找更快。
零基础理解： 假设你要存一批玩家 ID：
1003
1001
1002
1001集合的特点是：重复的只保留一份。
所以最终是：
1001
1002
1003或者无序地存成：
c
1002
1001
1003如果你用 set，它会自动按大小排序。 如果你用 unordered_set，它只保证“能找到、不会重复”，但不保证顺序。
set 是什么？
std::set 是有序集合。
c
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> ids;
ids.insert(1003);
ids.insert(1001);
ids.insert(1002);
ids.insert(1001); // 重复插入，set 不会保存第二份
for (int id : ids) {
// 输出时会自动从小到大
cout << id << endl;
}
return 0;
}输出：
c
1001
1002
1003set 底层通常是红黑树。红黑树是一种自平衡二叉搜索树，所以它能让元素一直保持有序。
查找、插入、删除复杂度通常是：
c
O(log n)unordered_set 是什么？
std::unordered_set 是无序集合。
c
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> ids;
ids.insert(1003);
ids.insert(1001);
ids.insert(1002);
ids.insert(1001); // 重复插入，也不会保存第二份
for (int id : ids) {
// 输出顺序不保证，可能不是从小到大
cout << id << endl;
}
return 0;
}它底层是哈希表。
大概过程是：
元素 -> hash(元素) -> 桶下标 -> 放进桶里平均查找、插入、删除复杂度是：
O(1)但如果哈希冲突很多，最坏可能退化成：
O(n)核心区别表：
| 对比点 | set | unordered_set |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 是否排序 | 自动排序 | 不保证顺序 |
| 是否允许重复 | 不允许 | 不允许 |
| 查找复杂度 | O(log n) | 平均 O(1) |
| 最坏复杂度 | O(log n) | 可能 O(n) |
| 范围查询 | 支持 | 不适合 |
| key 要求 | 能比较大小 | 能 hash，并能判断相等 |
| 常见用途 | 有序去重、范围查询 | 快速判重、快速判断存在 |
什么时候用 set？
当你需要“有序”时，用 set。
比如：排行榜、按 ID 排序输出、找某个范围内的数据。
c
set<int> scores = {90, 70, 80, 100};
// 找第一个 >= 80 的元素
auto it = scores.lower_bound(80);
if (it != scores.end()) {
cout << *it << endl; // 80
}set 很适合做这种范围相关操作：
c
lower_bound()
upper_bound()什么时候用 unordered_set？
当你只想快速判断“有没有这个东西”时，用 unordered_set。
c
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<string> loadedResources;
loadedResources.insert("hero.png");
loadedResources.insert("monster.png");
string name = "hero.png";
if (loadedResources.find(name) != loadedResources.end()) {
// 找到了，说明这个资源已经加载过
cout << "资源已经加载" << endl;
} else {
cout << "资源还没加载" << endl;
}
return 0;
}游戏里很常见：
c
unordered_set<int> aliveMonsterIds; // 记录还活着的怪物 ID
unordered_set<string> loadedAssetNames; // 记录已经加载过的资源名
unordered_set<int> unlockedSkillIds; // 记录已解锁技能因为你通常只关心：
这个 ID 在不在集合里？不关心它排第几。
insert 的返回值也常考：
c
set<int> s;
auto result = s.insert(10);
if (result.second) {
// second 为 true，说明插入成功
cout << "第一次插入 10" << endl;
} else {
// second 为 false，说明 10 已经存在
cout << "10 已经存在" << endl;
}set 和 unordered_set 都可以这样判断是否真的插入成功。
容易踩的坑：不要随便修改集合里的元素。
因为集合里的元素本身就是 key。
对于 set 来说，元素的位置依赖它的大小关系。 对于 unordered_set 来说，元素的位置依赖它的 hash 值。
如果你强行修改元素，容器内部结构可能就乱了。所以一般不能直接改集合中的元素，要先删除，再插入新的。
c
set<int> s = {1, 2, 3};
// 正确做法：先删旧值，再插新值
s.erase(2);
s.insert(20);NOTE
面试高分回答：set 和 unordered_set 都是用来存不重复元素的关联容器。set 底层通常是红黑树，会按照 key 自动排序，所以查找、插入、删除是稳定的 O(log n)，并且支持有序遍历和范围查询。unordered_set 底层是哈希表，不保证遍历顺序，平均查找、插入、删除是 O(1)，适合快速判重和判断元素是否存在。但它依赖哈希函数质量，冲突严重时可能退化，并且 rehash 可能导致迭代器失效。所以需要顺序或范围查询用 set，只追求快速存在性判断一般用 unordered_set。
deque 适合什么场景？
一句话理解：deque 适合“头部和尾部都要频繁插入、删除”的场景。它的全名是 double-ended queue，意思就是“双端队列”。
零基础理解：vector 像一整排连续座位，只在最后加人很方便；如果老是在最前面加人，就要把后面的人整体挪位置，很慢。
deque 更像一节一节车厢拼起来的队伍。前面可以加一节，后面也可以加一节，所以它两头操作都很方便。
c
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(10); // 尾部插入
dq.push_back(20); // 尾部插入
dq.push_front(5); // 头部插入
cout << dq.front() << endl; // 5，访问头部
cout << dq.back() << endl; // 20，访问尾部
dq.pop_front(); // 删除头部
dq.pop_back(); // 删除尾部
return 0;
}底层原理：deque 不是像 vector 那样一整块连续内存。
它通常是：
中控数组 + 多个连续小块可以粗略理解成：
c
map 指针数组
|
+-- 数据块 1: [1][2][3][4]
+-- 数据块 2: [5][6][7][8]
+-- 数据块 3: [9][10][11][12]所以它的特点是：
c
push_front() 快
push_back() 快
pop_front() 快
pop_back() 快
operator[] 支持随机访问但是它的内存不是整体连续的，所以缓存友好程度通常不如 vector。
适合场景 1：普通队列
比如 BFS、任务队列、消息队列，经常是后面进、前面出。
c
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> tasks;
tasks.push_back(1); // 新任务从尾部进入
tasks.push_back(2);
tasks.push_back(3);
while (!tasks.empty()) {
int task = tasks.front(); // 从头部取出最早的任务
tasks.pop_front(); // 删除已经处理的任务
cout << "处理任务: " << task << endl;
}
return 0;
}其实 std::queue 默认底层容器就是 deque：
c
#include <queue>
using namespace std;
queue<int> q; // 默认内部通常用 deque<int>适合场景 2：滑动窗口
比如算法题里常见的“滑动窗口最大值”，deque 非常经典。
c
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // 存下标，不直接存值
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
// 如果队头下标已经滑出窗口，就删掉
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 保持队列从大到小
// 如果新来的数更大，后面比它小的数就没用了
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
// 把当前下标加入队尾
dq.push_back(i);
// 当窗口长度达到 k 后，队头就是当前窗口最大值
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}这里 deque 的价值很明显： 队头要删过期元素，队尾要删没用元素，两头都在频繁操作。
适合场景 3：需要头尾都能加删的缓冲区
比如：
c
deque<string> logs;
logs.push_back("玩家登录");
logs.push_back("玩家进入战斗");
// 如果想在最前面补一条高优先级日志
logs.push_front("系统初始化完成");这种“前后都可能插入”的需求，用 deque 比 vector 更自然。
不适合什么场景？
deque 不适合大量中间插入删除。
c
deque<int> dq = {1, 2, 3, 4, 5};
// 在中间插入，通常需要移动元素，不是 deque 的优势
dq.insert(dq.begin() + 2, 99);如果你经常在中间插入删除，而且已经有目标位置的迭代器，可能考虑 list。 如果你主要是尾插、遍历、随机访问，通常优先考虑 vector。
deque 和 vector 对比：
| 对比点 | vector | deque |
|---|---|---|
| 底层 | 一整块连续数组 | 多个连续小块 |
| 尾部插入 | 快 | 快 |
| 头部插入 | 慢，需要移动大量元素 | 快 |
| 随机访问 | 快，缓存友好 | 支持，但通常略慢 |
| 中间插入删除 | 慢 | 也不适合 |
| 内存连续性 | 连续 | 不完全连续 |
| 适合场景 | 尾插、遍历、随机访问 | 两头频繁插入删除 |
CAUTION
面试高分回答：deque 是双端队列，适合头部和尾部都频繁插入删除的场景，比如 BFS 队列、任务队列、滑动窗口、单调队列等。它底层通常不是一整块连续内存，而是由多个固定大小的缓冲区组成，再通过一个中控数组管理这些缓冲区。所以它支持 push_front、push_back、pop_front、pop_back 的高效操作，也支持下标随机访问。但由于内存不完全连续，缓存友好性一般不如 vector，中间插入删除也不是它的优势。默认只需要尾插和遍历时用 vector，两头都要频繁操作时用 deque。
迭代器失效有哪些情况？
一句话理解： 迭代器失效就是：你手里的迭代器原来指向某个元素，但容器发生了插入、删除、扩容、rehash 等操作后，它指向的位置不再可靠了，再用它就可能出错。
零基础理解： 迭代器可以先理解成“指向容器里某个元素的指针”。
c
vector<int> v = {1, 2, 3};
auto it = v.begin(); // it 指向 1如果容器内部内存没变，it 还能用。 如果容器扩容、搬家、删除元素，那 it 可能还指着旧位置，这就叫迭代器失效。
最常见情况 1：vector 扩容导致全部失效
vector 底层是一整块连续数组。容量不够时，它会申请一块更大的新内存，把旧元素搬过去，再释放旧内存。
c
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
auto it = v.begin(); // 指向第一个元素 1
// 如果这次 push_back 导致 vector 扩容，
// 原来的内存会被释放，it 就失效了
v.push_back(3);
// 危险：it 可能已经失效
// cout << *it << endl;
// 正确：容器变化后重新获取迭代器
it = v.begin();
cout << *it << endl;
return 0;
}vector 规则要记住：
扩容：所有迭代器、指针、引用都失效
没扩容的 push_back：以前元素的迭代器一般还有效，但 end() 会失效
insert：插入位置以及后面的迭代器失效；如果扩容则全部失效
erase：删除位置以及后面的迭代器失效最常见情况 2：vector erase 后继续用旧迭代器
错误写法：
c
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == 3) {
v.erase(it); // it 被 erase 后已经失效
// 循环结尾还会 ++it，危险
}
}正确写法：
c
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ) {
if (*it == 3) {
// erase 会返回下一个有效迭代器
it = v.erase(it);
} else {
++it;
}
}
for (int x : v) {
cout << x << " ";
}
return 0;
}这个写法非常重要，面试和实际项目都常用。
情况 3：list 删除时，只有被删元素失效
list 是链表，每个元素是单独节点。插入新节点通常不会影响其他节点。
c
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> nums = {1, 2, 3, 4};
auto it1 = nums.begin(); // 指向 1
auto it2 = next(nums.begin(), 2); // 指向 3
nums.insert(nums.begin(), 100);
// list 插入一般不会让已有迭代器失效
cout << *it1 << endl; // 仍然可以用，输出 1
cout << *it2 << endl; // 仍然可以用，输出 3
nums.erase(it2);
// it2 指向的元素已经被删除，所以 it2 失效
// cout << *it2 << endl; // 危险
return 0;
}list 规则：
c
insert：其他迭代器不失效
erase：只有被删除元素的迭代器失效情况 4：map / set 删除时，被删元素失效
map、set 底层通常是红黑树，属于节点型容器。
c
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m[1] = "A";
m[2] = "B";
m[3] = "C";
auto it1 = m.find(1);
auto it2 = m.find(2);
m.erase(it2);
cout << it1->second << endl; // 安全，it1 还有效
// it2 指向的节点已经被删除，不能再用
// cout << it2->second << endl; // 危险
return 0;
}map / set 规则：
insert：一般不影响已有迭代器
erase：只有被删除元素的迭代器失效情况 5：unordered_map / unordered_set rehash 导致失效
哈希容器底层是哈希表。元素多了以后，桶不够用，会重新分配桶，这叫 rehash。
c
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> m;
m[1] = "A";
m[2] = "B";
auto it = m.find(1);
// 插入大量元素，可能触发 rehash
for (int i = 3; i < 1000; i++) {
m[i] = "X";
}
// it 可能已经因为 rehash 失效
// cout << it->second << endl; // 危险
// 正确：重新 find
it = m.find(1);
if (it != m.end()) {
cout << it->second << endl;
}
return 0;
}unordered_map / unordered_set 规则：
c
insert：如果没有 rehash，一般不影响已有迭代器
insert：如果触发 rehash，所有迭代器失效
erase：被删除元素的迭代器失效
rehash / reserve：通常会让所有迭代器失效想减少 rehash，可以提前：
c
unordered_map<int, string> m;
// 提前预留空间，减少扩容和 rehash
m.reserve(1000);情况 6：deque 的规则比较绕
deque 是双端队列，底层不是一整块连续内存，而是多个小块组成。
它的特点是两头插入删除很快：
c
deque<int> dq;
dq.push_front(1);
dq.push_back(2);但是它的迭代器失效规则比 vector、list 更容易记混。
大致面试记法：
c
push_front / push_back：可能导致迭代器失效，尤其 end() 要小心
pop_front / pop_back：被删除元素的迭代器失效
中间 insert / erase：通常会导致大量甚至全部迭代器失效所以 deque 里不要长期保存迭代器，容器修改后尽量重新获取。
常见容器总结表：
| 容器 | 插入是否导致失效 | 删除是否导致失效 |
|---|---|---|
vector | 扩容则全部失效；不扩容时插入位置及后面失效 | 删除位置及后面失效 |
string | 类似 vector | 类似 vector |
deque | 头尾操作也要小心；中间插入通常影响很大 | 中间删除通常影响很大 |
list | 一般不影响其他迭代器 | 只有被删元素失效 |
map / set | 一般不影响其他迭代器 | 只有被删元素失效 |
unordered_map / unordered_set | rehash 则全部迭代器失效 | 被删元素失效 |
最安全的 erase 写法：
c
for (auto it = container.begin(); it != container.end(); ) {
if (需要删除) {
// erase 返回删除后下一个有效位置
it = container.erase(it);
} else {
++it;
}
}不要这样写：
c
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == 3) {
v.erase(it); // erase 后 it 已经不可靠
}
}因为循环最后还会 ++it，但 it 已经失效了。
IMPORTANT
面试高分回答： 迭代器失效本质上是容器结构变化后，原来的迭代器不再指向有效位置。连续内存容器比如 vector、string，扩容会重新分配内存，导致所有迭代器、指针、引用失效；插入或删除会导致操作位置及其后的迭代器失效。节点型容器比如 list、map、set，插入一般不影响已有迭代器，删除只会让被删元素的迭代器失效。哈希容器比如 unordered_map、unordered_set，如果插入触发 rehash，所有迭代器会失效；删除时被删元素失效。deque 比较特殊，头尾操作很快，但中间插入删除容易导致大量迭代器失效。实际写代码时，erase 后要使用返回的新迭代器，容器修改后不要继续使用旧的 end() 或旧迭代器。
sort 底层大概是什么？
一句话理解：std::sort 底层通常不是单纯的快速排序，而是“内省排序” introsort：快速排序 + 堆排序 + 插入排序。
零基础理解： 你可以把 std::sort 理解成一个很聪明的排序工具：
平时它用类似快速排序的方法，因为快。 如果发现快速排序递归太深，可能要退化，它就切换成堆排序兜底。 如果只剩很小一段数组，它用插入排序收尾，因为小数据量下插入排序常数小，反而划算。
也就是：
std::sort ≈ 快速排序 + 堆排序 + 插入排序为什么不是只用快速排序？
快速排序平均很快：
平均时间复杂度：O(n log n)但是如果 pivot 选得很差，比如每次都把数组分得特别不均匀，最坏可能退化成：
最坏时间复杂度：O(n^2)std::sort 为了避免这种情况，主流实现会用 introsort。
introsort 是什么？
introsort 中文常叫“内省排序”。
它的思路是：
一开始：用快速排序
如果递归深度太深：切换成堆排序
如果区间很小：用插入排序这样它既想要快速排序的平均性能，又想要堆排序的最坏情况保障。
大概流程：
sort(array):
如果区间很大：
先用快速排序思想 partition
如果递归太深：
改用堆排序
如果区间很小：
用插入排序收尾注意：这只是帮助理解的伪代码，不是标准库源码。
代码怎么用？
c
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {5, 2, 9, 1, 7};
// 默认从小到大排序
sort(nums.begin(), nums.end());
for (int x : nums) {
cout << x << " ";
}
return 0;
}输出：
c
1 2 5 7 9自定义排序：
c
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {5, 2, 9, 1, 7};
// 从大到小排序
sort(nums.begin(), nums.end(), [](int a, int b) {
// 返回 true 表示 a 应该排在 b 前面
return a > b;
});
for (int x : nums) {
cout << x << " ";
}
return 0;
}输出：
c
9 7 5 2 1排序结构体：
c
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Player {
string name;
int score;
};
int main() {
vector<Player> players = {
{"Tom", 90},
{"Alice", 95},
{"Bob", 80}
};
sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
// 按分数从高到低排序
return a.score > b.score;
});
for (const Player& p : players) {
cout << p.name << " " << p.score << endl;
}
return 0;
}std::sort 的特点：
| 特点 | 说明 |
|---|---|
| 平均复杂度 | O(n log n) |
| 主流底层 | introsort |
| 是否稳定 | 不稳定 |
| 是否原地排序 | 基本是原地排序 |
| 需要什么迭代器 | 随机访问迭代器 |
| 常用容器 | vector、array、deque、普通数组 |
| 不适合 | list 不能直接用 std::sort |
为什么 list 不能用 std::sort？
std::sort 需要随机访问迭代器。
也就是说它需要能快速做这种操作：
c
it + 5
it - 3
middle = begin + length / 2vector 可以，因为它底层是连续数组。
c
vector<int> v = {3, 1, 2};
sort(v.begin(), v.end()); // 可以但 list 是链表，不能快速跳到第几个元素。
c
list<int> l = {3, 1, 2};
// sort(l.begin(), l.end()); // 错误，list 迭代器不是随机访问迭代器
l.sort(); // 正确，list 有自己的 sortstd::sort 稳定吗？
不稳定。
“不稳定”的意思是：如果两个元素排序关键字相等，它们原来的相对顺序不保证保持。
比如：
c
struct Student {
string name;
int score;
};原数据：
c
Tom 90
Bob 90
Alice 80如果按分数排序，Tom 和 Bob 都是 90。 使用 std::sort 后，不保证 Tom 仍然在 Bob 前面。
如果你需要稳定排序，要用：
c
stable_sort(v.begin(), v.end(), cmp);比较函数的坑：
比较函数必须满足严格弱序。
简单说，不要写这种：
c
sort(nums.begin(), nums.end(), [](int a, int b) {
return a <= b; // 错误
});正确写法：
c
sort(nums.begin(), nums.end(), [](int a, int b) {
return a < b; // 正确
});为什么 <= 错？ 因为当 a == b 时，a <= b 是 true，b <= a 也是 true。排序器会被这种逻辑搞乱，可能出现未定义行为。
IMPORTANT
面试高分回答：std::sort 标准并不强制规定具体实现，但主流 STL 一般使用 introsort，也就是内省排序。它一开始使用快速排序思想做 partition，因为快速排序平均性能好、缓存友好；当递归深度过深时，为了避免快速排序退化到 O(n^2)，会切换到堆排序，把最坏复杂度控制在 O(n log n)；对于小区间，通常用插入排序收尾，因为小数据量下插入排序常数开销低。std::sort 是不稳定排序，需要随机访问迭代器，所以常用于 vector、数组、deque，不能直接用于 list，list 要用自己的 list.sort()。
priority_queue 底层是什么？
一句话理解：priority_queue 底层默认是 vector，再用“堆”来维护优先级。默认是大根堆，也就是最大的元素先出来。
零基础理解： 普通队列 queue 是“先来先服务”：
先进去的，先出来但 priority_queue 是“谁优先级高，谁先出来”：
分数最高的，先出来
血量最低的，先处理
距离最短的，先处理比如：
c
priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(50);
cout << pq.top() << endl; // 50虽然 50 不是第一个插入的，但它最大，所以它先出来。
底层是什么？
priority_queue 是一个容器适配器。
意思是：它自己不是从零实现一个新容器，而是套在别的容器上，对外提供一套“优先队列”的接口。
默认大概可以理解成：
c
priority_queue<T> = vector<T> + heap默认底层容器是：
c
vector<T>默认堆规则是：
大根堆所以默认：
top() 取最大值什么是堆？
堆不是“内存里的堆区”那个堆。这里的堆是一种数据结构。
大根堆满足：
父节点 >= 子节点比如：
c
90
/ \
70 60
/ \ / \
40 50 20 10最大值永远在最上面，所以 top() 很快：
c
O(1)但注意，堆不是完全有序。
它只保证父节点比子节点优先级高，不保证整个数组从大到小排好。
priority_queue 的常用操作：
c
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(30); // 插入元素
pq.push(10);
pq.push(50);
cout << pq.top() << endl; // 查看堆顶，输出 50
pq.pop(); // 删除堆顶，也就是删除 50
cout << pq.top() << endl; // 输出 30
return 0;
}复杂度：
| 操作 | 复杂度 | 原因 |
|---|---|---|
top() | O(1) | 堆顶就在数组第一个位置 |
push() | O(log n) | 插入后要向上调整 |
pop() | O(log n) | 删除堆顶后要向下调整 |
size() | O(1) | 直接记录大小 |
empty() | O(1) | 判断是否为空 |
push 底层大概发生什么？
c
pq.push(80);底层可以粗略理解成：
1. 先把 80 放到 vector 最后
2. 然后不断和父节点比较
3. 如果 80 比父节点优先级更高，就往上交换
4. 最后重新满足堆规则类似：
c
vector.push_back(value);
push_heap(vector.begin(), vector.end());pop 底层大概发生什么？
c
pq.pop();底层可以粗略理解成：
1. 把堆顶元素和最后一个元素交换
2. 删除最后一个元素
3. 把新的堆顶向下调整
4. 重新满足堆规则类似：
c
pop_heap(vector.begin(), vector.end());
vector.pop_back();默认是大根堆：
c
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
while (!pq.empty()) {
cout << pq.top() << " "; // 每次取最大值
pq.pop();
}
return 0;
}输出：
c
5 3 1怎么写小根堆？
小根堆就是最小的元素先出来。
c
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
// 小根堆：最小值优先
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(3);
pq.push(1);
pq.push(5);
while (!pq.empty()) {
cout << pq.top() << " "; // 每次取最小值
pq.pop();
}
return 0;
}输出：
c
1 3 5这里三个模板参数分别是：
c
priority_queue<元素类型, 底层容器, 比较规则>也就是：
c
priority_queue<int, vector<int>, greater<int>>表示：
c
元素是 int
底层用 vector<int>
比较规则用 greater<int>自定义结构体怎么用？
比如游戏里有任务，优先处理优先级高的任务：
c
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Task {
int id;
int priority;
};
struct CompareTask {
bool operator()(const Task& a, const Task& b) const {
// 返回 true 表示 a 的优先级比 b 低
// priority_queue 会把“更不低”的放到 top
return a.priority < b.priority;
}
};
int main() {
priority_queue<Task, vector<Task>, CompareTask> pq;
pq.push({1, 10});
pq.push({2, 50});
pq.push({3, 30});
while (!pq.empty()) {
Task t = pq.top();
pq.pop();
cout << "处理任务 id = " << t.id
<< ", priority = " << t.priority << endl;
}
return 0;
}输出顺序是：
c
priority = 50
priority = 30
priority = 10比较器最容易绕的地方：
很多初学者会疑惑：
c
return a.priority < b.priority;为什么这是大优先级先出来？
你可以这样记：
在 priority_queue 里，比较器返回 true 的那个，会被认为“优先级更低，应该往后排”。
所以：
c
return a.priority < b.priority;意思是：
c
a.priority 小于 b.priority 时，a 优先级更低因此大的 priority 会在前面。
priority_queue 不能做什么？
它不能像 vector 一样随便遍历出有序结果。
c
priority_queue<int> pq;底层虽然是 vector，但这个 vector 只满足堆结构，不是完全有序数组。
如果你想从大到小拿结果，要反复：
c
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}适合什么场景？
priority_queue 适合“每次都要拿当前最优元素”的场景。
常见例子：
任务调度：优先级高的任务先执行
排行榜：取当前最高分
寻路算法：Dijkstra / A*
合并多个有序数组
Top K 问题
事件系统：时间最早的事件先触发例如 Top K：
c
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {5, 1, 9, 3, 7, 2};
int k = 3;
// 小根堆，堆里只保留最大的 k 个数
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : nums) {
pq.push(x);
// 如果超过 k 个，就弹出最小的
// 剩下的就是当前最大的 k 个
if (pq.size() > k) {
pq.pop();
}
}
cout << "第 " << k << " 大的数是: " << pq.top() << endl;
return 0;
}NOTE
面试高分回答：priority_queue 是 C++ STL 的容器适配器，默认底层容器是 vector，并在这个 vector 上维护堆结构。默认比较器是 less<T>，所以默认是大根堆，top() 返回当前最大元素。它不是完全排序的容器，只保证堆顶元素优先级最高。插入时先放到底层容器末尾，再向上调整堆，复杂度是 O(log n)；删除时删除堆顶，然后把元素向下调整，复杂度也是 O(log n)；访问堆顶是 O(1)。如果要小根堆，可以写 priority_queue<int, vector<int>, greater<int>>。它适合每次都需要取当前最大或最小元素的场景，比如 Top K、任务调度、Dijkstra、A* 等。
如何自定义哈希函数？
一句话理解： 自定义哈希函数就是告诉 unordered_map / unordered_set：我的自定义类型应该怎么转换成一个 size_t 数字，用来决定放进哪个哈希桶。
零基础理解：unordered_map 和 unordered_set 底层是哈希表。它们查找元素时大概分两步：
1. 用 hash(key) 算出一个数字，决定去哪个桶找
2. 在桶里用 == 判断是不是目标 key所以自定义哈希时，通常要提供两个东西：
哈希函数：怎么把 key 变成 size_t
相等判断：怎么判断两个 key 是不是同一个例子：自定义一个坐标 Point
假设我们想把二维坐标放进 unordered_set：
c
Point(1, 2)
Point(3, 4)
Point(1, 2)重复坐标只保留一份。
c
#include <iostream>
#include <unordered_set>
using namespace std;
struct Point {
int x;
int y;
// 判断两个 Point 是否相等
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
struct PointHash {
size_t operator()(const Point& p) const {
// 分别计算 x 和 y 的哈希值
size_t h1 = hash<int>()(p.x);
size_t h2 = hash<int>()(p.y);
// 把两个哈希值混合起来
// 这里用一个常见的 hash combine 写法
return h1 ^ (h2 << 1);
}
};
int main() {
unordered_set<Point, PointHash> points;
points.insert({1, 2});
points.insert({3, 4});
points.insert({1, 2}); // 重复，不会插入第二份
cout << points.size() << endl; // 输出 2
return 0;
}这里：
c
PointHash负责算哈希。
operator==负责判断两个 Point 是否相等。
最重要规则：相等的 key，哈希值必须相同
必须满足：
c
如果 a == b，那么 hash(a) 必须 == hash(b)但是反过来不要求。
也就是说：
c
hash(a) == hash(b)不一定代表：
c
a == b因为可能发生哈希冲突。
哈希冲突就是：两个不同的 key 被分到了同一个桶里。
方式 1：用函数对象，最常见
c
#include <iostream>
#include <unordered_map>
using namespace std;
struct GridPos {
int row;
int col;
// 两个格子位置相同，才认为是同一个 key
bool operator==(const GridPos& other) const {
return row == other.row && col == other.col;
}
};
struct GridPosHash {
size_t operator()(const GridPos& pos) const {
size_t h1 = hash<int>()(pos.row);
size_t h2 = hash<int>()(pos.col);
// 混合 row 和 col 的哈希值
return h1 ^ (h2 << 1);
}
};
int main() {
unordered_map<GridPos, string, GridPosHash> gridNames;
gridNames[{0, 0}] = "出生点";
gridNames[{1, 2}] = "宝箱";
gridNames[{3, 4}] = "怪物";
GridPos target{1, 2};
if (gridNames.find(target) != gridNames.end()) {
cout << gridNames[target] << endl;
}
return 0;
}这个写法面试最稳。
方式 2：自定义相等函数
如果你不想在结构体里写 operator==，也可以单独写相等比较器：
c
#include <iostream>
#include <unordered_set>
using namespace std;
struct Point {
int x;
int y;
};
struct PointHash {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
struct PointEqual {
bool operator()(const Point& a, const Point& b) const {
// x 和 y 都相等，才认为是同一个点
return a.x == b.x && a.y == b.y;
}
};
int main() {
unordered_set<Point, PointHash, PointEqual> s;
s.insert({10, 20});
s.insert({10, 20});
cout << s.size() << endl; // 输出 1
return 0;
}模板参数含义是：
c
unordered_set<元素类型, 哈希函数, 相等判断>也就是：
c
unordered_set<Point, PointHash, PointEqual>方式 3：特化 std::hash
你也可以让自己的类型像 int、string 一样直接被 unordered_set 使用。
c
#include <iostream>
#include <unordered_set>
using namespace std;
struct Point {
int x;
int y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
namespace std {
template <>
struct hash<Point> {
size_t operator()(const Point& p) const {
size_t h1 = hash<int>()(p.x);
size_t h2 = hash<int>()(p.y);
return h1 ^ (h2 << 1);
}
};
}
int main() {
unordered_set<Point> s;
s.insert({1, 2});
s.insert({1, 2});
s.insert({3, 4});
cout << s.size() << endl; // 输出 2
return 0;
}这样就可以直接写：
c
unordered_set<Point> s;不过注意：通常只建议对你自己定义的类型特化 std::hash，不要随便改标准库已有类型。
方式 4：用 lambda 写哈希函数
临时用一下时，可以用 lambda：
c
#include <iostream>
#include <unordered_set>
using namespace std;
struct Point {
int x;
int y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
int main() {
auto hashPoint = [](const Point& p) {
size_t h1 = hash<int>()(p.x);
size_t h2 = hash<int>()(p.y);
return h1 ^ (h2 << 1);
};
unordered_set<Point, decltype(hashPoint)> s(10, hashPoint);
s.insert({1, 2});
s.insert({3, 4});
cout << s.size() << endl;
return 0;
}这里比较绕的是：
c
decltype(hashPoint)表示“这个 lambda 的类型”。
构造时也要把 lambda 对象传进去：
c
unordered_set<Point, decltype(hashPoint)> s(10, hashPoint);pair 怎么自定义哈希？
这个也很常考，比如想用坐标作为 key：
c
#include <iostream>
#include <unordered_map>
using namespace std;
struct PairHash {
size_t operator()(const pair<int, int>& p) const {
size_t h1 = hash<int>()(p.first);
size_t h2 = hash<int>()(p.second);
// 混合 first 和 second
return h1 ^ (h2 << 1);
}
};
int main() {
unordered_map<pair<int, int>, string, PairHash> grid;
grid[{0, 0}] = "出生点";
grid[{2, 3}] = "宝箱";
cout << grid[{2, 3}] << endl;
return 0;
}不要写很差的哈希函数
比如：
c
struct BadHash {
size_t operator()(const Point& p) const {
return 1; // 所有 key 都进同一个桶
}
};这样虽然程序可能还能运行，但哈希表会退化，查找效率可能从平均：
c
O(1)退化成：
c
O(n)因为所有元素都挤在同一个桶里。
更好的 hash combine 写法
简单面试可以写：
c
return h1 ^ (h2 << 1);如果想更专业一点，可以写类似：
c
size_t seed = 0;
seed ^= hash<int>()(p.x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash<int>()(p.y) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;完整例子：
c
struct PointHash {
size_t operator()(const Point& p) const {
size_t seed = 0;
// 把 x 的哈希混入 seed
seed ^= hash<int>()(p.x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 把 y 的哈希混入 seed
seed ^= hash<int>()(p.y) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};你不用死记这个常数，只要面试能说出“多个字段的哈希要组合，尽量减少冲突”就很好。
TIP
面试高分回答： 在 C++ 里，如果要让自定义类型作为 unordered_map 或 unordered_set 的 key，需要提供哈希函数和相等判断。哈希函数通常写成函数对象，重载 operator()，返回 size_t，内部可以使用 std::hash<int>、std::hash<string> 分别计算字段哈希，再组合起来。同时必须保证相等规则和哈希规则一致：如果两个 key 相等，它们的 hash 值必须相同；但 hash 值相同不一定表示 key 相等，因为可能有哈希冲突，最终还要靠 operator== 或自定义 KeyEqual 判断。实际项目中要避免所有 key 都落到同一个桶里，否则 unordered_map 平均 O(1) 的查找可能退化成 O(n)。