好像是去年CVTE在招聘的時候出了這樣的一個筆試題：

       題目的大意就是：本公司現在要給公司員工發波福利，在員工工作時間會提供大量的水果供員工補充營養。由于水果種類比較多，但是卻又不知道哪種水果比較受歡迎，然后公司就讓每個員工報告了自己最愛吃的三種水果，并且告知已經將所有員工喜歡吃的水果存儲于一個數組中。然后讓我們統計出所有水果出現的次數，并且求出排列前三的這三種水果。

       拿到這個題，我們應該怎么做呢？

       首先，統計所有水果出現的次數，很顯而易見的我們最先想到的當然是，將數組遍歷一遍，就能得到每種水果的出現次數。然后再對求出水果次數的數組進行排序，這樣很容易就可以拿到最受歡迎三種水果。

       可是，大家有沒有想過，如果該公司有100w的員工，如此龐大的數量，我們對數字遍歷并且排序是多么大的開銷。而且其時間復雜度和空間復雜度都很高，如果按照這種思路我們肯定是會被拒之門外。

       那么，這道題應該怎么做呢？

       當然，首選的應該是紅黑樹了，并且需要的是K/V結構的紅黑樹，K來存儲水果的名稱，V來存儲這個水果出現的次數。

       可是，筆試時間那么短，紅黑樹相對來說比較復雜的結構，我們如何在短時間內拿到它呢？

       不用擔心，在c++STL庫中提供了兩個關聯式容器：set和map.

       那么我先大概的介紹一下這個set和map.

       set和map這兩個容器的底層都是用紅黑樹來實現的，并且他們都具有防冗余的特性（被插入的數據如果在容器中已經出現，那么插入失敗），他兩的唯一區別就是set是一個K結構，而map是一個K/V結構。

       那么他們是怎么使用呢？

       在這里，我主要講解一下map，因為上邊的這個題需要用到它。而set和map的用法基本上是一模一樣的。

       首先，來看一下這個map的原型：

	template < class Key,                                     // map::key_type          	 class T,                                       // map::mapped_type           	class Compare = less<Key>,                     // map::key_compare           	class Alloc = allocator<pair<const Key,T> >    // map::allocator_type           	> class map;
        那么這個map的模板參數都是什么意思呢？
        Key:這個就是我剛才說的K/V結構中的K
        T:這個就是我剛才說的K/V結構中的V
        Compare:這個是一個接受仿函數類型的參數，可以控制map是一個升序的還是降續的(不傳這個參數時，默認是升序)
        Alloc：這個是空間配置器，我們現在還用不到，先知道它是什么就好了。
        那么，這個map都有哪些接口呢？(這里主要講幾個重要的接口)
        1.insert      
	pair<iterator,bool> insert (const value_type& val);
        首先其返回值是一個pair，什么是pair:一個結構體，第一個參數是一個迭代器，第二個參數數一個bool值。意思就是：如果插入成功，就返回一個被插入元素的迭代器，并且第二個參數為true;反之返回容器中已經存在的這個和被插入元素相同的元素的迭代器和false.
        其參數是value_type          typedef  pair<const Key,T> value_type;
    2.Operator[]
    這個運算符的重載非常巧妙，等會再來講解。
    
    那么現在，我們回歸這道題：
    首先，求解所有水果出現的次數，在這里有三種解法：
    解法一：
         定義一個map，然后將數組中所有的元素插入到map中，在插入前先使用find()來查找存在不存在，如果不存在則插入，如果存在，則利用find返回值來對找到的元素的V進行+1操作。（其中strs是水果數組，同下）
  
	map<string, int> fruitCount;//創建map對象	for (int i = 0; i < sizeof(strs) / sizeof(strs[0]); ++i)	{		map<string, int>::iterator it = fruitCount.find(strs[i]);//創建map迭代器		if (it != fruitCount.end())//先查找看該字符數組內是否存在該字符串		{			(*it).second++;//給該類對象的計數+1			//或			//it->second++;		}		else		{			fruitCount.insert(pair<string, int>(strs[i], 1));		}	}
     解法二：
          上邊的解法一就是一種傳統的思維方式，但是效率稍微顯慢，英文如果map中沒有要插入的元素，則需要遍歷兩次map。
          那么，如何做到只遍歷一次就能完成這個任務呢？
          還記得我之前講的那個insert的返回值pair嗎？既然不管是否插入成功，它都能返回我們需要的這個元素的迭代器。那么，我們可以先插入，然后對其返回值進行保存，如果該返回值得第二個參數是true，表示插入成功，不進行其他操作，如果為flase，表示插入失敗，那么其返回的第一個參數將會帶回已經存在的這個被插入元素的迭代器，當然輕而易舉就可以通過迭代器拿到這個元素的第二個參數V。
	void CalculateFruitCount(map<string,int>& m, string s[], size_t size)	{		for (size_t i = 0; i < size; i++)		{			//m[s[i]]++;    //map中有operator[]的重載,其內容等同于下邊代碼					pair<map<string, int>::iterator, bool> ret;			ret = m.insert(make_pair(s[i], 1));			if (ret.second == false)				ret.first->second++;		}	}
     解法三：
          解法二中被注釋掉的那一句。那么現在我就講一下這個operator[].map中對[]這個運算符進行了重載，其格式為：
          T& operator[] (const Key& k);
          而其代碼的實現就是解法二中的思想。現在大家對這個operator了解了吧。
     好!到這里，這個問題已經解決了一半。那么我們繼續往下走。
     現在水果出現的次數已經統計出來，那么如何求出排列前3的水果呢？乃至前N呢？
     這里有4中解法：
     1.講統計好的數據全部放入一個vector中，并且利用排序算法sort進行排序。而其默認為升序，最大的則位于數組后邊，但是我們并不知道vector有多大。所以，我們采用降續，這樣最大的永遠在vector的前列.
void GetBeginOfThreeFruits(map<string, int>& m, vector<map<string, int>::iterator>& v)  //按照水果出現的次數降續存儲于v中{	map<string, int>::iterator it = m.begin();	while (it != m.end())	{		v.push_back(it);		it++;	}		struct Compare   //仿函數（降續）	{		bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)		{			return l->second > r->second;		}	};	sort(v.begin(), v.end(),Compare());}
     2.同1的思想，只不過這次我們不是放在vector中，而是放在一個set中，這樣就可以省去我們自己給它排序的麻煩。（因為set底層是一個紅黑樹，而紅黑樹就是一個近似平衡的二叉排序樹）代碼比較簡單，這里就不實現了。
     3.大家還知道堆嗎？既然我們需要找出最大的3個，那么我們只需要建立一個3個大小的堆，但是，我們應該建大堆還是小堆呢?當然是小堆，為什么呢?
       因為，小堆的話大的數據就會往下沉，而對頂永遠是最小的，當來了一個數據時，我們只需要和對頂的元素做一個判斷，如果比對頂元素小，那么不用插入到堆，如果比對頂元素大，那么將對頂元素pop出去，然后將這個元素插入。當剛才求好水果出現次數的數組全部遍歷一遍后，最后堆里面剩下的肯定就是出現次數最多的三個水果。
void GetBeginOfNFruits(map<string, int>& m, size_t n, vector<map<string,int>::iterator>& v){	map<string, int> ::iterator it = m.begin();	for (size_t i = 0; i < n; ++i)	{		v.push_back(it);		it++;	}	struct Compare  //堆算法默認是大堆，此處需要仿函數將其改為小堆	{		bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)		{			return l->second > r->second;  //小堆		}	};	make_heap(v.begin(), v.end(), Compare());	while (it != m.end())	{		if (it->second > v.front()->second)		{			pop_heap(v.begin(), v.end(), Compare());			v.pop_back();			v.push_back(it);			push_heap(v.begin(), v.end(), Compare());					}		it++;	}}
      4.利用優先級隊列，優先級隊列的底層其實就是一個堆，這里代碼不予實現了，思想同3.
      到這里，整個題目就解決完了。代碼寫出來其實不難，難的就是我們需要對STL庫函數有一定的了解，已經要會使用。