C＋＋进阶 map和set的使用

一.序列式容器和关联式容器1.序列式容器概念序列式容器中的元素按照插入顺序存储。容器会记录每个元素的位置用户可以通过下标或迭代器访问指定位置的元素。元素的位置由插入顺序决定常见序列式容器vector动态顺序表string字符顺序表等2.关联式容器关联式容器也是⽤来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是⾮线性结构两个位置有紧密的关联关系交换⼀下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。常见的关联式容器set map系列二.set的使用1.set的介绍set 是 C STL中的一种关联式容器用于存储唯一且有序的元素。2.set的特点1.元素唯一不能存储重复元素最终只会保存 10因为 set 会自动去重。2.自动排序默认按照升序排列结果 1 3 8 103.查找效率高底层是红黑树4. 不支持下标访问因为 set 不是顺序存储结构。只能通过迭代器访问三. set 的类模板1.set类的介绍set默认要求Key⽀持⼩于⽐较如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数set底层存储数据的内存是从空间配置器申请的如果需要可以⾃⼰实现内存池传给第三个参数。⼀般情况下我们都不需要传后两个模版参数。set底层是⽤红⿊树实现增删查效率是 O(logN)迭代器遍历是⾛的搜索树的中序所以是有序的2.set的构造和迭代器1.默认构造创建一个空的 set。2.区间构造利用一段区间的数据构造 set。结果 1 3 6 8发生了两件事自动排序自动去重3.拷贝构造s2中的数据1 24.set 的迭代器由于 set 底层是红黑树因此不能使用下标访问。begin()指向最小值节点。输出3end()指向最后一个元素的下一个位置。输出3 8 105.反向迭代器rbegin()指向最大值。rend()指向最小值前一个位置。输出10 8 6 3 16.为什么不能修改 set 中的数据set底层是红黑树。红黑树满足左子树 根 右子树如果允许通过迭代器修改元素会破坏红黑树的有序结构。因此set迭代器解引用后得到的是const引用不允许修改数据。四.set的增删查1.insert —— 插入插入单个元素返回值输出10第一次插入10成功第二次插入10失败set不允许重复列表插入输出1 3 6 8 10自动排序去重区间插入结果1 3 6 8 102.find —— 查找返回输出5查找失败3.count —— 统计由于 set 不允许重复返回值只有0 1输出104.erase —— 删除1.按值删除返回输出102. 按迭代器删除3. 删除区间删除 2 3 45.lower_bound作用返回 val 的第一个位置输出56.upper_bound作用返回 val 的第一个位置输出7五.multiset和set的差异1.定义对比set结果10multiset结果:10 10 102.insert 返回值不同set因为不允许重复所以需要告诉你插入是否成功。结果:10multiset允许重复。因此不存在插入失败。结果:全部成功3.count 的区别set元素唯一。所以结果:1或者0只有两种可能multiset可能有多个相同元素。输出:34.find 的区别set找到的就是唯一那个元素。multiset可能存在多个。返回第一个10的位置5.erase 的区别set删除后:空multiset按值删除删除后:空会删除所有 key。删除一个如果只想删一个结果:10 106.lower_bound 和 upper_bound对于重复值作用特别明显。数据: 1 3 3 3 5lower_bound(3)返回第一个3upper_bound(3)返回第一个大于3位置常用于统计重复元素输出:3表示有3个3六.map系列的使⽤1.map类的介绍对应2.pair类型介绍map底层的红⿊树节点中的数据使⽤pairKey, T存储键值对数据。1.定义first保存第一个数据second保存第二个数据。2.创建 pair 对象方法一:直接构造输出: 1001张三方法二:make_pair输出: 1002李四3.pair 可以存储不同类型都合法4.pair 的比较规则pair 支持比较运算符。比较顺序先比较 first如果 first 相等再比较 second3.map的构造1. 无参构造构造一个空的map存储:2. 区间构造利用一段迭代器区间构造 map。结果:3. 拷贝构造4. 初始化列表构造c11开始支持直接创建并初始化4.map的迭代器正向迭代器begin()指向最小 Key 的节点。end()指向最后一个节点的下一个位置。输出:1:C3:B8:A10:D反向迭代器rbegin()指向最大 Key。rend()指向最小 Key 前一个位置。输出:10:D8:A3:B1:C支持范围 for七. map的增删查1.insert 插入插入单个键值对输出:10map 不允许重复 Key。列表插入区间插入2.find 查找输出:2李四3.count输出: 104.erase 删除按 Key 删除结果:返回值:删除成功1删除失败0按迭代器删除删除区间删除: 1 25.lower_bound返回第一个 k 的位置6.upper_bound返回第一个 k 的位置八.operator[]这是 map 最重要的接口。1. operator[] 可以修改结果:继续修改本质2.operator[] 可以查找输出:100相当于:3.operator[] 还可以插入此时苹果 不存在map 会自动插入然后赋值4.operator[] 和 insert 的区别insert结果:第二次失败operator[]结果:因为:operator[]找到后直接修改Value九.multimap和map的差异multimap和map的使⽤基本完全类似主要区别点在于multimap⽀持关键值key冗余那么insert/find/count/erase都围绕着⽀持关键值key冗余有所差异这⾥跟set和multiset完全⼀样⽐如find时有多个key返回中序第⼀个。其次就是multimap不⽀持[]因为⽀持key冗余[]就只能⽀持插⼊了不能⽀持修改。为什么 multimap 不支持 operator[]map 支持因为Key唯一找到 Key1 后直接修改 Value。但是 multimap:如果写:修改哪一个会无法确定所以 STL 直接规定multimap 不提供 operator[]