C++ 标准容器 STL

C 标准容器 STLSTL 清单1. 序列式容器容器头文件逻辑结构默认底层容器特点operator[]常用频率std::vectorvector动态数组连续内存块随机访问 O(1)尾部增删 O(1)中间插入删除 O(n)内存连续缓存友好✅ 支持随机访问 O(1)⭐⭐⭐⭐⭐ (极高)std::dequedeque双端队列分段连续数组首尾增删 O(1)支持随机访问 O(1)中间插入删除 O(n)内存非完全连续✅ 支持随机访问 O(1)⭐⭐⭐ (中等)std::listlist双向链表离散节点双向指针任意位置插入删除O(1)不支持随机访问遍历较慢内存开销大❌ 不支持非随机访问迭代器⭐⭐ (较低)std::forward_listforward_list单向链表离散节点单向指针仅支持前向遍历头部插入O(1)比list更省内存无size()方法❌ 不支持非随机访问迭代器⭐ (极低)std::arrayarray固定大小数组栈上连续内存编译期确定大小零开销抽象支持STL接口和边界检查(at)不可动态扩容✅ 支持随机访问 O(1)⭐⭐⭐⭐ (高)2. 有序关联式容器容器头文件逻辑结构默认底层容器特点operator[]常用频率std::setset有序唯一集合红黑树元素自动排序且唯一查找/插入/删除 O(log n)支持范围查询❌ 不支持无 Key-Value 结构⭐⭐⭐⭐ (高)std::multisetset有序可重复集合红黑树允许重复元素其余同 setcount() 返回重复次数❌ 不支持无 Key-Value 结构⭐⭐ (较低)std::mapmap有序键值对映射红黑树Key 唯一且自动排序Value 通过 Key 访问查找/插入 O(log n)✅ 支持按 Key 访问不存在则插入O(log n)⭐⭐⭐⭐⭐ (极高)std::multimapmap有序可重复键映射红黑树允许重复 Key需用 equal_range() 获取所有匹配项❌ 不支持Key 不唯一语义不明确⭐ (极低)3. 无序关联式容器容器头文件逻辑结构默认底层容器特点operator[]常用频率std::unordered_setunordered_set无序唯一集合哈希表平均查找/插入 O(1)最坏 O(n)元素无序需自定义哈希函数❌ 不支持无 Key-Value 结构⭐⭐⭐⭐ (高)std::unordered_multisetunordered_set无序可重复集合哈希表允许重复元素平均 O(1) 操作无序❌ 不支持无 Key-Value 结构⭐ (极低)std::unordered_mapunordered_map无序键值对映射哈希表Key 唯一平均查找 O(1)高频查找场景首选无序✅ 支持按 Key 访问不存在则插入平均 O(1)⭐⭐⭐⭐⭐ (极高)std::unordered_multimapunordered_map无序可重复键映射哈希表允许重复 Key平均 O(1)❌ 不支持Key 不唯一语义不明确⭐ (极低)4. 容器适配器容器头文件逻辑结构默认底层容器特点operator[]常用频率std::stackstack栈(LIFO)std::deque后进先出仅暴露 push/pop/top无迭代器不可遍历❌ 不支持仅顶部访问无随机访问语义⭐⭐⭐⭐ (高)std::queuequeue队列(FIFO)std::deque先进先出仅暴露 push/pop/front/back无迭代器❌ 不支持仅首尾访问无随机访问语义⭐⭐⭐⭐ (高)std::priority_queuequeue优先队列(堆)std::vector出队始终为最大/最小元素基于二叉堆实现无迭代器❌ 不支持仅顶部访问堆结构不允许随机下标访问⭐⭐⭐ (中等)5. C 23 扁平关联容器容器头文件逻辑结构默认底层容器特点operator[]常用频率std::flat_setflat_set排序唯一集合std::vector连续内存二分查找缓存友好中小数据量优于红黑树 set❌ 不支持无 Key-Value 结构⭐⭐ (新特性)std::flat_multisetflat_set排序可重复集合std::vector同上允许重复元素❌ 不支持无 Key-Value 结构⭐ (新特性)std::flat_mapflat_map排序键值对映射std::vectorpairKey-Value 分离存储或配对存储缓存命中率远高于 std::map✅ 支持按 Key 访问不存在则插入O(log n)⭐⭐ (新特性)std::flat_multimapflat_map排序可重复键映射std::vectorpair同上允许重复 Key❌ 不支持Key 不唯一语义不明确⭐ (新特性)