【C＋＋STL】map与set（举例+详解，一文说懂）！
🌟个人主页：第七序章
🌈专栏系列：C＋＋
目录
6.5.4 ⭐map的数据修改+map的迭代器和[ ]功能样例
7.2 🌙如何统计水果出现的次数并排序（map用法和排序稳定性）
❄️前言：
上一篇我们学习了C++数据结构——二叉搜索树，以及在之前的学习中，已经接触过了string、vector、list、stack、queue等容器，现在来了解一下set与map容器的使用。
☀️一、序列式容器与关联式容器
🌷序列式容器:前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，其依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
🌷关联式容器:关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构， 两个位置有紧密的关联关系，交换⼀下，其存储结构就被破坏了。序列容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。 本章节讲解的map和set底层是红⿊树，红⿊树是⼀棵平衡⼆叉搜索树。
🌷set是key搜索场景的结构， map是key/value搜索场景的结构。
☀️二、键值对
🌷用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，其中key代表健值，而value表示与key对应的信息。比如:字典中必然存在英文单词与其对应的中文含义
☀️三、树形结构的关联式容器
🌷根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，采用中序遍历，容器中的元素是一个有序的序列
☀️四、set
🌙4.1 set介绍
set是按照一定次序存储元素的容器
🌷在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的，对此插入元素时，只需要插入value即可，不需要构造键值对
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
🌷set中的元素不可以重复(因此可以使用set进行去重)
🌷set中的元素默认按照小于来比较
🌷set中查找某个元素，时间复杂度为：O(logn)
🌷set中的元素不允许修改，保证数据排序和搜索树结构
🌷set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代
🌷与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对
🌷set中的底层使用二叉搜索树(红黑树)来实现
🌙4.2 set的构造和迭代器
set的构造我们关注以下几个接口即可。
🌷set⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造 explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type()); // copy (3) 拷⻉构造 set (const set& x); // initializer list (5) initializer 列表构造 set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是⼀个双向迭代器 iterator -> a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();🌙4.3 set的增删查
🌷set的增删查关注以下几个接口即可：
Member types key_type -> The first template parameter (T) value_type -> The first template parameter (T) // 单个数据插⼊，如果已经存在则插⼊失败 pair<iterator,bool> insert (const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert (initializer_list<value_type> il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template <class InputIterator> void insert (InputIterator first, InputIterator last); // 查找val，返回val所在的迭代器，没有找到返回end() iterator find (const value_type& val); // 查找val，返回Val的个数 size_type count (const value_type& val) const; // 删除⼀个迭代器位置的值 iterator erase (const_iterator position); // 删除val，val不存在返回0，存在返回1 size_type erase (const value_type& val); // 删除⼀段迭代器区间的值 iterator erase (const_iterator first, const_iterator last); // 返回⼤于等val位置的迭代器 iterator lower_bound (const value_type& val) const; // 返回⼤于val位置的迭代器 iterator upper_bound (const value_type& val) const;🌙4.4 insert和迭代器遍历使用样例
#include<set> #include<iostream> using namespace std; int main() { //去重+升序排序 set<int> s1; //去重+排降序(传一个大于的仿函数) set<int, greater<int>> s2; s2.insert(1); s2.insert(4); s2.insert(-2); s2.insert(100); //使用迭代器 set<int>::iterator it = s2.begin(); //auto it = s2.begin(); while (it != s2.end()) { cout << *it << " "; it++; } cout << endl; //使用范围for打印 for (auto e : s2) { cout << e << " "; } cout << endl; //支持插入一段initializer_list列表值，已经存在的值插入失败 s2.insert({ 2, 3, 4, 5 }); for (auto e : s2) { cout << e << " "; } cout << endl; //set里面存如string类型的值 set<string> strset = { "sort","animal","list","young" }; //遍历strset比较ASCII码大小进行插入,注意这里并不是比较字符串的长度 //注意下面e最好使用引用，set里面存的是string类型，多次的拷贝构造e会降低效率，不想改变就加上const即可 for (const auto& e : strset) { cout << e << " "; } cout << endl; return 0; }
🌙4.5 find和erase使用样例
🌷erase删除成功就返回1，删除失败就返回0
【erase+find+count】
#include<iostream> #include<set> using namespace std; int main() { set<int> s = { 1,4,0,34,12,56 }; for (auto e : s) { cout << e << " "; } cout << endl; //1.利用迭代器进行删除,删除最小值 s.erase(s.begin()); for (auto e : s) { cout << e << " "; } cout << endl; //2.直接输入x，删除x int x = 0; cin >> x; //erase的返回值帮助我们去判断是否删除成功 int num = s.erase(x); if (num == 0) { cout << x << "不存在!" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; //3.先查找再利用迭代器去删除 int y = 0; cin >> y; auto pos = s.find(y); if (pos != s.end()) s.erase(pos); else cout << "不存在！" << endl; for (auto e : s) { cout << e << " "; } cout << endl; // 算法库的查找 O(N)，全部进行遍历 auto pos1 = find(s.begin(), s.end(), x); // set⾃⾝实现的查找 O(logN),按照平衡二叉树的特点进行寻找 auto pos2 = s.find(x); // 利⽤count间接实现快速查找 cin >> x; if (s.count(x)) { cout << x << "在！" << endl; } else { cout << x << "不存在！" << endl; } return 0; }
【lower_bound+upper_bound】
#include<iostream> #include<set> using namespace std; int main() { set<int> s = { 10,20,35 ,40 ,50 ,65 ,70 ,80 ,90 }; for (int i = 1; i < 10; i++) { s.insert(i * 10); } for (auto e : s) { cout << e << " "; } cout << endl; // 实现查找到[itlow,itup)包含[30, 60]区间]，注意[itlow,itup)左闭右开 // 返回 >= 30 auto itlow = s.lower_bound(30); // 返回 > 60 auto itup = s.upper_bound(60); //删除这段区间的值 s.erase(itlow, itup); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }
🌙4.6 multiset和set的差异
🌷multiset和set的使用基本完全类似，主要区别点在于multiset⽀持值冗余，那么 insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下⾯的样例代码理解。
#include<iostream> #include<set> using namespace std; int main() { //相比set不同的是，multiset是排序，但是不去重 multiset<int> s = { 1,4,3,4,6,4,8,3,0 }; for (auto e : s) { cout << e << " "; } cout << endl; //multiset相比于set不同的是，里面可以存在多个x，find查找中序里面的第一个x int x = 0; cin >> x; //返回的是pos位置的迭代器，返回的是中序里面的第一个x auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // 相比set不同的是，count会返回x的实际个数 cout << s.count(x) << endl; //相⽐set不同的是，erase给值时会删除所有的x s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }
🌙4.7 set相关题目练习
🌷我们需要知道，set是间接实现去重操作，如果存在该值就不再插入到set里面。
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); // 因为set遍历是有序的，有序值，依次⽐较 // ⼩的++，相等的就是交集 vector<int> ret; auto it1 = s1.begin(); auto it2 = s2.begin(); while (it1 != s1.end() && it2 != s2.end()) { if (*it1 < *it2) { it1++; } else if (*it1 > *it2) { it2++; } else { ret.push_back(*it1); it1++; it2++; } } return ret; } };
数据结构初阶阶段，我们通过证明⼀个指针从头开始走⼀个指针从相遇点开始走，会在入口点相遇， 理解证明都会很麻烦。这里我们使用set查找记录解决非常简单方便，这里体现了set在解决⼀些问题时的价值，完全是降维打击。
快速判断一个值在不在，下面类似的算法很有用
class Solution { public: ListNode* detectCycle(ListNode* head) { set<ListNode*> s; ListNode* cur = head; while (cur) { //如果cur在s.count的返回值是1，则表明带环，返回值是0是插入即可 if(s.count(cur)) return cur;//入环节点 else s.insert(cur); cur=cur->next; } return nullptr; } };
☀️五、multiset
🌙5.1 multiset介绍
🌷multiset当作可以set使用，同样属于key模型，区别在于muliset允许数据冗余也就是不去除重复数据。muliset是一种允许元素重复出现的集合类型，你可以像使用set一样使用它，但它会保留重复的元素并且不进行去重操作。
🌙5.2 multiset使用
int main() { multiset<int> s1; s1.insert(1); s1.insert(11); s1.insert(3); s1.insert(1); s1.insert(4); s1.insert(2); s1.insert(4); s1.insert(2); s1.insert(1); s1.insert(2); s1.insert(1); multiset<int>::iterator it = s1.begin(); while (it != s1.end()) { //*it = 1; cout << *it << " "; ++it; } cout << endl; auto pos = s1.find(2); while (pos != s1.end() && *pos == 2) { cout << *pos << " "; ++pos; } return 0; } 
☀️六、map
🌙6.1 map介绍
🌷map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
🌷在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。
🌷键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
🌷在内部，map中的元素总是按照键值key进行比较排序的。
🌷map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
🌷map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
🌷map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
map的模板参数说明：
🌷key: 键值对中key的类型
🌷T： 键值对中value的类型
🌷Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
🌷Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件
🌷key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;的意思就是说，之前key和value是单个单个的存储的，现在将key和value存在一个结构中。
🌙6.2 掌握pair与make_pair
⭐6.2.1 pair
🌷在 C++ 中，pair 确实是一个模板类，允许用户将两个不同类型的数据组合在一起。模板的关键特性是它能够为不同类型的元素提供通用的实现，因此 pair 能够处理任意类型的两个数据项。
pair底层实现逻辑
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; //Key T1 first; //value T2 second; pair():first(T1(), T2()){} pair(const T1& a, const T2& b):first(a), second(b){} }; ⭐6.2.2 make_pair
🌷make_pair 是 C++ 标准库中的一个函数模板，用于简化 std::pair 对象的创建。它可以自动推导出 pair 的类型，因此在构造 pair 对象时，无需显式地指定模板参数类型。
⭐6.2.3 pair与make_pair区别
🌷相对于pair使用中需要明确数据类型，而make_pair是函数模板可以自动去推类型
函数模板：支持类型推导，编译器根据传递的参数自动推导模板参数。类模板：不支持类型推导，必须显式指定模板参数类型，因为类的结构和使用方式更复杂，无法通过简单的参数推导出类型。
🌙6.3 map对象多种插入场景
int main() { map<string, string> dict; pair<string, string> kv1("sort", "排序"); dict.insert(kv1); //使用匿名对象 dict.insert(pair<string, string>("left", "左边")); //使用make_pair,省略类型的书写 dict.insert(make_pair("right", "右边")); //隐式类型转化 pair<string, string> kv2("string", "字符串"); dict.insert({ "string", "字符串" }); //初始化列表 map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} }; return 0; } 关于以上两种map初始化的方式，推荐使用第一种写法。同时需要注意的是dict.insert({ "string", "字符串" });这里不是列表初始化initializelist，而是调用pair构造函数，强制类型转化为pair类型插入数据。
⭐6.3.1 map当中列表初始化
🌷而对于map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} };属于初始化列表， std::map 的构造函数接受一个std::initializer_list<std::pair<const Key, T>> 类型的参数。所以当你使用 {"i", "dd"} 进行初始化时，它会被转换为 std::pair<const std::string, std::string> 类型，然后添加到 map 中。
🌙6.4 将数据存在结构体
🌷我们知道map中的元素类型是pair或make_pair，但是为什么map不分开来存储数据呢？而是需要将数据放在一个结构体中，通过结构体间接访问这些对象。
//map<string, string>::iterator it = dict.begin(); //auto的作用就重复体现到了 auto it = dict.begin(); while (it != dict.end()) { // iterator key不能修改 value可以修改 // const_iterator key不能修改 value不能修改 //it->first += 'x'; it->second += 'x'; ++it; } cout << endl; 🌷关于key不是能被修改的。在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。对此key是不能随意修改的，可能会破坏搜索树结构，但key所对的内容value是支持修改的。
auto it = dict.begin(); while (it != dict.end()) { cout << (*it).first << ":" << (*it).second << endl; } cout << endl; 🌷对于如果不将key和value放在同一个结构体中，operator *只能返回一个值，但是我们希望可以得到key也可以得到value的值，对此将这两个变量放在结构体中，间接调用这两个变量，就会不出现冲突。对于上面的写法过于麻烦，这里喜欢使用→来解引用。
🌷底层是调用operator ->接口，这里编译器会省略一个箭头进行优化，使得使用更加便捷。
🌙6.5 map相关接口使用
⭐6.5.1 map的构造
map的构造我们关注以下几个接口即可。
🌷map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着⽀持范围for，map支持修改value数据，不支持修改key数据，修改关键 字数据，破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造 explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type()); // copy (3) 拷⻉构造 map(const map& x); // initializer list (5) initializer 列表构造 map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是⼀个双向迭代器 iterator->a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();⭐6.5.2 map的增删查
🌷map的增删查关注以下几个接⼝即可： map增接⼝，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value
Member types key_type -> The first template parameter (Key) mapped_type -> The second template parameter (T) value_type -> pair<const key_type,mapped_type> // 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 pair<iterator,bool> insert (const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert (initializer_list<value_type> il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template <class InputIterator> void insert (InputIterator first, InputIterator last); // 查找k，返回k所在的迭代器，没有找到返回end() iterator find (const key_type& k); // 查找k，返回k的个数 size_type count (const key_type& k) const; // 删除⼀个迭代器位置的值 iterator erase (const_iterator position); // 删除k，k存在返回0，存在返回1 size_type erase (const key_type& k); // 删除⼀段迭代器区间的值 iterator erase (const_iterator first, const_iterator last); // 返回⼤于等k位置的迭代器 iterator lower_bound (const key_type& k); // 返回⼤于k位置的迭代器 const_iterator lower_bound (const key_type& k) const;⭐6.5.3 构造遍历及增删查使用样例
#include<iostream> #include<map> #include<string> using namespace std; int main() { //转换成多参数的直接构造kv1 pair<string, string> kv1 = { "sky","天空" }; //正常情况下是这样的，先构造kv1对象，再用initializer list (5) initializer 列表构造 //map<string, string> dict = { kv1 }; //这里是pair的多参数的构造的转换，以前的单参数是直接构造，这里省略了上面的步骤 map<string, string> dict = { {"left","左边"},{"right","右边"},{"list","列表"},{"animal","动物"} }; auto it = dict.begin(); while (it != dict.end()) { cout << (*it).first << ":"<<(*it).second << endl; // map的迭代基本都使⽤operator->,这⾥省略了⼀个-> // 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据 //cout << it->first << ":"<<it->second << endl; //cout << it.operator->()->first << ":" << it->second << endl; it++; } cout << endl; //范围for,为什么这里使用引用？ for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便 pair<string, string> kv2("one","一"); dict.insert(kv2); //匿名对象去插入 dict.insert(pair<string, string>("num", "数字")); //前两个都是创建pair的对象，有名和匿名的区别 dict.insert(make_pair("two", "二")); //多参数也支持隐式类型转换 dict.insert({ "three", "三" }); for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; //结构化绑定，将dict里面的值分别赋值给k和v，C++17才开始支持的 for (const auto& [k,v] : dict) { cout << k << ":" << v << endl; } //经典的key/value场景，通过一个值去找另一个值 string str; while (cin >> str) { auto ret = dict.find(str); if (ret != dict.end()) { cout << "->" << ret->second << endl; } else { cout << "不存在！请重新输入" << endl; } } return 0; }
//修改map里面的second #include<iostream> #include<map> #include<string> using namespace std; int main() { map<string, string> dict = { {"left","左边"},{"right","右边"},{"list","列表"},{"animal","动物"} }; //通过迭代器进行修改，但是仅能修改second for (auto& e : dict) { e.second += "y"; cout << e.second << endl; } cout << endl; //通过find进行修改 auto ret = dict.find("left"); ret->second = "左边"; for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } return 0; }⭐6.5.4 map的数据修改+map的迭代器和[ ]功能样例
[ ]的底层是用insert实现的，我们先来了解insert
🌷前面我提到map⽀持修改mapped_type 数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。 map第⼀个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map 还有⼀个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是⼀个多功能复合接口需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为 mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
Member types key_type -> The first template parameter (Key) mapped_type -> The second template parameter (T) value_type -> pair<const key_type,mapped_type> // 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的 mapped_type值 iterator find (const key_type& k); // ⽂档中对insert返回值的说明 // The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed. // insert插⼊⼀个pair<key, T>对象 // 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象 first是key所在结点的迭代器，second是false // 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象 first是新插⼊key所在结点的迭代器，second是true // 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器 // 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[] // 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另 ⼀个是insert返回值pair<iterator,bool> pair<iterator,bool> insert (const value_type& val); mapped_type& operator[] (const key_type& k); // operator的内部实现 mapped_type& operator[] (const key_type& k) { // 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储 mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能 // 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的 迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能 pair<iterator, bool> ret = insert({ k, mapped_type() }); iterator it = ret.first; return it->second; }
【应用1】
#include<iostream> #include<map> #include<string> using namespace std; int main() { map<string, string> dict; //不存在，插入{"insert",string()}，value中插入的是string()的默认值 dict["insert"]; //不存在，成功插入，返回的是value的引用，可以完成修改 dict["list"] = "列表"; //修改 dict["list"] = "列表，清单"; //查找，已存在就返回已存在list结点迭代器中value的引用 cout << dict["list"] << endl; return 0; }【应用2】
int main() { // 利⽤find和iterator修改功能，统计⽔果出现的次数 string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹果", "⾹蕉", "苹果", "⾹蕉" }; map<string, int> countMap; for (const auto& str : arr) { // 先查找⽔果在不在map中 // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1} // 2、在，则查找到的节点中⽔果对应的次数++ auto ret = countMap.find(str); if (ret == countMap.end()) { countMap.insert({ str, 1 }); } else { ret->second++; } } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; } //根据上面学的知识，下面一句代码就搞定上面代码的场景，厉害！ int main() { // 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数 string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹果", "⾹蕉", "苹果", "⾹蕉" }; map<string, int> countMap; for (const auto& str : arr) { // []先查找⽔果在不在map中 // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了 // 2、在，则返回⽔果对应的次数++ countMap[str]++; } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; }⭐6.5.5 erase
🌷这里使用insert不会出现迭代器实现的问题，而erase可能会出现迭代器失效的问题，这里搜索树可以看成链表的加强版。
⭐6.5.6 operaor[]
🌷首先这里operator不是通过下标进行访问，而是通过key来进行访问对应value。关于operator[]实现不是通过find来实现而是通过insert来实现。
⭐6.5.7 insert实现operator[]
解释上面两段话
🌷key存在，插入失败，返回 ->pair < 存在的key所在节点的迭代器，false>
🌷key不存在，插入成功，返回 ->pair < 新插入key所在节点的迭代器，true>
对此我们可以看出来，insert在find功能基础上增加了插入的功能。这里insert的功能就是查找 + 插入(如果该元素存在，就是查找)
⭐6.5.8 operaort[] 底层逻辑
V& operator[](const K& key) { // 不管插入成功还是失败，pair中iterator始终指向key所在节点的iterator //这个V()就是调用默认构造，不是一个明确的数值 pair<iterator, bool> ret = this->insert(make_pair(key, V())); iterator it = ret.fisrt; return it->second; } ☀️七、map使用方面
🌙7.1 operator[]使用
int main() { map<string, string> dict; dict.insert({ "string", "字符串" }); // 插入（一般不会这么用，单纯的插入） dict["right"]; // 插入left + 修改 left对应内容 dict["left"] = "左边"; // "查找" cout << dict["string"] << endl; // 修改 dict["right"] = "右边"; string str; cin >> str; if (dict.count(str)) { cout << "在" << endl; } else { cout << "不在" << endl; } return 0; } 
🌙7.2 如何统计水果出现的次数并排序（map用法和排序稳定性）
瑕疵版本
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" }; map<string, int> countMap; for (auto& e : arr) { auto it = countMap.find(e); if (it != countMap.end()) { it->second++; } else { //const pair<string, int>& val = { e, 1 }; countMap.insert({ e, 1 }); } } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; 
优化版本
通过operator[]学习，我们可以对上面代码进行优化。
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" }; map<string, int> countMap; for (auto& e : arr) { countMap[e]++; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; 
通过次数来排序
只需将countMap的first和second位置数据，分别存放在sortMap的second和first位置上就行了
map<int, string> sortMap; for (auto& kv : countMap) { //sortMap[kv.second] = kv.first; sortMap.insert({ kv.second, kv.first }); } cout << endl; for (auto& kv : sortMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } 
🌷这里问题就是香蕉不见。对此我们知道map底层是通过搜索树实现的，而二叉搜索树是不允许冗余数据，并且是通过K对比较的，如果出现重复的K不会进行插入操作。（现在是次数对内容，而不是内容对次数，搞清楚K现在是谁)
multimap允许冗余
🌷真的需要排序，可以使用multimap 允许冗余.
☀️八、multimap
⭐multimap和map的差异
🌷multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如 find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插入了，不能⽀持修改。
⭐multimap使用事项:
🌷Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的
🌷在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，
value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
🌷multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
🌷multimap在底层用二叉搜索树(红黑树)来实现。
🌷multimap中的key是可以重复的。
🌷multimap中的元素默认将key按照小于来比较。
🌷multimap中没有重载operator[]操作，允许数据冗余，那么查找有冲突。
🌷使用时与map包含的头文件相同。
🌻共勉:
以上就是本篇博客的所有内容，如果你觉得这篇博客对你有帮助的话，可以点赞收藏关注支持一波~~🥝
![[特殊字符]颠覆MCP！Open WebUI新技术mcpo横空出世！支持ollama！轻松支持各种MCP Server！Cline+Claude3.7轻松开发论文检索MCP Server！](https://qiniu.meowparty.cn/coder.2023/2026-03-16/cover_1773591144192_f510eca35cdf4772ab987ff1e7151aa7.png)
