C++ STL map/set 核心知识点精要

一、底层共性

• 底层实现：均采用红黑树（平衡二叉搜索树）
• 特性：
  • 自动排序
  • 增删查时间复杂度：O(logN)
  • 属于关联式容器（非线性容器）
  • 默认升序排列（基于 less<T>）
  • 中序遍历结果即为有序序列

二、基础区别

三、关键特性

1. 有序性

   • 自动维护元素顺序
   • 支持自定义比较器

2. 元素唯一性

   • set/map：key 唯一
   • multiset/multimap：key 可重复

3. 迭代器特性

   • 双向迭代器（不支持随机访问）
   • 插入/删除操作仅使被操作元素的迭代器失效

4. 不可变性

   • set 元素和 map 的 key 均为 const
   • 修改 key 会破坏红黑树结构

5. 查找效率

   • find(): O(logN)
   • 显著优于 vector 的 O(N)遍历

四、常用接口

set/multiset

• insert() - 插入元素
• find() - 查找元素
• erase() - 删除元素
• count() - 统计出现次数
• lower_bound() - 返回首个≥目标的迭代器
• upper_bound() - 返回首个>目标的迭代器

map/multimap

• insert() - 插入键值对
• operator[] - 访问/插入元素
• at() - 安全访问（越界抛异常）
• find() - 按键查找
• erase() - 删除元素
• count() - 统计键出现次数

五、operator[] 注意事项

• 存在时：返回 value 引用
• 不存在时：自动插入默认值
• 仅查询时建议使用 find() 避免意外插入

六、multimap 无 [] 原因

• key 可重复导致无法确定返回哪个 value
• 因此禁用下标运算符

七、红黑树优势

• 平衡特性保证 O(logN) 复杂度
• 天然有序结构
• 动态平衡适合频繁增删场景

八、有序 vs 无序容器对比

九、使用场景指南

• 去重+有序 → set
• 允重+有序 → multiset
• 键值对+有序唯一 → map
• 键值对+允重 → multimap
• 仅需快速查找 → unordered_map