STL 容器

容器分类

分类	容器	常见实现/特征
序列容器	vector、deque、list、forward_list、array	关注元素位置与遍历顺序
有序关联容器	set、multiset、map、multimap	通常红黑树，按比较器有序，O(log n)
无序关联容器	unordered_set、unordered_map 等	哈希表，平均 O(1)，无顺序
容器适配器	stack、queue、priority_queue	在底层容器上限定操作接口

容器适配器

stack、queue 和 priority_queue 不是独立的节点存储结构，而是对底层容器暴露受限操作的适配器。std::priority_queue 默认以 std::vector 为底层，提供 top()、push()、pop()，但不提供按下标访问或按值删除；它维护堆序而非完整排序。大/小顶堆写法、比较器、Top K 和索引堆的取舍统一见堆与优先队列，避免在此重复维护两份实现说明。

vector 与 list

维度	std::vector	std::list
底层布局	连续动态数组	双向链表节点
随机访问	O(1)	O(n)
尾部插入/删除	均摊 O(1)	O(1)
已知位置插入/删除	O(n)，需移动元素	O(1)，已有迭代器时仅改链接
缓存局部性	好，通常遍历快	差，节点额外存指针且分散分配
迭代器失效	扩容会全部失效；中间插删影响后续位置	插删通常只使被删元素的迭代器失效

不要因为“中间插入是 O(1)”就默认选 list：找到插入位置本身常需 O(n)，且内存分配和缓存未命中成本高。实际程序中 vector 往往是序列容器的默认首选。

vector 原理与扩容

vector 管理一块连续存储，逻辑上有 size()（已构造元素数）和 capacity()（当前可容纳数）。push_back 在容量足够时直接在末尾构造；容量不足时会：

1. 申请更大的连续内存；
2. 移动（若不能移动则拷贝）已有元素到新内存；
3. 销毁旧元素并释放旧内存；
4. 在新末尾构造新元素。

这使尾部追加具有均摊 O(1) 复杂度，但单次扩容为 O(n)，且原有指针、引用、迭代器全部失效。增长比例是实现细节，标准并不保证“固定扩容”或“每次翻倍”。已知元素数量时调用 reserve(n) 可减少扩容；resize 则会改变元素数量，不应混淆。

两个 vector 如何交换

std::vector<int> a(N), b(N);
std::swap(a, b); // 等价于调用 a.swap(b)

默认 allocator 下，std::swap(a, b) / a.swap(b) 的复杂度是 O(1)：交换的是内部数据指针、size、capacity 等控制信息，而不是逐个交换元素。该结论与两个容器的长度是否相同无关。交换后，原先指向 a 元素的指针/引用/迭代器仍指向同一批元素，但这些元素现在属于 b；反之亦然。

不要和以下操作混淆：

操作	复杂度
std::swap(a, b)，a、b 为 vector	O(1)
遍历并交换 a[i]、b[i]	O(N)
std::swap_ranges(a.begin(), a.end(), b.begin())	O(N)

对于不兼容的自定义 allocator，容器交换可能不满足常数时间前提，甚至不应执行；日常默认 allocator 场景下，面试回答“交换内部控制信息，所以是 O(1)”即可。

push_back 与 emplace_back

items.push_back(Widget{a, b}); // 先有一个 Widget，再复制/移动进容器（可被优化）
items.emplace_back(a, b);      // 直接以 a、b 在末尾构造 Widget

emplace_back 接收构造参数并原地构造，通常可少一次移动，但并非总是更快或更安全：若已有对象，push_back(std::move(obj)) 很清晰；emplace_back 的完美转发还可能调用意料外的构造函数。应以语义清晰为先。

有序与无序关联容器

map 与 unordered_map

维度	map	unordered_map
实现	通常红黑树	哈希表（实现常用桶+链式/其他冲突处理）
顺序	按比较器有序	无排序保证
查找/插入/删除	O(log n)	平均 O(1)，最坏 O(n)
范围查询	高效	不适合按键范围遍历
迭代器	插入通常不使已有迭代器失效	rehash 会使迭代器失效

unordered_map 也不允许重复键；不同键可以有相同哈希值，容器会处理哈希冲突。需要重复键请用 multimap 或 unordered_multimap。

unordered_map 与哈希表

unordered_map 以哈希表实现平均 O(1) 的精确 key 查找。哈希函数将 key 映射到桶，哈希冲突后仍必须用相等比较确认；自定义 Hash 与 KeyEqual 必须满足“相等的 key 有相同哈希值”的契约。

拉链法、开放寻址法、探测策略、墓碑删除、装载因子和冲突攻击等底层原理统一见哈希表，避免在容器与数据结构笔记中重复维护两份说明。

std::unordered_map 的标准不规定具体的冲突处理或物理存储实现；它提供桶相关接口，但不能据此假定节点布局、探测方式或桶内容器。实际实现常采用桶结构和节点式存储。它维护桶数量 bucket_count() 与元素数量 size()；两者的比值是装载因子：

