一、引言在 C 编程里map 和 set是两个特别好用的 “智能工具箱”专门帮我们存数据、找数据、管数据比普通数组、列表方便太多而且自带两个超实用的 “隐藏技能”自动排序 自动去重。可以把它们简单理解成两种不同的 “记录本”Set 就是一个 “独一无二的有序名单”你往里面放数字、字符串都行它会自动帮你做两件事绝不重复同样的东西放两次它只留一个自动排好序放进去是乱的拿出来自动按大小 / 先后排整齐。它只存一个值适合用来做 “去重、查重、有序列表”。Map 就是一个 “带名字的有序字典”它存的是一对一对的数据名字 内容比如 “学号→姓名”“单词→解释”名字key不能重复还会自动排序想查数据直接报 “名字”瞬间就能找到对应的内容。它存键 值适合用来做 “映射、查找、对应关系”。两个工具底层都用了高效的树形结构找数据特别快数据再多也不卡顿是写程序时处理数据最常用、最省心的两个容器。两个容器的底层都是红黑树是优化版本的高效的二叉搜索树关于二叉搜索树的内容在这里二叉搜索树二、set的相关接口头文件set,性质只能存储key值不同的元素并按照指定顺序排列成树。一、构造和遍历1.构造构造分为三种首先介绍一下set的模板参数1.存储数据类型2.定义内部数据存储顺序的比较仿函数默认是排升序即每个节点“左小右大”3.空间配置器一般不用传参使用缺省值其次是构造函数的使用1.空构造例如setint a;2.c数组风格构造例如setint arr{1,2,3,4};3.迭代器区间构造将已有容器或数组中的元素赋值到set中传入参数是容器第一个元素迭代器或数组首元素地址容器最后一个元素下一个位置的迭代器或数组末尾元素下一个元素的地址4.拷贝构造利用已有的set对象来构造一个新的set对象2.迭代器和遍历使用迭代器方式的遍历默认走的是中序遍历一定是有序的。set的迭代器遍历只支持读不支持改。3.代码演示//构造升序排列的set //c数组风格构造 cout ------------set1---------------- endl; setint set1 { 1,2,3,4,5,6,7,8,9,10 }; setint::iterator it1 set1.begin(); while (it1 ! set1.end()) { cout *it1 ; it1; } cout endl;//1 2 3 4 5 6 7 8 9 10 //迭代器区间构造 cout -----------------set2-------------- endl; vectorint arr { 1,2,3,4,5,6,7,8,9,10 }; setint set2(arr.begin(), arr.end()); setint::iterator it2 set2.begin(); while (it2 ! set2.end()) { cout *it2 ; it2; } cout endl;//1 2 3 4 5 6 7 8 9 10 //构造降序排列的set cout ------------set3---------------- endl; setint, greaterint set3 { 1,2,3,4,5,6,7,8,9,10 }; setint, greaterint::iterator it3 set3.begin(); while (it3 ! set3.end()) { cout *it3 ; it3; } cout endl;//10 9 8 7 6 5 4 3 2 1 //迭代器区间构造 cout -----------------set4-------------- endl; vectorintarr2 { 1,2,3,4,5,6,7,8,9,10 }; setint, greaterint set4(arr2.begin(), arr2.end()); setint, greaterint::iterator it4 set4.begin(); // 类型匹配 while (it4 ! set4.end()) { cout *it4 ; it4; } cout endl;//10 9 8 7 6 5 4 3 2 1 //拷贝构造 cout ---------------set5---------------- endl; setint set5(set1); setint, greaterint::iterator it5 set5.begin(); // 类型匹配 while (it5 ! set5.end()) { cout *it5 ; it5; } cout endl;//1 2 3 4 5 6 7 8 9 10二、增删查插入insert1.插入一个值 返回值是pair类型pair第二个参数是一个布尔值取决于插入的成功或失败由于set只允许存储不同信息的元素所以插入失败意味着set中已有该元素返回该已有元素的迭代器作为pair第一个参数插入成功就返回新插入节点的迭代器。2.指定迭代器位置的附近插入一个元素可以认为传参的迭代器是你给编译器的一个提示编译器会根据二叉搜索树的结构插入元素并返回新插入节点的迭代器。3.插入一个迭代器区间指示的元素相当于将该区间涵盖的元素排序加去重存储到set中代码示例setint a; //插入一个值 a.insert(3); auto it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//3 //指定迭代器位置的附近插入一个元素 a.insert(it, 4); it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//3 4 //插入一段迭代器区间指示的元素 vector int v1 { 1,2,3,4,5 }; a.insert(v1.begin(), v1.end()); it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//1 2 3 4 5查找和计数find:给定值返回相应的迭代器位置如果不存在就返回set的末尾元素的下一个位置的迭代器count:给定值判断这个值是否在set中存在返回1反之返回0lower_bound :传入一个值返回中序遍历情况下第一个满足这个值节点的迭代器upper_bound :传入一个值返回中序遍历情况下第一个满足 这个值节点的迭代器equal_range:传入值返回两个参数都是指示这个值的迭代器的pair(意义不大主要是为了适配multiset)删除erase1.按迭代器位置删除搭配find使用2.按值删除返回删除元素的个数1个表示删除成功0表示set中无该元素3.删除一段区间通常搭配 lower_bound,upper_bound 使用代码示例setint s { 1,2,3,4,5,6,7,23,44,78 }; for (int i 1; i 20 ; i * 2) { auto its.find(i); if (it s.end()) cout i 不存在 endl; else cout i 存在 endl; } cout ------------------------- endl; /*1存在 2存在 4存在 8不存在 16不存在*/ //按值删除 for (int i 1; i 20; i * 2) { auto it s.erase(i); if (it 0) cout i 不存在 endl; else cout i 删除成功 endl; } /* 1删除成功 2删除成功 4删除成功 8不存在 16不存在 */ //迭代器区间插入 s.insert({ 1,2,4 });//s:1,2,3,4,5,6,7,23,44,78 auto start s.lower_bound(1);//找1的第一个位置 auto finish s.upper_bound(7);//找1的第一个位置 s.erase(start, finish);//按区间删除1-7传参区间左闭右开。 auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl;//23 44 78 //按迭代器删除 s.insert({ 1,2,3,4,5,6,7 });//s:1,2,3,4,5,6,7,23,44,78 for (int i 1; i 20; i * 2) { auto it s.find(i); if (it s.end()) { ; } else s.erase(it); } it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl;// 3 5 6 7 23 44 78 //看1是否在set中 cout s.count(1) endl;//0三、multiset相关接口multiset是set的一对孪生兄弟和set的区别就是它可以存储不同key值的元素所以大部分接口都和set相同这里介绍二者有不同之处的接口1.构造和区间插入multiset的构造和区间插入不会删除重复值。2.count与set的count相比当所给定的key值在multiset中时multiset的count返回的是这个key值相同的所有元素的个数不存在具有这个key值的元素时返回值还是0/3.find与set相比multiset之中find返回的所有迭代器都是中序遍历第一个出现那个节点所对应的迭代器4.erasemultiset的按值删除会删除所有key值为这个值的节点5.equal_range 返回值为key的这段元素的迭代器区间左闭右开构成的pairmultiset和set的差异示意代码#include iostream #include set using namespace std; // 辅助打印函数 templatetypename T void print(const T container) { for (auto val : container) { cout val ; } cout endl; } int main() { // set不允许重复 setint s; // 1. 插入重复元素会失败 cout set 测试 endl; auto ret1 s.insert(10); // 成功 auto ret2 s.insert(20); // 成功 auto ret3 s.insert(10); // 重复失败 // insert 返回 pair迭代器, 是否成功 cout 插入10是否成功 boolalpha ret3.second endl; cout set 内容; print(s); // 自动排序10 20 // 2. find返回唯一元素的迭代器 auto it s.find(10); if (it ! s.end()) cout 找到了 *it endl; // 3. count只能是 0 或 1 cout count(10) s.count(10) endl; // 4. erase(值)只删一个 s.erase(10); cout 删除10后; print(s); cout endl; // multiset允许重复 multisetint ms; cout multiset 测试 endl; ms.insert(10); ms.insert(20); ms.insert(10); // 重复也能插入成功 ms.insert(10); cout multiset 内容; print(ms); // 自动排序保留重复10 10 10 20 // 1. find返回第一个匹配元素 auto pos ms.find(10); if (pos ! ms.end()) cout 第一个10 *pos endl; // 遍历所有相同元素 cout 所有10; while (pos ! ms.end() *pos 10) { cout *pos ; pos; } cout endl; // 2. count返回实际个数可大于1 cout count(10) ms.count(10) endl; // 3. erase(值)删除所有等于该值的元素 ms.erase(10); cout erase(10) 后; print(ms); // 4. 只想删除一个用迭代器删除 ms.insert(10); ms.insert(10); cout 重新插入两个10; print(ms); auto one ms.find(10); if (one ! ms.end()) { ms.erase(one); // 只删这一个 } cout 只删除一个10后; print(ms); // 核心区别总结 /* set 与 multiset 使用时的核心区别 1. 唯一性 set 不允许重复元素插入重复会失败 multiset 允许重复元素插入总是成功。 2. insert 返回值 set 返回 pair迭代器, bool可判断是否插入成功 multiset 只返回迭代器无需判断成功与否。 3. find set 找到唯一元素 multiset 找到第一个相同元素后续要自己遍历。 4. count set 结果只能是 0 或 1 multiset 返回元素实际个数≥0。 5. erase(值) set 删除这一个值最多1个 multiset 删除所有等于该值的元素。 共同点 都自动升序排序底层都是红黑树迭代器用法一致。 */ return 0; }四、map相关接口头文件mapmap的性质存放的是键值对有两个数据key,valkey不可以重复map的每一个元素是一个pairkey,val一map的构造和遍历map的构造1.默认构造不手动调用。2.迭代器区间构造根据已有的存储数据类型为pairkeyval的容器或结构体数组构造传入指示容器首位的两个迭代器或指针注意是左闭右开。3.拷贝构造使用已有的map进行构造4.补充c结构体风格构造。和结构体数组的定义方式类似.,具体操作见代码演示.map的遍历和set一样map只可以使用迭代器进行中序遍历遍历的结果对key而言是有序的但是值得注意的是由于pairkey,val没有重载operator 所以不能对map的单个节点直接进行输入输出由于pair中key,val是公有的并且不能修改key所以输出要用pair指针-first/second pair对象.first/second代码演示//迭代器区间构造 pairstring, int p[] { {apple,1},{peach,4},{orange,6} }; mapstring, int map1(p, p 3); for (auto e : map1) { cout e.first : e.second endl; } //apple:1 //orange : 6 //peach : 4 //c结构体风格构造 mapstring, int map2 { {apple,1},{peach,4},{orange,6} }; auto it map2.begin(); while (it ! map2.end()) { cout it-first : it-second endl; it; } //apple:1 //orange : 6 //peach : 4 //拷贝构造 mapstring, int map3(map2); for (auto e : map3) { cout e.first : e.second endl; } //apple:1 //orange : 6 //peach : 4二map的增删查插入insert使用方式和set大同小异只不过把key值换成了pairkey,val类型的对象。1.插入一个pairkey,val类型的对象返回值是pair类型pair第二个参数是一个布尔值取决于插入的成功或失败由于set只允许存储不同信息的元素所以插入失败意味着set中已有该元素返回该已有元素的迭代器作为pair第一个参数插入成功就返回新插入节点的迭代器。2.指定迭代器位置的附近插入一个pairkey,val类型的对象可以认为传参的迭代器是你给编译器的一个提示编译器会根据二叉搜索树的结构插入元素并返回新插入节点的迭代器。3.插入一个迭代器区间指示的元素pairkey,val类型的对象相当于将该区间涵盖的元素排序加去重存储到set中。代码演示//插入一个pairkey,val类型的对象 mapstring, int index; index.insert({ apple,1 }); pairstring, int p1 { peach,6 }; index.insert(p1); index.insert(make_pair(orange, 3)); for (auto it : index) { cout it.first : it.second endl; } //apple: 1 //orange : 3 //peach : 6 //指定迭代器位置的附近插入一个pairkey,val类型的对象 index.insert(index.begin(), { banana,4 }); for (auto it : index) { cout it.first : it.second endl; } //apple: 1 //banana: 4 //orange : 3 //peach : 6 index.clear();//容器清空 index.insert({ {apple,1},{peach,4},{orange,6} }); for (auto it : index) { cout it.first : it.second endl; }; //apple: 1 //orange : 6 //peach : 4 pairstring, int p[] { {pineapple,1},{watermelon,4},{grape,6} }; index.insert(p, p 3); for (auto it : index) { cout it.first : it.second endl; }; //apple: 1 //grape : 6 //orange : 6 //peach : 4 //pineapple : 1 //watermelon : 4查找和计数find给定key值返回相应的迭代器位置如果不存在就返回set的末尾元素的下一个位置的迭代器count:给定值判断这个值是否在set中存在返回1反之返回0lower_bound :传入一个值返回中序遍历情况下第一个满足这个值节点的迭代器upper_bound :传入一个值返回中序遍历情况下第一个满足 这个值节点的迭代器equal_range:传入值返回两个参数都是指示这个值的迭代器的pair(意义不大主要是为了适配multimap)删除erase和set几乎一模一样1.按迭代器位置删除搭配find使用2.按值删除返回删除元素的个数1个表示删除成功0表示set中无该元素3.删除一段区间通常搭配 lower_bound,upper_bound 使用由于和set操作别无二异因此不再做代码展示触类旁通即可三、operator[ ]在pairkey,val中key充当索引关键字的作用在map中存储具有唯一性可以根据key来查找val,就好比数组的下标一样。所以实现【】的重载可以和数组的【】作类比得出它在map中的使用原理1.map中无key,调用插入一个val为val的默认构造值的元素节点返回值pair中第一个元素为当前元素的迭代器以方便实现复制和修改2.map中有key,还是调用返回值pair中第一个元素为当前元素的迭代器以方便实现复制和修改。代码示例mapstring, int index; index.insert({ apple,5 }); index[apple] 13; index[peach] 23; index[banana] 15; for (auto e : index) { cout e.first : e.second endl; } //apple:13 //banana : 15 //peach : 23五、multimap相关接口multimap是map的一对孪生兄弟和map的区别就是它可以存储不同key值的元素所以大部分接口都和map相同这里介绍二者有不同之处的接口1.构造和区间插入multiset的构造和区间插入不会删除key重复的值。2.count与set的count相比当所给定的key值在multimap中时multimap的count返回的是这个key值相同的所有元素的个数不存在具有这个key值的元素时返回值还是0.3.find与map相比multimap之中find返回的所有迭代器都是中序遍历第一个出现那个节点所对应的迭代器4.erasemultimap的按值删除会删除所有key值为这个值的节点5.equal_range 返回值为key的这段元素的迭代器区间左闭右开构成的pair6.[]运算符map支持[]访问 / 修改multimap不支持[]因为 key 不唯一不知道取哪个代码示例#include iostream #include map // multimap 包含在这里 using namespace std; void testMultimap() { // 1. 创建 multimapkey 可重复 multimapstring, int mm; // 2. 插入允许 key 重复multimap 最核心特点 mm.insert({ apple, 1 }); mm.insert({ apple, 2 }); // 重复 key插入成功 mm.insert({ apple, 3 }); mm.insert({ banana, 10 }); mm.insert({ orange, 20 }); cout 插入重复 key 后 endl; for (auto e : mm) { cout e.first : e.second endl; } // 结果apple 出现 3 次 // 3. multimap 不支持 [] 操作 // mm[apple]; // ❌ 报错 // 4. find找到第一个匹配的 key cout \n find 查找 apple返回第一个 endl; auto pos mm.find(apple); if (pos ! mm.end()) { cout pos-first : pos-second endl; } // 5. 遍历所有相同 key 的元素multimap 特有 cout \n 遍历所有 apple endl; while (pos ! mm.end() pos-first apple) { cout pos-first : pos-second endl; pos; } // 6. count统计 key 出现次数 cout \napple 出现次数 mm.count(apple) endl; // 7. erase(key)删除所有同 key 的元素 mm.erase(apple); cout \n erase(\apple\) 后 endl; for (auto e : mm) { cout e.first : e.second endl; } // 8. 清空 mm.clear(); } int main() { testMultimap(); return 0; }
二叉搜索双壁——map和set
一、引言在 C 编程里map 和 set是两个特别好用的 “智能工具箱”专门帮我们存数据、找数据、管数据比普通数组、列表方便太多而且自带两个超实用的 “隐藏技能”自动排序 自动去重。可以把它们简单理解成两种不同的 “记录本”Set 就是一个 “独一无二的有序名单”你往里面放数字、字符串都行它会自动帮你做两件事绝不重复同样的东西放两次它只留一个自动排好序放进去是乱的拿出来自动按大小 / 先后排整齐。它只存一个值适合用来做 “去重、查重、有序列表”。Map 就是一个 “带名字的有序字典”它存的是一对一对的数据名字 内容比如 “学号→姓名”“单词→解释”名字key不能重复还会自动排序想查数据直接报 “名字”瞬间就能找到对应的内容。它存键 值适合用来做 “映射、查找、对应关系”。两个工具底层都用了高效的树形结构找数据特别快数据再多也不卡顿是写程序时处理数据最常用、最省心的两个容器。两个容器的底层都是红黑树是优化版本的高效的二叉搜索树关于二叉搜索树的内容在这里二叉搜索树二、set的相关接口头文件set,性质只能存储key值不同的元素并按照指定顺序排列成树。一、构造和遍历1.构造构造分为三种首先介绍一下set的模板参数1.存储数据类型2.定义内部数据存储顺序的比较仿函数默认是排升序即每个节点“左小右大”3.空间配置器一般不用传参使用缺省值其次是构造函数的使用1.空构造例如setint a;2.c数组风格构造例如setint arr{1,2,3,4};3.迭代器区间构造将已有容器或数组中的元素赋值到set中传入参数是容器第一个元素迭代器或数组首元素地址容器最后一个元素下一个位置的迭代器或数组末尾元素下一个元素的地址4.拷贝构造利用已有的set对象来构造一个新的set对象2.迭代器和遍历使用迭代器方式的遍历默认走的是中序遍历一定是有序的。set的迭代器遍历只支持读不支持改。3.代码演示//构造升序排列的set //c数组风格构造 cout ------------set1---------------- endl; setint set1 { 1,2,3,4,5,6,7,8,9,10 }; setint::iterator it1 set1.begin(); while (it1 ! set1.end()) { cout *it1 ; it1; } cout endl;//1 2 3 4 5 6 7 8 9 10 //迭代器区间构造 cout -----------------set2-------------- endl; vectorint arr { 1,2,3,4,5,6,7,8,9,10 }; setint set2(arr.begin(), arr.end()); setint::iterator it2 set2.begin(); while (it2 ! set2.end()) { cout *it2 ; it2; } cout endl;//1 2 3 4 5 6 7 8 9 10 //构造降序排列的set cout ------------set3---------------- endl; setint, greaterint set3 { 1,2,3,4,5,6,7,8,9,10 }; setint, greaterint::iterator it3 set3.begin(); while (it3 ! set3.end()) { cout *it3 ; it3; } cout endl;//10 9 8 7 6 5 4 3 2 1 //迭代器区间构造 cout -----------------set4-------------- endl; vectorintarr2 { 1,2,3,4,5,6,7,8,9,10 }; setint, greaterint set4(arr2.begin(), arr2.end()); setint, greaterint::iterator it4 set4.begin(); // 类型匹配 while (it4 ! set4.end()) { cout *it4 ; it4; } cout endl;//10 9 8 7 6 5 4 3 2 1 //拷贝构造 cout ---------------set5---------------- endl; setint set5(set1); setint, greaterint::iterator it5 set5.begin(); // 类型匹配 while (it5 ! set5.end()) { cout *it5 ; it5; } cout endl;//1 2 3 4 5 6 7 8 9 10二、增删查插入insert1.插入一个值 返回值是pair类型pair第二个参数是一个布尔值取决于插入的成功或失败由于set只允许存储不同信息的元素所以插入失败意味着set中已有该元素返回该已有元素的迭代器作为pair第一个参数插入成功就返回新插入节点的迭代器。2.指定迭代器位置的附近插入一个元素可以认为传参的迭代器是你给编译器的一个提示编译器会根据二叉搜索树的结构插入元素并返回新插入节点的迭代器。3.插入一个迭代器区间指示的元素相当于将该区间涵盖的元素排序加去重存储到set中代码示例setint a; //插入一个值 a.insert(3); auto it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//3 //指定迭代器位置的附近插入一个元素 a.insert(it, 4); it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//3 4 //插入一段迭代器区间指示的元素 vector int v1 { 1,2,3,4,5 }; a.insert(v1.begin(), v1.end()); it a.begin(); while (it ! a.end()) { cout *it ; it; } cout endl;//1 2 3 4 5查找和计数find:给定值返回相应的迭代器位置如果不存在就返回set的末尾元素的下一个位置的迭代器count:给定值判断这个值是否在set中存在返回1反之返回0lower_bound :传入一个值返回中序遍历情况下第一个满足这个值节点的迭代器upper_bound :传入一个值返回中序遍历情况下第一个满足 这个值节点的迭代器equal_range:传入值返回两个参数都是指示这个值的迭代器的pair(意义不大主要是为了适配multiset)删除erase1.按迭代器位置删除搭配find使用2.按值删除返回删除元素的个数1个表示删除成功0表示set中无该元素3.删除一段区间通常搭配 lower_bound,upper_bound 使用代码示例setint s { 1,2,3,4,5,6,7,23,44,78 }; for (int i 1; i 20 ; i * 2) { auto its.find(i); if (it s.end()) cout i 不存在 endl; else cout i 存在 endl; } cout ------------------------- endl; /*1存在 2存在 4存在 8不存在 16不存在*/ //按值删除 for (int i 1; i 20; i * 2) { auto it s.erase(i); if (it 0) cout i 不存在 endl; else cout i 删除成功 endl; } /* 1删除成功 2删除成功 4删除成功 8不存在 16不存在 */ //迭代器区间插入 s.insert({ 1,2,4 });//s:1,2,3,4,5,6,7,23,44,78 auto start s.lower_bound(1);//找1的第一个位置 auto finish s.upper_bound(7);//找1的第一个位置 s.erase(start, finish);//按区间删除1-7传参区间左闭右开。 auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl;//23 44 78 //按迭代器删除 s.insert({ 1,2,3,4,5,6,7 });//s:1,2,3,4,5,6,7,23,44,78 for (int i 1; i 20; i * 2) { auto it s.find(i); if (it s.end()) { ; } else s.erase(it); } it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl;// 3 5 6 7 23 44 78 //看1是否在set中 cout s.count(1) endl;//0三、multiset相关接口multiset是set的一对孪生兄弟和set的区别就是它可以存储不同key值的元素所以大部分接口都和set相同这里介绍二者有不同之处的接口1.构造和区间插入multiset的构造和区间插入不会删除重复值。2.count与set的count相比当所给定的key值在multiset中时multiset的count返回的是这个key值相同的所有元素的个数不存在具有这个key值的元素时返回值还是0/3.find与set相比multiset之中find返回的所有迭代器都是中序遍历第一个出现那个节点所对应的迭代器4.erasemultiset的按值删除会删除所有key值为这个值的节点5.equal_range 返回值为key的这段元素的迭代器区间左闭右开构成的pairmultiset和set的差异示意代码#include iostream #include set using namespace std; // 辅助打印函数 templatetypename T void print(const T container) { for (auto val : container) { cout val ; } cout endl; } int main() { // set不允许重复 setint s; // 1. 插入重复元素会失败 cout set 测试 endl; auto ret1 s.insert(10); // 成功 auto ret2 s.insert(20); // 成功 auto ret3 s.insert(10); // 重复失败 // insert 返回 pair迭代器, 是否成功 cout 插入10是否成功 boolalpha ret3.second endl; cout set 内容; print(s); // 自动排序10 20 // 2. find返回唯一元素的迭代器 auto it s.find(10); if (it ! s.end()) cout 找到了 *it endl; // 3. count只能是 0 或 1 cout count(10) s.count(10) endl; // 4. erase(值)只删一个 s.erase(10); cout 删除10后; print(s); cout endl; // multiset允许重复 multisetint ms; cout multiset 测试 endl; ms.insert(10); ms.insert(20); ms.insert(10); // 重复也能插入成功 ms.insert(10); cout multiset 内容; print(ms); // 自动排序保留重复10 10 10 20 // 1. find返回第一个匹配元素 auto pos ms.find(10); if (pos ! ms.end()) cout 第一个10 *pos endl; // 遍历所有相同元素 cout 所有10; while (pos ! ms.end() *pos 10) { cout *pos ; pos; } cout endl; // 2. count返回实际个数可大于1 cout count(10) ms.count(10) endl; // 3. erase(值)删除所有等于该值的元素 ms.erase(10); cout erase(10) 后; print(ms); // 4. 只想删除一个用迭代器删除 ms.insert(10); ms.insert(10); cout 重新插入两个10; print(ms); auto one ms.find(10); if (one ! ms.end()) { ms.erase(one); // 只删这一个 } cout 只删除一个10后; print(ms); // 核心区别总结 /* set 与 multiset 使用时的核心区别 1. 唯一性 set 不允许重复元素插入重复会失败 multiset 允许重复元素插入总是成功。 2. insert 返回值 set 返回 pair迭代器, bool可判断是否插入成功 multiset 只返回迭代器无需判断成功与否。 3. find set 找到唯一元素 multiset 找到第一个相同元素后续要自己遍历。 4. count set 结果只能是 0 或 1 multiset 返回元素实际个数≥0。 5. erase(值) set 删除这一个值最多1个 multiset 删除所有等于该值的元素。 共同点 都自动升序排序底层都是红黑树迭代器用法一致。 */ return 0; }四、map相关接口头文件mapmap的性质存放的是键值对有两个数据key,valkey不可以重复map的每一个元素是一个pairkey,val一map的构造和遍历map的构造1.默认构造不手动调用。2.迭代器区间构造根据已有的存储数据类型为pairkeyval的容器或结构体数组构造传入指示容器首位的两个迭代器或指针注意是左闭右开。3.拷贝构造使用已有的map进行构造4.补充c结构体风格构造。和结构体数组的定义方式类似.,具体操作见代码演示.map的遍历和set一样map只可以使用迭代器进行中序遍历遍历的结果对key而言是有序的但是值得注意的是由于pairkey,val没有重载operator 所以不能对map的单个节点直接进行输入输出由于pair中key,val是公有的并且不能修改key所以输出要用pair指针-first/second pair对象.first/second代码演示//迭代器区间构造 pairstring, int p[] { {apple,1},{peach,4},{orange,6} }; mapstring, int map1(p, p 3); for (auto e : map1) { cout e.first : e.second endl; } //apple:1 //orange : 6 //peach : 4 //c结构体风格构造 mapstring, int map2 { {apple,1},{peach,4},{orange,6} }; auto it map2.begin(); while (it ! map2.end()) { cout it-first : it-second endl; it; } //apple:1 //orange : 6 //peach : 4 //拷贝构造 mapstring, int map3(map2); for (auto e : map3) { cout e.first : e.second endl; } //apple:1 //orange : 6 //peach : 4二map的增删查插入insert使用方式和set大同小异只不过把key值换成了pairkey,val类型的对象。1.插入一个pairkey,val类型的对象返回值是pair类型pair第二个参数是一个布尔值取决于插入的成功或失败由于set只允许存储不同信息的元素所以插入失败意味着set中已有该元素返回该已有元素的迭代器作为pair第一个参数插入成功就返回新插入节点的迭代器。2.指定迭代器位置的附近插入一个pairkey,val类型的对象可以认为传参的迭代器是你给编译器的一个提示编译器会根据二叉搜索树的结构插入元素并返回新插入节点的迭代器。3.插入一个迭代器区间指示的元素pairkey,val类型的对象相当于将该区间涵盖的元素排序加去重存储到set中。代码演示//插入一个pairkey,val类型的对象 mapstring, int index; index.insert({ apple,1 }); pairstring, int p1 { peach,6 }; index.insert(p1); index.insert(make_pair(orange, 3)); for (auto it : index) { cout it.first : it.second endl; } //apple: 1 //orange : 3 //peach : 6 //指定迭代器位置的附近插入一个pairkey,val类型的对象 index.insert(index.begin(), { banana,4 }); for (auto it : index) { cout it.first : it.second endl; } //apple: 1 //banana: 4 //orange : 3 //peach : 6 index.clear();//容器清空 index.insert({ {apple,1},{peach,4},{orange,6} }); for (auto it : index) { cout it.first : it.second endl; }; //apple: 1 //orange : 6 //peach : 4 pairstring, int p[] { {pineapple,1},{watermelon,4},{grape,6} }; index.insert(p, p 3); for (auto it : index) { cout it.first : it.second endl; }; //apple: 1 //grape : 6 //orange : 6 //peach : 4 //pineapple : 1 //watermelon : 4查找和计数find给定key值返回相应的迭代器位置如果不存在就返回set的末尾元素的下一个位置的迭代器count:给定值判断这个值是否在set中存在返回1反之返回0lower_bound :传入一个值返回中序遍历情况下第一个满足这个值节点的迭代器upper_bound :传入一个值返回中序遍历情况下第一个满足 这个值节点的迭代器equal_range:传入值返回两个参数都是指示这个值的迭代器的pair(意义不大主要是为了适配multimap)删除erase和set几乎一模一样1.按迭代器位置删除搭配find使用2.按值删除返回删除元素的个数1个表示删除成功0表示set中无该元素3.删除一段区间通常搭配 lower_bound,upper_bound 使用由于和set操作别无二异因此不再做代码展示触类旁通即可三、operator[ ]在pairkey,val中key充当索引关键字的作用在map中存储具有唯一性可以根据key来查找val,就好比数组的下标一样。所以实现【】的重载可以和数组的【】作类比得出它在map中的使用原理1.map中无key,调用插入一个val为val的默认构造值的元素节点返回值pair中第一个元素为当前元素的迭代器以方便实现复制和修改2.map中有key,还是调用返回值pair中第一个元素为当前元素的迭代器以方便实现复制和修改。代码示例mapstring, int index; index.insert({ apple,5 }); index[apple] 13; index[peach] 23; index[banana] 15; for (auto e : index) { cout e.first : e.second endl; } //apple:13 //banana : 15 //peach : 23五、multimap相关接口multimap是map的一对孪生兄弟和map的区别就是它可以存储不同key值的元素所以大部分接口都和map相同这里介绍二者有不同之处的接口1.构造和区间插入multiset的构造和区间插入不会删除key重复的值。2.count与set的count相比当所给定的key值在multimap中时multimap的count返回的是这个key值相同的所有元素的个数不存在具有这个key值的元素时返回值还是0.3.find与map相比multimap之中find返回的所有迭代器都是中序遍历第一个出现那个节点所对应的迭代器4.erasemultimap的按值删除会删除所有key值为这个值的节点5.equal_range 返回值为key的这段元素的迭代器区间左闭右开构成的pair6.[]运算符map支持[]访问 / 修改multimap不支持[]因为 key 不唯一不知道取哪个代码示例#include iostream #include map // multimap 包含在这里 using namespace std; void testMultimap() { // 1. 创建 multimapkey 可重复 multimapstring, int mm; // 2. 插入允许 key 重复multimap 最核心特点 mm.insert({ apple, 1 }); mm.insert({ apple, 2 }); // 重复 key插入成功 mm.insert({ apple, 3 }); mm.insert({ banana, 10 }); mm.insert({ orange, 20 }); cout 插入重复 key 后 endl; for (auto e : mm) { cout e.first : e.second endl; } // 结果apple 出现 3 次 // 3. multimap 不支持 [] 操作 // mm[apple]; // ❌ 报错 // 4. find找到第一个匹配的 key cout \n find 查找 apple返回第一个 endl; auto pos mm.find(apple); if (pos ! mm.end()) { cout pos-first : pos-second endl; } // 5. 遍历所有相同 key 的元素multimap 特有 cout \n 遍历所有 apple endl; while (pos ! mm.end() pos-first apple) { cout pos-first : pos-second endl; pos; } // 6. count统计 key 出现次数 cout \napple 出现次数 mm.count(apple) endl; // 7. erase(key)删除所有同 key 的元素 mm.erase(apple); cout \n erase(\apple\) 后 endl; for (auto e : mm) { cout e.first : e.second endl; } // 8. 清空 mm.clear(); } int main() { testMultimap(); return 0; }
