STL之容器比较

STL 标准容器优劣简述C11 及以后工程选型速查先划分大类顺序容器vector、deque、list、forward_list、array关联容器set/multiset、map/multimap红黑树有序无序关联容器unordered_set、unordered_map哈希表一、顺序容器1. std::vector动态连续数组✅优点内存连续随机访问 O (1)缓存友好遍历速度最快API 简单支持尾插尾删摊销 O (1)。 ❌缺点中间插入 / 删除O(n)需要挪动大量元素容量满时触发扩容产生内存重分配、迭代器失效不支持头部高效插入删除。 适用绝大多数场景优先默认选择。2. std::deque双端队列分段连续内存✅优点头部、尾部插入删除均为摊销 O (1)支持随机访问 O (1)比 vector 略慢扩容不需要拷贝全部元素迭代器失效范围更小。 ❌缺点内存分段缓存局部性差遍历慢于 vector中间插入删除依然 O (n)。 适用需要频繁头尾增删又偶尔随机访问。3. std::list双向链表✅优点任意位置插入 / 删除 O (1)前提已有迭代器不会发生内存重分配插入不使其他迭代器失效。 ❌缺点无随机访问只能顺序遍历每个节点额外存储前后指针内存开销大内存碎片化缓存极差遍历很慢。 适用频繁中间增删、极少遍历查找现代工程很少用。4. std::forward_list单向链表✅优点比 list 内存开销更小只有后继指针。 ❌缺点仅单向遍历不支持反向迭代不能获取 size ()。 适用内存极度受限场景。5. std::array静态数组栈 / 静态内存✅优点栈分配、无堆开销、随机访问 O (1)、内存连续。 ❌缺点容量编译期固定不能动态扩容。 适用长度已知的小型固定数组。二、有序关联容器红黑树实现set/map/multiset/multimapstd::set / std::map✅优点自动有序查找、插入、删除O(log n)迭代遍历按排序顺序输出set 自动去重map 存储 key-valuekey 唯一。 ❌缺点节点分散缓存不友好O (log n) 复杂度慢于哈希表key 不可修改破坏有序结构multiset/multimap 允许重复键。 适用要求有序、需要范围查询lower_bound/upper_bound。三、无序关联容器哈希表 unordered_xxxunordered_set /unordered_map ✅优点平均查找、插入、删除 O (1)性能高于红黑树容器 ❌缺点元素无序不能范围查找存在哈希冲突最坏退化 O (n)哈希表扩容会 rehash迭代器失效需要类型提供哈希函数 适用只需要快速查找不要求排序。关键横向对比总结选型口诀需要随机访问、频繁遍历 →vector需要头尾快速增删、偶尔随机访问 →deque大量中间插入删除、很少遍历查找 →list谨慎固定大小数组 →array需要有序、范围查找、自动排序去重 →map / set只需要快速查找不要求顺序 →unordered_map / unordered_set高频踩坑补充vector 尽量 reserve 减少扩容list 不要用来做频繁查找查找必须遍历unordered 容器不要依赖遍历顺序map/unordered_map不要修改 key不要盲目用 list绝大多数场景 vector 性能碾压 list。