C++ STL 容器怎么选？vector/map/unordered_map 对比与算法

STL 容器分四类。序列容器：vector 连续内存随机访问 O(1) 尾插 O(1) 中间插 O(n)；deque 双端队列两端 O(1)；list 双向链表任意位置 O(1) 但不支持随机访问。关联容器：map/set 基于红黑树有序 O(log n)，map 存键值对 set 存键。无序容器：unordered_map/unordered_set 基于哈希表平均 O(1) 最坏 O(n)。容器适配器：stack（默认 deque）、queue（默认 deque）、priority_queue（默认 vector+堆算法）。常用算法：sort O(nlogn)、find O(n)、copy、transform、accumulate。选容器先看需求：随机访问选 vector，频繁头插选 deque，频繁中间插选 list，查找为主选 unordered_map/set，需要有序选 map/set。

追问

vector 扩容机制是什么？怎么避免？

vector 满了重新分配更大内存（通常翻倍），把旧元素拷贝/移动过去，再释放旧内存。这会导致迭代器失效和性能抖动。提前 reserve(预估大小) 可避免运行时扩容，shrink_to_fit 可释放多余容量。

map 和 unordered_map 怎么选？

需要键有序遍历、范围查询用 map。只做查找/插入/删除不关心顺序用 unordered_map，平均 O(1) 比 O(log n) 快。unordered_map 的坑：最坏 O(n)（哈希冲突严重时）、自定义类型要手写 hash 函数和相等判断。

什么操作会使迭代器失效？

vector：insert/erase 当前位置及之后失效，reserve 后全部失效。list：只有被删除位置的失效，其他不受影响。map/set：只有被删除元素的失效。遍历中删除元素要用 it = container.erase(it) 模式。

emplace_back 和 push_back 有什么区别？

push_back 先构造临时对象再移动/拷贝进容器。emplace_back 直接在容器内存中原地构造参数，省去一次移动。对于简单类型差别不大，对复杂对象 emplace_back 更高效。