C STL map/set 核心知识点精要一、底层共性底层实现均采用红黑树平衡二叉搜索树特性自动排序增删查时间复杂度O(logN)属于关联式容器非线性容器默认升序排列基于 lessT中序遍历结果即为有序序列二、基础区别容器类型存储内容key 特性其他特性set仅 key唯一key 不可修改multiset仅 key可重复其余同 setmapkey-valuekey 唯一value 可重复multimapkey-valuekey 可重复无 [] 运算符三、关键特性有序性自动维护元素顺序支持自定义比较器元素唯一性set/mapkey 唯一multiset/multimapkey 可重复迭代器特性双向迭代器不支持随机访问插入/删除操作仅使被操作元素的迭代器失效不可变性set 元素和 map 的 key 均为 const修改 key 会破坏红黑树结构查找效率find(): O(logN)显著优于 vector 的 O(N)遍历四、常用接口set/multisetinsert()- 插入元素find()- 查找元素erase()- 删除元素count()- 统计出现次数lower_bound()- 返回首个≥目标的迭代器upper_bound()- 返回首个目标的迭代器map/multimapinsert()- 插入键值对operator[]- 访问/插入元素at()- 安全访问越界抛异常find()- 按键查找erase()- 删除元素count()- 统计键出现次数五、operator[] 注意事项存在时返回 value 引用不存在时自动插入默认值仅查询时建议使用 find() 避免意外插入六、multimap 无 [] 原因key 可重复导致无法确定返回哪个 value因此禁用下标运算符七、红黑树优势平衡特性保证 O(logN) 复杂度天然有序结构动态平衡适合频繁增删场景八、有序 vs 无序容器对比特性map/setunordered_map/unordered_set底层结构红黑树哈希表排序特性有序无序时间复杂度O(logN)平均 O(1)最坏 O(N)迭代器类型双向迭代器前向迭代器内存占用较小较大哈希表开销适用场景需有序/范围查询仅需快速查找九、使用场景指南去重有序 → set允重有序 → multiset键值对有序唯一 → map键值对允重 → multimap仅需快速查找 → unordered_map