本文是 C 系列教程的第 12 篇。上一篇讲解了序列容器本篇讲解关联容器与无序容器set/multiset、map/multimap红黑树实现、unordered_set/unordered_map哈希表实现、自定义比较器与哈希函数。一、关联容器概览1.1 两类关联容器类别实现查找复杂度顺序关联容器set/map红黑树O(log n)有序无序容器unordered_*哈希表O(1) 平均无序1.2 六种关联容器容器键唯一键值对有序set是否是multiset否否是map是是是multimap否是是unordered_set是否否unordered_map是是否二、set 集合2.1 set 基本操作set 存储唯一且有序的元素自动去重#includeiostream#includesetusingnamespacestd;intmain(){setints;// 插入自动排序去重s.insert(5);s.insert(3);s.insert(8);s.insert(3);// 重复不插入s.insert(1);// 遍历有序for(intx:s)coutx ;coutendl;// 1 3 5 8// 查找autoits.find(5);if(it!s.end())cout找到 5endl;// 计数set 里只能是 0 或 1cout3 的数量: s.count(3)endl;// 1cout9 的数量: s.count(9)endl;// 0// 删除s.erase(5);coutsize s.size()endl;// 3// 下界上界autolbs.lower_bound(3);// 3 的第一个autoubs.upper_bound(3);// 3 的第一个coutlower_bound(3) *lbendl;// 3coutupper_bound(3) *ubendl;// 8return0;}2.2 multiset 允许重复#includeiostream#includesetusingnamespacestd;intmain(){multisetintms;ms.insert(3);ms.insert(1);ms.insert(3);// 允许重复ms.insert(2);ms.insert(3);cout3 的数量: ms.count(3)endl;// 3// 删除所有 3ms.erase(3);cout删除后 size ms.size()endl;// 2// 只删除一个ms.insert(3);ms.insert(3);autoitms.find(3);if(it!ms.end())ms.erase(it);// 只删一个cout3 的数量: ms.count(3)endl;// 1return0;}2.3 set 实战去重排序#includeiostream#includesetusingnamespacestd;intmain(){intnumbers[]{5,2,8,2,9,1,5,8};// set 自动去重 排序setintuniqueSorted(numbers,numbers8);cout去重排序后: ;for(intx:uniqueSorted)coutx ;coutendl;// 1 2 5 8 9// 自定义排序降序setint,greaterintdesc(numbers,numbers8);cout降序: ;for(intx:desc)coutx ;coutendl;// 9 8 5 2 1return0;}三、map 映射3.1 map 基本操作map 存储键值对按键自动排序#includeiostream#includemap#includestringusingnamespacestd;intmain(){mapstring,intscores;// 插入scores[张三]88;// 方式一下标scores[李四]92;scores.insert({王五,76});// 方式二insert// 访问cout张三: scores[张三]endl;// 88coutsize scores.size()endl;// 3// 遍历按键排序for(constautokv:scores){coutkv.first: kv.secondendl;}// 查找autoitscores.find(李四);if(it!scores.end()){cout找到 it-first it-secondendl;}// 判断键是否存在注意下标会创建if(scores.count(赵六)0){cout赵六不存在endl;}// scores[赵六]; // 危险这会插入一个默认值// 删除scores.erase(王五);return0;}3.2 map 的 [] 陷阱#includeiostream#includemap#includestringusingnamespacestd;intmain(){mapstring,intscores;// [] 不存在时自动插入默认值cout赵六: scores[赵六]endl;// 0且已插入coutsize scores.size()endl;// 1// 正确判断存在性用 find 或 countmapstring,intm{{a,1}};if(m.find(b)m.end()){coutb 不存在用 find 判断endl;}return0;}3.3 multimap 一对多#includeiostream#includemap#includestringusingnamespacestd;intmain(){// 一个键对应多个值multimapstring,stringcourses;courses.insert({张三,C});courses.insert({张三,Python});courses.insert({李四,Java});// 统计张三的课程数cout张三的课程数: courses.count(张三)endl;// 2// 遍历张三的所有课程autorangecourses.equal_range(张三);for(autoitrange.first;it!range.second;it){coutit-second ;}coutendl;// C Pythonreturn0;}四、unordered_set 与 unordered_map4.1 哈希表特性unordered 容器用哈希表实现查找 O(1)平均但无序#includeiostream#includeunordered_map#includestringusingnamespacestd;intmain(){unordered_mapstring,intumap;// 插入umap[apple]3;umap[banana]5;umap[cherry]2;// 查找 O(1)autoitumap.find(banana);if(it!umap.end()){coutbanana: it-secondendl;// 5}// 遍历无序for(constautokv:umap){coutkv.first: kv.secondendl;}return0;}4.2 map vs unordered_map维度mapunordered_map实现红黑树哈希表查找O(log n)O(1) 平均顺序有序无序内存较小较大适用需要有序遍历追求查找速度4.3 词频统计实战#includeiostream#includeunordered_map#includesstream#includestringusingnamespacestd;intmain(){string textthe quick brown fox jumps over the lazy dog the fox;unordered_mapstring,intfreq;stringstreamss(text);string word;// 统计每个单词出现次数while(ssword){freq[word];}// 输出词频for(constautokv:freq){coutkv.first: kv.secondendl;}// 查询cout\the\ 出现次数: freq[the]endl;// 3return0;}五、自定义比较器与哈希5.1 set/map 自定义排序#includeiostream#includeset#includestringusingnamespacestd;structPerson{string name;intage;};// 自定义比较器按年龄排序structCompareByAge{booloperator()(constPersona,constPersonb)const{returna.ageb.age;}};intmain(){setPerson,CompareByAgepeople;people.insert({张三,30});people.insert({李四,25});people.insert({王五,35});// 按年龄升序遍历for(constautop:people){coutp.name p.age岁endl;}return0;}5.2 unordered_map 自定义哈希#includeiostream#includeunordered_map#includestringusingnamespacestd;structPoint{intx,y;// 必须实现 运算符booloperator(constPointother)const{returnxother.xyother.y;}};// 自定义哈希函数structPointHash{size_toperator()(constPointp)const{returnhashint()(p.x)^(hashint()(p.y)1);}};intmain(){unordered_mapPoint,string,PointHashpoints;points[{1,2}]A;points[{3,4}]B;points[{1,2}]C;// 覆盖cout({1,2}) points[{1,2}]endl;// Ccout({3,4}) points[{3,4}]endl;// Breturn0;}六、实战成绩管理系统综合本篇知识实现基于 map 的成绩管理#includeiostream#includemap#includeunordered_map#includestringusingnamespacestd;classScoreSystem{private:mapstring,intscores;// 有序用于排名展示unordered_mapstring,stringclasses;// 快速查找班级public:voidaddStudent(conststringname,conststringcls,intscore){scores[name]score;classes[name]cls;}voidshowAll()const{cout 成绩表按姓名排序 endl;for(constautokv:scores){coutkv.first classes.at(kv.first)班 kv.second分endl;}}voidshowTop(intn3)const{cout 前 n 名 endl;// 用 multiset 按分数排序multimapint,string,greaterintranking;for(constautokv:scores){ranking.insert({kv.second,kv.first});}intcount0;for(constautokv:ranking){if(countn)break;coutkv.second kv.first分endl;}}voidquery(conststringname)const{autoitscores.find(name);if(it!scores.end()){coutname classes.at(name)班 it-second分endl;}else{coutname 不存在endl;}}};intmain(){ScoreSystem sys;sys.addStudent(张三,三,88);sys.addStudent(李四,一,95);sys.addStudent(王五,二,76);sys.addStudent(赵六,三,91);sys.showAll();sys.showTop(3);sys.query(李四);return0;}总结本篇讲解了关联容器set/multiset、map/multimap与无序容器unordered_set/unordered_map的差异、map 的 [] 陷阱、自定义比较器与哈希函数并用成绩管理系统串联实战。重点掌握set/map 的有序特性、unordered 容器的 O(1) 查找、count vs find 判断存在性、自定义哈希的写法。下一篇将讲解迭代器与算法库sort/find/transform/accumulate 等敬请期待
本文是 C 系列教程的第 12 篇。上一篇讲解了序列容器本篇讲解关联容器与无序容器set/multiset、map/multimap红黑树实现、unordered_set/unordered_map哈希表实现、自定义比较器与哈希函数。一、关联容器概览1.1 两类关联容器类别实现查找复杂度顺序关联容器set/map红黑树O(log n)有序无序容器unordered_*哈希表O(1) 平均无序1.2 六种关联容器容器键唯一键值对有序set是否是multiset否否是map是是是multimap否是是unordered_set是否否unordered_map是是否二、set 集合2.1 set 基本操作set 存储唯一且有序的元素自动去重#includeiostream#includesetusingnamespacestd;intmain(){setints;// 插入自动排序去重s.insert(5);s.insert(3);s.insert(8);s.insert(3);// 重复不插入s.insert(1);// 遍历有序for(intx:s)coutx ;coutendl;// 1 3 5 8// 查找autoits.find(5);if(it!s.end())cout找到 5endl;// 计数set 里只能是 0 或 1cout3 的数量: s.count(3)endl;// 1cout9 的数量: s.count(9)endl;// 0// 删除s.erase(5);coutsize s.size()endl;// 3// 下界上界autolbs.lower_bound(3);// 3 的第一个autoubs.upper_bound(3);// 3 的第一个coutlower_bound(3) *lbendl;// 3coutupper_bound(3) *ubendl;// 8return0;}2.2 multiset 允许重复#includeiostream#includesetusingnamespacestd;intmain(){multisetintms;ms.insert(3);ms.insert(1);ms.insert(3);// 允许重复ms.insert(2);ms.insert(3);cout3 的数量: ms.count(3)endl;// 3// 删除所有 3ms.erase(3);cout删除后 size ms.size()endl;// 2// 只删除一个ms.insert(3);ms.insert(3);autoitms.find(3);if(it!ms.end())ms.erase(it);// 只删一个cout3 的数量: ms.count(3)endl;// 1return0;}2.3 set 实战去重排序#includeiostream#includesetusingnamespacestd;intmain(){intnumbers[]{5,2,8,2,9,1,5,8};// set 自动去重 排序setintuniqueSorted(numbers,numbers8);cout去重排序后: ;for(intx:uniqueSorted)coutx ;coutendl;// 1 2 5 8 9// 自定义排序降序setint,greaterintdesc(numbers,numbers8);cout降序: ;for(intx:desc)coutx ;coutendl;// 9 8 5 2 1return0;}三、map 映射3.1 map 基本操作map 存储键值对按键自动排序#includeiostream#includemap#includestringusingnamespacestd;intmain(){mapstring,intscores;// 插入scores[张三]88;// 方式一下标scores[李四]92;scores.insert({王五,76});// 方式二insert// 访问cout张三: scores[张三]endl;// 88coutsize scores.size()endl;// 3// 遍历按键排序for(constautokv:scores){coutkv.first: kv.secondendl;}// 查找autoitscores.find(李四);if(it!scores.end()){cout找到 it-first it-secondendl;}// 判断键是否存在注意下标会创建if(scores.count(赵六)0){cout赵六不存在endl;}// scores[赵六]; // 危险这会插入一个默认值// 删除scores.erase(王五);return0;}3.2 map 的 [] 陷阱#includeiostream#includemap#includestringusingnamespacestd;intmain(){mapstring,intscores;// [] 不存在时自动插入默认值cout赵六: scores[赵六]endl;// 0且已插入coutsize scores.size()endl;// 1// 正确判断存在性用 find 或 countmapstring,intm{{a,1}};if(m.find(b)m.end()){coutb 不存在用 find 判断endl;}return0;}3.3 multimap 一对多#includeiostream#includemap#includestringusingnamespacestd;intmain(){// 一个键对应多个值multimapstring,stringcourses;courses.insert({张三,C});courses.insert({张三,Python});courses.insert({李四,Java});// 统计张三的课程数cout张三的课程数: courses.count(张三)endl;// 2// 遍历张三的所有课程autorangecourses.equal_range(张三);for(autoitrange.first;it!range.second;it){coutit-second ;}coutendl;// C Pythonreturn0;}四、unordered_set 与 unordered_map4.1 哈希表特性unordered 容器用哈希表实现查找 O(1)平均但无序#includeiostream#includeunordered_map#includestringusingnamespacestd;intmain(){unordered_mapstring,intumap;// 插入umap[apple]3;umap[banana]5;umap[cherry]2;// 查找 O(1)autoitumap.find(banana);if(it!umap.end()){coutbanana: it-secondendl;// 5}// 遍历无序for(constautokv:umap){coutkv.first: kv.secondendl;}return0;}4.2 map vs unordered_map维度mapunordered_map实现红黑树哈希表查找O(log n)O(1) 平均顺序有序无序内存较小较大适用需要有序遍历追求查找速度4.3 词频统计实战#includeiostream#includeunordered_map#includesstream#includestringusingnamespacestd;intmain(){string textthe quick brown fox jumps over the lazy dog the fox;unordered_mapstring,intfreq;stringstreamss(text);string word;// 统计每个单词出现次数while(ssword){freq[word];}// 输出词频for(constautokv:freq){coutkv.first: kv.secondendl;}// 查询cout\the\ 出现次数: freq[the]endl;// 3return0;}五、自定义比较器与哈希5.1 set/map 自定义排序#includeiostream#includeset#includestringusingnamespacestd;structPerson{string name;intage;};// 自定义比较器按年龄排序structCompareByAge{booloperator()(constPersona,constPersonb)const{returna.ageb.age;}};intmain(){setPerson,CompareByAgepeople;people.insert({张三,30});people.insert({李四,25});people.insert({王五,35});// 按年龄升序遍历for(constautop:people){coutp.name p.age岁endl;}return0;}5.2 unordered_map 自定义哈希#includeiostream#includeunordered_map#includestringusingnamespacestd;structPoint{intx,y;// 必须实现 运算符booloperator(constPointother)const{returnxother.xyother.y;}};// 自定义哈希函数structPointHash{size_toperator()(constPointp)const{returnhashint()(p.x)^(hashint()(p.y)1);}};intmain(){unordered_mapPoint,string,PointHashpoints;points[{1,2}]A;points[{3,4}]B;points[{1,2}]C;// 覆盖cout({1,2}) points[{1,2}]endl;// Ccout({3,4}) points[{3,4}]endl;// Breturn0;}六、实战成绩管理系统综合本篇知识实现基于 map 的成绩管理#includeiostream#includemap#includeunordered_map#includestringusingnamespacestd;classScoreSystem{private:mapstring,intscores;// 有序用于排名展示unordered_mapstring,stringclasses;// 快速查找班级public:voidaddStudent(conststringname,conststringcls,intscore){scores[name]score;classes[name]cls;}voidshowAll()const{cout 成绩表按姓名排序 endl;for(constautokv:scores){coutkv.first classes.at(kv.first)班 kv.second分endl;}}voidshowTop(intn3)const{cout 前 n 名 endl;// 用 multiset 按分数排序multimapint,string,greaterintranking;for(constautokv:scores){ranking.insert({kv.second,kv.first});}intcount0;for(constautokv:ranking){if(countn)break;coutkv.second kv.first分endl;}}voidquery(conststringname)const{autoitscores.find(name);if(it!scores.end()){coutname classes.at(name)班 it-second分endl;}else{coutname 不存在endl;}}};intmain(){ScoreSystem sys;sys.addStudent(张三,三,88);sys.addStudent(李四,一,95);sys.addStudent(王五,二,76);sys.addStudent(赵六,三,91);sys.showAll();sys.showTop(3);sys.query(李四);return0;}总结本篇讲解了关联容器set/multiset、map/multimap与无序容器unordered_set/unordered_map的差异、map 的 [] 陷阱、自定义比较器与哈希函数并用成绩管理系统串联实战。重点掌握set/map 的有序特性、unordered 容器的 O(1) 查找、count vs find 判断存在性、自定义哈希的写法。下一篇将讲解迭代器与算法库sort/find/transform/accumulate 等敬请期待
