STL 容器

容器分类

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

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 则会改变元素数量，不应混淆。

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 与 deque

map 与 unordered_map

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

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

哈希表如何实现

哈希表先通过哈希函数把 key 转换为整数哈希值，再映射到桶数组下标：

index = hash(key) % bucket_count
buckets[index] → 该桶中保存的元素

查找、插入和删除时，先定位桶，再在桶内比较 key。哈希表要满足：若两个 key 相等，它们的哈希值必须相等；哈希值相同不代表 key 一定相等，所以还必须用相等比较函数确认。

不同 key 落到同一个桶称为哈希冲突，常见处理方式：

• 拉链法：每个桶关联一条链（或其他小型容器），冲突元素挂在同一桶后；
• 开放寻址法：所有元素直接放在桶数组中，冲突时按线性探测、二次探测或双重哈希继续寻找空位。

std::unordered_map 的标准不规定具体使用哪一种实现，实际实现通常采用桶结构和节点式存储。它维护桶数量 bucket_count() 与元素数量 size()；两者的比值是装载因子：

load_factor = size / bucket_count

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

deque

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

list

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