load_factor = size / bucket_count

装载因子过高，桶内冲突增多，平均查找会变慢。容器会在超过 max_load_factor() 时扩容并 rehash：创建更多桶、按新桶数重新分配元素。rehash 单次为 O(n)，且会使迭代器失效；但由于不在每次插入时发生，插入的平均复杂度通常仍是摊还 O(1)。已知元素数量时，可提前调用 reserve(n) 减少 rehash。

std::unordered_map<std::string, int> counts;
counts.reserve(expected_count);          // 预留能容纳 expected_count 的桶数
counts.max_load_factor(0.7F);            // 更低负载：更少冲突，更多内存

max_load_factor 调低会减少平均桶长、提高查找速度，但要使用更多桶；不能把它当作“冲突不存在”的保证。自定义 Hash 和 KeyEqual 必须满足同一契约：equal(a, b) == true 时必须有 hash(a) == hash(b)，否则查找行为不正确。对于组合键，不能只对一个字段哈希；应组合所有参与相等比较的字段。

最坏复杂度、冲突攻击和拉链 / 开放寻址的工程取舍见哈希表。

其他序列容器

deque

deque 通常是分段连续存储：用一张索引表管理多个固定大小块，而非一个可无限扩大的连续数组。因此它支持 O(1) 随机访问和两端均摊 O(1) 插删，但不保证整个元素区间连续；指针/迭代器失效规则也比 vector 更复杂。

元素块内连续、块与块之间未必相邻；实现可以调整索引表，因此不能把 deque 的迭代器稳定性等同于 list。

list

list 通常为双向链表，擅长已知位置的常数时间插删、splice 节点转移；不支持随机访问，查找线性，额外指针和分配开销较大。

迭代器、引用与并发访问

以下是常用操作的安全速查；具体重载和标准版本仍应查阅对应容器文档：

容器与操作	迭代器 / 指针 / 引用规则
vector::push_back 发生扩容	所有迭代器、指针、引用失效
vector::push_back 未扩容	既有元素的迭代器、指针、引用仍有效；end() 失效
vector 中间 insert/erase 未扩容	操作位置及之后的迭代器、指针、引用失效
list / forward_list 插入	既有元素迭代器、指针、引用保持有效
list / 有序关联容器 erase(it)	只使被删元素失效；C++11 起 erase(it) 返回后继迭代器
map / set 插入	既有元素迭代器、指针、引用保持有效
unordered_map rehash	全部迭代器失效；引用和指针通常仍指向元素，但不要把它与迭代器混用
deque	首尾或中间操作的规则不同，插入时迭代器可能失效；需要长期稳定地址/迭代器时优先核对具体操作或选择节点容器

可以一边遍历一边插入吗

按容器类型区分：

• vector / deque / string：不行。插入会使迭代器失效（vector 扩容时全部失效，未扩容时插入点及之后的迭代器失效），元素移动还会让遍历跳过或重复访问元素。
• list / forward_list / map / set：可以。插入不使既有迭代器失效；在 it 之前插入的键会出现在后续遍历中，注意避免死循环。
• unordered_map / unordered_set：不建议。插入可能触发 rehash 使全部迭代器失效；先收集待插入内容、循环结束后统一插入，或提前 reserve 避免 rehash。

一边遍历一边删除的正确写法

C++11 起所有容器 erase(it) 都返回指向“被删元素之后”的迭代器，直接赋值给循环变量即可，不要再 ++：

// vector / deque / string：erase 返回后继
for (auto it = v.begin(); it != v.end();) {
    if (条件(*it)) it = v.erase(it); // 返回值是下一个元素的位置
    else ++it;
}

// list / map / set / unordered_*：同样适用
for (auto it = m.begin(); it != m.end();) {
    if (条件(*it)) it = m.erase(it);
    else ++it;
}

vector 的批量删除更适合“先搬移后删除”的 remove-erase 惯用法，避免反复移动元素：

v.erase(std::remove_if(v.begin(), v.end(), 条件), v.end());

C++11 之前的写法是 m.erase(it++)（先自增再删除），现在不必使用。注意：list / map / set 的 erase(it) 只使被删迭代器失效，其他迭代器保持有效；而 vector 删除点之后的迭代器全部失效——这正是删除循环必须使用 erase 返回值的原因。

线程安全

• C++ 标准不保证任何容器线程安全：无外部同步时，同一容器上并发“读 + 写”或“写 + 写”是数据竞争，属于未定义行为。
• 只读并发：多个线程同时以 const 方式访问同一容器通常安全；实现还须避免同一容器不同元素被并发修改时引入数据竞争（vector<bool> 例外）。
• 任何结构性修改（插入、删除、rehash、排序）都必须互斥；一边遍历一边由其他线程插入/删除是典型的数据竞争场景。
• 工程实践：多读少写用 std::shared_mutex，简单或写多场景用 std::mutex；也可以按线程分片容器或改用无锁队列等结构避免共享。