四. C++中的Map
⚡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的用法
💦Map的模板参数
参数说明：
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
使用map要包含map的头文件哦
💦Map的迭代器
//map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); while (it != dict.end()) { //pair没有重载流插入 //cout << (*it).first << (*it).second << endl; //cout << it->->first << it->->second << endl; //operator重载 cout << it->first << it->second << endl; ++it; } for (const auto& kv : dict)//给const & 引用 { cout << kv.first << ":" << kv.second << endl; } cout << endl;
💦Map的构造
void testmap1() { map<int, int> map1;//空构造 int num[] = { 1,5,9,4,8,2,3,1,5,4,5,7 }; for (auto e : num) { map1.insert(make_pair(e,e)); } map<int, int> map2(map1.begin(),map1.end());//迭代区间构造 map<int, int> map3(map2);//拷贝构造 for (auto& e : map3) { cout << e.first << ":" << e.second << endl; } }
💦Map的常见修改操作
🌏Insert
find插入的是pair的结构体，此版本是不支持冗余的，插入只看key值，有相等的就不需要了
void test_map1() { map<string, string> dict; //pair<string, string> kv1("sort", "排序"); //dict.insert(kv1); //匿名对象 dict.insert(pair<string, string>("sort", "排序")); dict.insert(pair<string, string>("test", "测试")); dict.insert(pair<string, string>("string", "字符串")); //宏替换 typedef pair<string, string> Dictkv; dict.insert(Dictkv("string", "字符串")); }
还有一个很便捷的操作：make_pair：构造匿名的pair，返回
dict.insert(make_pair("string", "字符串"));//很常用
💦Map的[ ]的使用（重头戏）
[]:的功能：查找 + 修改
map中有这个key，就返回value的引用（查找 + 修改）
map中没有这个key，会插入一个pair(key, K())，会插入这个key值，value就要去调用默认构造，最后还是返回value的引用 （插入+ 修改）
如果是int，就是0；是指针，就默认空指针；
map<string, string> dict; dict.insert(make_pair("sort", "排序")); dict["insert"]; //插入 dict["insert"] = "插入"; //插入 + 修改value返回值 dict["left"] = "左边"; //插入 + 修改
可以看见Insert的返回值和实现
key已经在map中，返回pair（key_iterator，false）
key不在map中，返回pair（new_key_iterator，true）
[]其底层实现：有两个pair结构
✨返回值是一个pair结构pair<iterator, bool>；第一个值是迭代器，第二个值是bool；第二个bool是用来反应是否插入成功，如果成功，则 第一个值迭代器就是指向插入的pair数据
第二个是kv的pair,是插入的pair数据
V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V()); //返回key节点的迭代器，迭代器是map的，再调用->就是pair*,取second return ret.first->second; }
⚡统计次数的两种方法
第一次找不到的时候make_pair，使得count = 1
后面每遍历一次就++一次
//统计次数 void test_map2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& str : arr) { map<string, int>::iterator it = countMap.find(str); if (it != countMap.end()) { /*(*it).second++;*/ //it->->second++; 第一个箭头是调用operator->返回的是pair*，再->指向成员 it->second++; } else { //找不到 countMap.insert(make_pair(str, 1)); } } //遍历 map<string, int>::iterator it = countMap.begin(); while(it != countMap.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; }
第二种方法：[]
map<string, int> countMap; for (auto& str : arr) { //1、str不在countMap中，插入pair(str, int()),然后对返回次数++ //2、str在的话，就返回value的引用次数++ countMap[str]++; }
⚡multimap的用法
multimap容器与map容器的底层实现以及成员函数的接口都是基本一致，区别是multimap 允许键值冗余，即multimap容器当中存储的元素是可以重复的
multimap<string, string> mdict; mdict.insert(make_pair("sort", "排序")); mdict.insert(make_pair("left", "左边")); mdict.insert(make_pair("left", "左边")); mdict.insert(make_pair("left", "你猜"));
五. 来两道题目练练手
1️⃣前K个高频单词
题目地址：传送
要注意要按出现次数按大到小的来，如果出现次数相等，要按字母顺序排序，比如：i和love都出现了两次，那么 按字母顺序i要在love之前
思路：
使用一个countMap统计各种单词的出现的次数（统计次数 此时是i在上面，love在下面）
再写一个sortMap按照字符出现的次数进行降序排列
不同的单词出现相同的次数，会按字典序排列
注意不能用反向迭代来进行，不然同样的次数，love会在前面，i在后；就违背了题意
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; //统计次数 此时是i在上面，love在下面 for(auto& str : words) { countMap[str]++; } // apple 3 \ i 2 \ love 2 \ j 5 multimap<int, string, greater<int>> sortMap;//排降序 for(auto& kv : countMap) { sortMap.insert(make_pair(kv.second, kv.first)); } vector<string> v; multimap<int, string, greater<int>> :: iterator it = sortMap.begin(); for(size_t i = 0; i < k; i++) { v.push_back(it->second); it++; } return v; } };
2️⃣两个数组的交集
题目地址：传送
思路：
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<int> :: iterator it1 = s1.begin(); auto it2 = s2.begin(); vector<int> v; while(it1 != s1.end() && it2 != s2.end()) { if(*it1 < *it2) { ++it1; } else if(*it1 > *it2) { ++it2; } else { v.push_back(*it1); ++it1; ++it2; } } return v; } };
那如果是求差集呢？
