C第十节map和set的介绍与使用
目录
C++第十节：map和set的介绍与使用
【本节要点】
- 1.关联式容器
- 2.键值对
- 3.map介绍与使用
- 4.set介绍与使用
- 5.multimap与multisedd的介绍与使用
一、关联式容器：数据管理的核心利器
关联式容器是STL中用于高效存储和检索键值对（key-value pair） 的数据结构，其底层基于 红黑树（Red-Black Tree）实现，具备以下特性：
- 有序性 ：元素按**键（key）**自动排序（默认升序）。
- 对数时间复杂度 ：插入、删除、查找操作均为 O(logN) 。
- 键的唯一性 （仅Map和Set）：每个键唯一存在，Multimap和Multiset允许重复键。
应用场景 ：
- 数据库索引（如MySQL的B+树索引）
- 配置参数映射（如INI文件解析）
- 单词频次统计
- 唯一元素集合管理
二、键值对（Key-Value Pair）
概念 键值对是关联式容器的核心单元，通过 键（Key）快速定位值（Value） ，适用于“一对一”或“一对多”映射场景。
SGI-STL中关于键值对的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};三、Map：高效键值映射
3.1 核心特性
- 唯一键 ：每个键只能对应一个值。
- 自动排序 ：元素按键升序存储（可自定义比较函数）。
3.2 map的构造
3.3 map的迭代器
3.4 map的容量与元素访问
3.5. map中元素的修改
3.6 map小结
- map中的的元素是键值对
- map中的key是唯一的，并且不能修改
- 默认按照小于的方式对key进行比较
- map中的元素如果用迭代器去遍历，可以得到一个有序的序列
- map的底层为平衡搜索树(红黑树)，查找效率比较高$O(log_2 N)$
- 支持[]操作符，operator[]中实际进行插入查找。
四、Set：唯一元素集合
4.1 核心特性
- 元素即键 ：存储不重复的元素，仅支持按值查找。
- 自动去重 ：插入重复元素无效。
4.2 set的构造
4.3 set的迭代器
4.4 set的容量
4.5 set修改操作
4.6 应用场景
- 用户ID去重
- 集合运算（如set_intersection、set_union）
五、Multimap与Multiset：支持重复键的扩展容器
| 容器 | 键是否唯一 | 值是否唯一 | 适用场景 |
| Multimap | 否 | 是 | 邮件地址分组、学生课程映射 |
| Multiset | 否 | 否 | 单词频次统计、学生成绩排名 |
| 容器 | 插入/删除 | 查找 | 键是否唯一 | 是否允许修改键 | 适用场景 |
| Map | O(logN) | O(logN) | 是 | 否 | 需要键值映射的场景 |
| Set | O(logN) | O(logN) | 是 | 否 | 唯一元素集合管理 |
| Multimap | O(logN) | O(logN) | 否 | 否 | 一对多映射（如用户-角色） |
| Multiset | O(logN) | O(logN) | 否 | 否 | 允许重复的统计场景 |
选型建议 ：
- 若需 键值映射 且 键唯一 ，优先选择Map。
- 若仅需 存储唯一元素 ，使用Set。
- 若存在 一对多关系 ，选用Multimap（如用户-邮件地址）。
六、总结
Map和Set作为基于红黑树的关联式容器，提供了平衡的时间复杂度和有序性保障，适用于需要高效查找和唯一性管理的场景。开发者需根据实际需求权衡有序性、唯一性及性能因素，灵活选择容器类型（Map vs unordered_map、Set vs Multiset），并合理使用API以避免潜在陷阱（如下标操作副作用）。深入理解其底层原理，有助于在复杂系统中设计高效的数据结构。
以上就是关于 树型结 构的关联式容器主总结 ，如果有发现问题的小伙伴，请在评论区说出来哦。 后面还会持续更新C++相关知识，感兴趣请持续关注我哦！！
