测试环境：win10+vs2015
生活中经常遇到key-value问题，最常见的就是字典，所以研究key-value的问题就是很有必要的。
这里有个例题： 夏日炎炎，某公司为犒劳辛苦耕耘的程序猿，打算卖水果，但是不知道各位程序猿的喜欢的事什么水果，然后发了一张调查问卷，现今数据已经发到了你的手上，你需要统计并且找出最受程序猿欢迎的前几种水果。
这个是一道非常标准的key-value的topK问题。
思路：
使用map用来保存和统计程序猿选了哪一些水果（key）和相应水果选择的人数（value），由于map的底层是红黑树，方便查找使用堆用来找出最受程序猿欢迎的前K个水果，这里创建小根堆，即最小元素在堆顶（方便替换）代码实现：
/* 这个是包含上述方法的一个类*/#PRagma once#include<iostream> //包含输入输出#include<map> //引入map数据结构#include<algorithm> //引入堆的相关算法#include<vector> //引入vector数据结构 #include<string> //引入stringusing namespace std; //使用命名空间//创建两个仿函数，用来传入比较函数template<class K, class V>//pair是c++里面内置的一个类，方便我们使用key-value结构//其中first表示key，second表示valuetemplate<class K, class V>class Less {public: bool Operator()(const pair<K, V>& p1, const pair<K, V>& p2) { return p1.second < p2.second; }};template<class K, class V>class Great {public: bool operator()(const pair<K, V>& p1, const pair<K, V>& p2) { return p1.second > p2.second; }};//声明一个模板类template<class K, class V, class comp = Less<K, V>>class Count {public: //统计并保存的函数 void CountV(K key[],size_t size) { /* 参数：存放key的数组，数组大小 返回值：void */ //将每个数据依次导入 for (size_t i = 0; i < size; ++i) { /*由于map重载了[]，其意义是 (*((this->insert(make_pair(x,T()))).first)).second 通俗一点就是operator[]的参数是key，返回的是该key的value， 如果key不存在则会创建一个key，并把value设置成默认值 */ _m[key[i]]++; //找到key[i]所对应的value，然后++ } } //找map中前K个值 void TopK(size_t k) { /* 参数：找出前k个 返回值：void */ size_t size = _m.size(); //求得map的大小，用来停止迭代 map<string, int>::iterator it = _m.begin(); //声明一个map的迭代器 /* 这里本打算使用map<K, V>::iterator it; 但是好像迭代器只能使用一个确切的类型来创建 所以在这里纠结了一会儿 */ //设计一个遍历变量 size_t i = 0; //如果用户输入的值比size还要大，直接存入vector中，然后返回 if (size < k) { for (; i < size; ++i) { //使用尾插，进行插入 _v.push_back(*it); //++迭代器，可以访问下一个map元素 ++it; } //直接返回 return; } //如果用户输入是小于size for (; i < k; ++i) { //使用尾插 _v.push_back(*it); ++it; } //将剩下的元素进行一一插入 while (size != i) { //创建一个堆 make_heap(_v.begin(), _v.end(), comp()); //进行堆排序 sort_heap(_v.begin(), _v.end(), comp()); /* 堆排序后的第一个元素是整个堆里面最小的元素 一旦后续元素有比它大的都应该替换它 */ if ((_v[0]).second < _m[it->first]) { _v[0].first = it->first; _v[0].second = _m[it->first]; } ++i; } }protected://定义两个受保护的成员：//_m用来保存统计数据//_v用来当做堆的容器，堆的容器需要支持随机访问，vector比较合适 map<K, V> _m; vector<pair<K, V>> _v;};//这是一个测试函数void test() { Count<string, int> c; //创建一个Count类型的对象c string strs[] = { "a","b" ,"d" ,"a" ,"c" ,"d" ,"b" ,"a" ,"a" ,"c" ,"b" ,"b" ,"c" }; //相当于获取的水果数组 c.CountV(strs, sizeof(strs) / sizeof(strs[0])); //统计并存入c中 c.TopK(3); //找出出现次数最多的前3个元素}如果需要找出最小的前几个元素，将仿函数Less改为Great即可
这是一种常规的算法，算法简单，思路清晰，适合像我这样的初学去熟悉使用STL库来练练手
如有疑问可以在评论区交流交流
新闻热点
疑难解答
