void MapTest1() { map<string, string> dict; // 有名对象 pair<string, string> kv1("sort", "排序"); dict.insert(kv1); // 匿名对象 dict.insert(pair<string, string>("test", "测试")); dict.insert(pair<string, string>("sort", "排序")); dict.insert(pair<string, string>("string", "字符串")); typedef pair<string, string> DictKV; dict.insert(DictKV("left", "左边")); dict.insert(make_pair("left", "剩下")); // make_pair是个函数模板 //map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); while (it != dict.end()) { //cout << (*it).first << ":" << (*it).second << endl; // operator->返回的是结构的指针,再加上一个->就是结构中的数据 // 为了可读性,编译器省略了一个-> cout << it->first << ":" << it->second << endl; ++it; } cout << endl; for (auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; } cout << endl; }
注：map 的 operator* 返回的是结构体 pair。
注：map 和 set 的迭代器都是双向迭代器！！！
统计出现次数
void MapTest2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& str : arr) { map<string, int>::iterator it = countMap.find(str); if (it != countMap.end()) ++it->second; else countMap.insert(make_pair(str, 1)); } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; }
void MapTest3() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& str : arr) { // 1. str不在countMap中，插入pair(str, int())，再对value的引用进行++ // 2. str在countMap中，对value的引用进行++ ++countMap[str]; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; }
multimap
1. multimap 的介绍
multimap 是关联式容器，它按照特定的顺序，存储由 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 和 map 的唯一不同就是：map中的key 是唯一的，而 multimap 中 key 是可以重复的。
2. multimap 的使用
multimap 中没有重载[]，原因是 multimap 允许键值冗余。当有多个相同的键值时，不知道返回哪一个。
void MultimapTest() { multimap<string, string> mdict; mdict.insert(make_pair("sort", "排序")); mdict.insert(make_pair("left", "左边")); mdict.insert(make_pair("left", "剩下")); mdict.insert(make_pair("string", "字符串")); for (auto& kv : mdict) { cout << kv.first << ":" << kv.second << endl; } cout << endl; }
👉前K个高频单词👈
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序排序。
思路一：可以通过优先级队列来做，认为出现次数多的单词优先级高。如果出现次数相同，则在字典顺序靠前的优先级高。根据优先级比较的规则，我们自己实现一个仿函数即可。
class Solution { struct Less { bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const { if(kv1.second < kv2.second) return true; else if(kv1.second == kv2.second && kv1.first > kv2.first) return true; else return false; } }; public: vector<string> topKFrequent(vector<string>& words, int k) { // 统计出现的次数 map<string, int> countMap; for(auto& str : words) { ++countMap[str]; } // TOPK问题 priority_queue<pair<string, int>, vector<pair<string, int>>, Less> mh(countMap.begin(), countMap.end()); vector<string> v; while(k--) { v.push_back(mh.top().first); mh.pop(); } return v; } };
思路二：因为countMap中已经按照字典顺序排序了，所以我们可以采用稳定的排序对countMap中的元素按照出现次数来排序就行了。sort 底层是一个快排，快排是不稳定排序，那么我们可以给 sort 传一个比较方式，就可以保证稳定性了。注：sort 要求传入的迭代器是随机迭代器，而 map 的迭代器是双向迭代器。那我们可以先将 map 的元素存储 vector 中。
class Solution { struct Greater { bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const { if(kv1.second > kv2.second) return true; else if(kv1.second == kv2.second && kv1.first < kv2.first) return true; else return false; } }; public: vector<string> topKFrequent(vector<string>& words, int k) { // 统计出现的次数 map<string, int> countMap; for(auto& str : words) { ++countMap[str]; } vector<pair<string, int>> sortV(countMap.begin(), countMap.end()); sort(sortV.begin(), sortV.end(), Greater()); vector<string> v; for(size_t i = 0; i < k; ++i) { v.push_back(sortV[i].first); } return v; } };
上面的解法是通过比较方式来控制稳定性的。那么我们也可以使用库里提供的稳定排序stable_sort来控制稳定性。
class Solution { struct Greater { bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const { if(kv1.second > kv2.second) return true; else return false; } }; public: vector<string> topKFrequent(vector<string>& words, int k) { // 统计出现的次数 map<string, int> countMap; for(auto& str : words) { ++countMap[str]; } vector<pair<string, int>> sortV(countMap.begin(), countMap.end()); stable_sort(sortV.begin(), sortV.end(), Greater()); vector<string> v; for(size_t i = 0; i < k; ++i) { v.push_back(sortV[i].first); } return v; } };
思路三：因为countMap已经按照字典顺序排序了，那可以将其中的元素依次插入到以整型为 key 值的multimap中即可。
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { // 统计出现的次数 map<string, int> countMap; for(auto& str : words) { ++countMap[str]; } // 传greater<int>也是为了保证稳定性 multimap<int, string, greater<int>> sortMap; for(auto& str : countMap) { sortMap.insert(make_pair(str.second, str.first)); } vector<string> v; auto it = sortMap.begin(); for(size_t i = 0; i < k; ++i) { v.push_back(it->second); ++it; } return v; } };
👉两个数组的交集👈
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。
思路：因为set容器是对元素进行排序加上去重的，所以我们可以用数组中的元素来构造set，然后再来求交集。求交集的思路：谁小谁往后走，相等就添加到vector中并同时往后走。
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()); auto 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; } };
补充：求差集的思路：先用两个数组的元素构造出两个et，然后遍历set。谁小就将谁添加到vector中并且往后走，相等时就同时加加。求并集只需要将两个数组的元素插入到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()); auto it1 = s1.begin(); auto it2 = s2.begin(); vector<int> v; while(it1 != s1.end() && it2 != s2.end()) { if(*it1 < *it2) { v.push_back(*it1); ++it1; } else if(*it1 > *it2) { v.push_back(*it2); ++it2; } else { ++it1; ++it2; } } // 后面的元素都是相差的元素 while(it1 != s1.end()) { v.push_back(*it1); ++it1; } while(it2 != s2.end()) { v.push_back(*it2); ++it2; } return v; } };
👉总结👈
本篇博客主要讲解了键值对、关联式容器 set、multiset、map 和 multiset 以及两道 OJ 题前 K 个高频单词和两个数组的交集等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
