I.Map类0x00介绍template class Key, // map::key_type class T, // map::mapped_type class Compare lessKey, // map::key_compare class Alloc allocatorpairconst Key, T // map::allocator_type class map;STL是map的关联式容器按照特定顺序存储关联由Key和Value组合而成的元素{:}它们组合成键值对Key通常用于排序和唯一的表示元素value中存贮与key关联的内容key和value的类型额可以不同在map内部key和value通过成员类型value_type绑定value_type实际上就是pair类型typedef pair value_type;底层基于红黑树是一种自平衡的二叉搜索树能确保在插入和删除元素时维持良好的性能。map 通常被实现为二叉搜索树更准确地说是平衡二叉搜索树红黑树底层基于红黑树是一种自平衡的二叉搜索树能确保在插入和删除元素时维持良好的性能。0x01 pair类型map 的insert接口就是是一个value_type我们先来搞清楚什么是value_type。value_type 实际上就是 pair 类型在 map 中称之为键值对typedef pairconst Key, T value_type;pair 是在库里面就定义好了的SGI-STL 中关于键值对 的定义如下templateclass T1, class T2 struct pair { typedef T1 fisrt_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()) , second(T2()) {} pair(const T1 a, const T2 b) : first(a) , second(b) {} };0x02 map插入insert)我们假设 dict 变量的数据类型为mapstring, string我们可以如何插入数据呢①我们可以直接调用 pair 的构造函数来插入dict.insert(pairstring, string(sort, 排序));②似乎比较麻烦我们可以用匿名对象的方式来写pairstring, string kv(insert, 插入); dict.insert(kv);③还有更爽的方式调用神奇的make_pair我们戏称之为 做对子 dict.insert( make_pair(left, 左边) );make_pair 是一个函数模板使用时不用声明参数可自动推导出对应的类型。templateclass T1, class T2 pairT1, T2 make_pair(T1 x, T2 y) { return (pairT1, T2(x, y) ); }④还有更强大的方式插入直接用 { } dict.insert( {right, 右边} );0x03 遍历mapstring, string::iterator it dict.begin();map 的迭代器的底层相似于链表的迭代器。这里的类型真的是很长写起来很费劲……还有auto关键字auto it dict.begin();下面我们来写遍历部分我们发现似乎不行当然不行本质上是因为 C 不支持一次返回两个值这里的 * 就是 it-operator*() 。但是可以打包我们可以把这些返回值打包成一个结构数据 —— pair这里有两种方法第一种方法就是在 *it 中分别提取 first 和 secondauto it dict.begin(); while (it ! dict.end()) { cout (*it).first : (*it).second ; it; } cout endl;结果如下我们可以看到map 也是会自动排序的。当然我们还可以用 - 操作符auto it dict.begin(); while (it ! dict.end()) { cout it-first : it-second ; it; } cout endl;0x04 统计次数方式现在我们要统计一些数据比如我们需要统计这些水果的个数苹果, 西瓜, 苹果, 香蕉, 草莓, 柠檬西瓜, 苹果, 柠檬, 柠檬, 西瓜, 橙子草莓, 柠檬, 香蕉, 苹果, 橙子, 柠檬我们就可以使用 map 来存储pair 我们就可以用 string int 类型来组合mapstring, int count_map; // 统计水果的个数我们先用 最老实 的方式来进行统计用迭代器进行检查。检查很简单如果这个元素在map中就次数如果不在就将元素insert到map中mapstring,intCountMap; for(autostr:arr){ mapstring,int::iterator it CountMap.find(str); if(it!CountMap.end()){ it-second; } else{ CountMap.insert(make_pair(str,1));//CountMap.insert({str,1}); }打印一下void test_map2() { string arr[] { 苹果, 西瓜, 苹果, 香蕉, 草莓, 柠檬, 西瓜, 苹果, 柠檬, 柠檬, 西瓜, 橙子, 草莓, 柠檬, 香蕉, 苹果, 橙子, 柠檬 }; // 统计 mapstring, int count_map; for (auto str : arr) { mapstring, int::iterator it count_map.find(str); if (it ! count_map.end()) { it-second; } else { count_map.insert(make_pair(str, 1)); } } // 打印 for (auto kv : count_map) { cout kv.first : kv.second endl; } cout endl; }结果如下当然我们也可以这么做for (auto str : arr) { pair mapstring, int::iterator, bool ret count_map.insert(make_pair(str, 1)); }auto一下for (auto str : arr) { auto ret count_map.insert(make_pair(str, 1)); }为什么可以这么做呢我们来看下 map 的 insert 接口的原型std::pairiterator, boolinsert(const value_type value);我们可以看到 insert 的返回值是一个 pairiterator, bool 类型。插入成功 second 就是 true如果插入失败 second 就是 false。mapstring, int count_map; for (auto str : arr) { auto ret count_map.insert(make_pair(str, 1)); if (ret.second false) { ret.first-second; } }结果如下 解读ret.first-second不好理解实际上这里是两个pair嵌套在一块的一个 pair 是 insert 的返回值一个 pair 是节点。insert 的返回值里是pairiterator, int其中第一个是迭代器所以我们取first。而迭代器里是节点pairstring, int我们要让次数 1所以我们节点里我们取second。实际运用中这两种方法我们几乎都不用因为有更加的方式非常恐怖的方式for (auto str : arr) { count_map[str]; }下面我们来看一下operator[]0x05 map::operator[]底层mapped_type operator[] (const key_type k) { return (*((this-insert(make_pair(k, mapped_type()))).first)).second; }好长的一段啊这也太复杂了吧我们让他简洁一些mapped_type operator[] (const key_type k) { pairiterator, bool ret insert(make_pair(k, mapped_type())); // return (*(ret.first)).second; return ret.first-second; } 解读目的是在关联容器中通过键访问元素如果元素不存在则插入一个具有默认值的新元素并返回对这个元素的引用。首先const key_type k 是传入的键表示要查找或插入的元素的键值。make_pair(k, mapped_type()) 创建了一个 pair 对象该对象的第一个元素是传入的键 k第二个元素是使用 mapped_type 的默认构造函数创建的默认值。this-insert(...) 调用关联容器的 insert 函数该函数用于将一个键-值对插入容器中。返回值是一个pair其first 成员指向插入的元素second 成员指示是否插入成功。(this-insert(...).first) 获取返回的 std::pair 对象的 first 成员即指向插入的元素的迭代器。*((this-insert(...).first)) 解引用上一步中获取的迭代器得到插入的元素。(*((this-insert(...).first)).second再次解引用获取插入的元素的second成员即与传入的键关联的值。return (*((this-insert(...).first)).second; 返回通过operator[]访问或插入的元素的引用。这样就使得operator[]的实现如果是第一次出现就先插入。插入成功后会返回插入的节点中的次数 0 的引用对它 后变为 1。如果是第二次插入插入失败会返回它所在节点的迭代器的次数再 。II.Map算法题class Solution { public:vectorint topKFrequent(vectorint nums, int k) {我们看到题目中提到要记录整数K的出现频率除了暴力解法的遍历之外还可以想到使用mapint,int CountMap 来解决第一个int表示记录的元素值第二个int表示出现的次数那么这道题的解法就很明了了方法一TopK问题我们可以使用堆来求解这道题我们直接建立一个容量为K的最小堆class Solution { public: //仿函数出现频率更高的插入到最小堆 struct Comp{ bool operator()(const pairint,int a,const pairint,int b){ return a.secondb.second; } }; vectorint topKFrequent(vectorint nums, int k) { //定义Map来存储数据和出现次数 unordered_mapint,int mp; for(auto m:nums){ mp[m]; } //建立最小堆 priority_queuepairint,int,vectorpairint,int, Comp pq; int c0;//记录堆内元素个数 for(auto m:mp){ if(ck){ pq.push(m);//堆大小不足K直接入堆 c; } else{ // coutm.first m.secondendl; //堆已满K个元素档期那数字的频率堆顶最小频率时 if(m.secondpq.top().second){ //coutm.secondendl; pq.pop();//弹出堆顶 pq.push(m);//加入当前更大频率的数字 } } } //从最小堆中取出前K个元素存入vector中返回 vectorint ans; for(int i0;ik;i){ ans.push_back(pq.top().first); pq.pop(); } return ans; } }; priority_queue pairint,int, // 第1个堆里存什么类型 数字频率 vectorpairint,int, // 第2个底层容器固定写法 Comp // 第3个比较规则我们写的最小堆规则 pq;方法二快速选择class Solution { public: struct Compare{ bool operator()(const pairint,int kv1,const pairint,int kv2) { return kv1.secondkv2.second; } }; vectorint topKFrequent(vectorint nums, int k) { //创造一个map来计数,first:int ,因为这是个整数数组 //second:int ,计数 mapint,intCountMap; for(autoe:nums){ CountMap[e]; } //放到vector里面排序 vectorpairint,int v(CountMap.begin(),CountMap.end()); sort(v.begin(),v.end(),Compare()); //前k个 vectorint ret; int i 0; while(k--) { ret.push_back(v[i].first); } return ret; } };