測試環境：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庫來練練手
如有疑問可以在評論區交流交流
新聞熱點
疑難解答
