map是用來存放<key, value>鍵值對的資料結構，可以很友善快速的根據key查到相應的value。假如存儲學生和其成績（假定不存在重名，當然可以對重名加以區分），我們用map來進行存儲就是個不錯的選擇。 我們這樣定義，map<string, int>，其中學生姓名用string類型，作為Key；該學生的成績用int類型，作為value。這樣一來，我們可以根據學生姓名快速的查找到他的成績。
但是，我們除了希望能夠查詢某個學生的成績，或許還想看看整體的情況。我們想把所有同學和他相應的成績都輸出來，并且按照我們想要的順序進行輸出：比如按照學生姓名的順序進行輸出，或者按照學生成績的高低進行輸出。換句話說，我們希望能夠對map進行按Key排序或按Value排序，然後按序輸出其鍵值對的内容。
一、C++ STL中Map的按Key排序
其實，為了實作快速查找，map内部本身就是按序存儲的（比如紅黑樹）。在我們插入<key, value>鍵值對時，就會按照key的大小順序進行存儲。這也是作為key的類型必須能夠進行<運算比較的原因。現在我們用string類型作為key，是以，我們的存儲就是按學生姓名的字典排序儲存的。
【參考代碼】
[cpp]
view plain
copy
print
?
- #include<map>
- #include<string>
- #include<iostream>
- using namespace std;
- typedef pair<string, int> PAIR;
- ostream& operator<<(ostream& out, const PAIR& p) {
- return out << p.first << "\t" << p.second;
- }
- int main() {
- int> name_score_map;
- "LiMin"] = 90;
- "ZiLinMi"] = 79;
- "BoB"] = 92;
- "Bing",99));
- "Albert",86));
- for (map<string, int>::iterator iter = name_score_map.begin();
- iter != name_score_map.end();
- ++iter) {
- cout << *iter << endl;
- }
- return 0;
- }
【運作結果】
大家都知道map是stl裡面的一個模闆類，現在我們來看下map的定義：
[cpp]
view plain
copy
print
?
- template < class Key, class T, class Compare = less<Key>,
- class Allocator = allocator<pair<const Key,T> > > class map;
它有四個參數，其中我們比較熟悉的有兩個: Key 和 Value。第四個是 Allocator，用來定義存儲配置設定模型的，此處我們不作介紹。
現在我們重點看下第三個參數： class Compare = less<Key>
這也是一個class類型的，而且提供了預設值 less<Key>。 less是stl裡面的一個函數對象，那麼什麼是函數對象呢？
所謂的函數對象：即調用操作符的類，其對象常稱為函數對象（function object），它們是行為類似函數的對象。表現出一個函數的特征，就是通過“對象名+(參數清單)”的方式使用一個 類，其實質是對operator()操作符的重載。
現在我們來看一下less的實作：
[cpp]
view plain
copy
print
?
- template <class T> struct less : binary_function <T,T,bool> {
- bool operator() (const T& x, const T& y) const
- return x<y;}
- };
它是一個帶模闆的struct，裡面僅僅對()運算符進行了重載，實作很簡單，但用起來很友善，這就是函數對象的優點所在。stl中還為四則運算等常見運算定義了這樣的函數對象，與less相對的還有greater：
[cpp]
view plain
copy
print
?
- template <class T> struct greater : binary_function <T,T,bool> {
- bool operator() (const T& x, const T& y) const
- return x>y;}
- };
map這裡指定less作為其預設比較函數(對象)，是以我們通常如果不自己指定Compare，map中鍵值對就會按照Key的less順序進行組織存儲，是以我們就看到了上面代碼輸出結果是按照學生姓名的字典順序輸出的，即string的less序列。
我們可以在定義map的時候，指定它的第三個參數Compare，比如我們把預設的less指定為greater：
【參考代碼】
[cpp]
view plain
copy
print
?
- #include<map>
- #include<string>
- #include<iostream>
- using namespace std;
- typedef pair<string, int> PAIR;
- ostream& operator<<(ostream& out, const PAIR& p) {
- return out << p.first << "\t" << p.second;
- }
- int main() {
- int, greater<string> > name_score_map;
- "LiMin"] = 90;
- "ZiLinMi"] = 79;
- "BoB"] = 92;
- "Bing",99));
- "Albert",86));
- for (map<string, int>::iterator iter = name_score_map.begin();
- iter != name_score_map.end();
- ++iter) {
- cout << *iter << endl;
- }
- return 0;
- }
【運作結果】
現在知道如何為map指定Compare類了，如果我們想自己寫一個compare的類，讓map按照我們想要的順序來存儲，比如，按照學生姓名的長短排序進行存儲，那該怎麼做呢？
其實很簡單，隻要我們自己寫一個函數對象，實作想要的邏輯，定義map的時候把Compare指定為我們自己編寫的這個就ok啦。
[cpp]
view plain
copy
print
?
- struct CmpByKeyLength {
- bool operator()(const string& k1, const string& k2) {
- return k1.length() < k2.length();
- }
- };
是不是很簡單！這裡我們不用把它定義為模闆，直接指定它的參數為string類型就可以了。
【參考代碼】
[cpp]
view plain
copy
print
?
- int main() {
- int, CmpByKeyLength> name_score_map;
- "LiMin"] = 90;
- "ZiLinMi"] = 79;
- "BoB"] = 92;
- "Bing",99));
- "Albert",86));
- for (map<string, int>::iterator iter = name_score_map.begin();
- iter != name_score_map.end();
- ++iter) {
- cout << *iter << endl;
- }
- return 0;
- }
【運作結果】
二、C++ STL中Map的按Value排序
在第一部分中，我們借助map提供的參數接口，為它指定相應Compare類，就可以實作對map按Key排序，是在建立map并不斷的向其中添加元素的過程中就會完成排序。
現在我們想要從map中得到學生按成績的從低到高的次序輸出，該如何實作呢？換句話說，該如何實作Map的按Value排序呢？
第一反應是利用stl中提供的sort算法實作，這個想法是好的，不幸的是，sort算法有個限制，利用sort算法隻能對序列容器進行排序，就是線性的（如vector，list，deque）。map也是一個集合容器，它裡面存儲的元素是pair，但是它不是線性存儲的（前面提過，像紅黑樹），是以利用sort不能直接和map結合進行排序。
雖然不能直接用sort對map進行排序，那麼我們可不可以迂回一下，把map中的元素放到序列容器（如vector）中，然後再對這些元素進行排序呢？這個想法看似是可行的。要對序列容器中的元素進行排序，也有個必要條件：就是容器中的元素必須是可比較的，也就是實作了<操作的。那麼我們現在就來看下map中的元素滿足這個條件麼？
我們知道map中的元素類型為pair，具體定義如下：
[cpp]
view plain
copy
print
?
- template <class T1, class T2> struct pair
- {
- typedef T1 first_type;
- typedef T2 second_type;
- T1 first;
- T2 second;
- pair() : first(T1()), second(T2()) {}
- const T1& x, const T2& y) : first(x), second(y) {}
- template <class U, class V>
- const pair<U,V> &p) : first(p.first), second(p.second) { }
- }
pair也是一個模闆類，這樣就實作了良好的通用性。它僅有兩個資料成員first 和 second，即 key 和 value，而且
<utility>頭檔案中，還為pair重載了 < 運算符， 具體實作如下：
[cpp]
view plain
copy
print
?
- template<class _T1, class _T2>
- inline bool
- const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
- return __x.first < __y.first
- || (!(__y.first < __x.first) && __x.second < __y.second); }
重點看下其實作：
[cpp]
view plain
copy
print
?
- __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second)
這個less在兩種情況下傳回true，第一種情況：__x.first < __y.first 這個好了解，就是比較key，如果__x的key 小于 __y的key 則傳回true。
第二種情況有點費解： !(__y.first < __x.first) && __x.second < __y.second
當然由于||運算具有短路作用，即目前面的條件不滿足是，才進行第二種情況的判斷 。第一種情況__x.first < __y.first 不成立，即__x.first >= __y.first 成立，在這個條件下，我們來分析下 !(__y.first < __x.first) && __x.second < __y.second
!(__y.first < __x.first) ，看清出，這裡是y的key不小于x的key ，結合前提條件，__x.first < __y.first 不成立，即x的key不小于y的key
即： !(__y.first < __x.first) && !(__x.first < __y.first ) 等價于 __x.first == __y.first ,也就是說，第二種情況是在key相等的情況下，比較兩者的value（second）。
這裡比較令人費解的地方就是，為什麼不直接寫 __x.first == __y.first 呢？ 這麼寫看似費解，但其實也不無道理：前面講過，作為map的key必須實作<操作符的重載，但是并不保證==符也被重載了，如果key沒有提供==，那麼 ，__x.first == __y.first 這樣寫就錯了。由此可見，stl中的代碼是相當嚴謹的，值得我們好好研讀。
現在我們知道了pair類重載了<符，但是它并不是按照value進行比較的，而是先對key進行比較，key相等時候才對value進行比較。顯然不能滿足我們按value進行排序的要求。
而且，既然pair已經重載了<符，而且我們不能修改其實作，又不能在外部重複實作重載<符。
[cpp]
view plain
copy
print
?
- typedef pair<string, int> PAIR;
- bool operator< (const PAIR& lhs, const PAIR& rhs) {
- return lhs.second < rhs.second;
- }
如果pair類本身沒有重載<符，那麼我們按照上面的代碼重載<符，是可以實作對pair的按value比較的。現在這樣做不行了，甚至會出錯（編譯器不同，嚴格的就報錯）。
那麼我們如何實作對pair按value進行比較呢？ 第一種：是最原始的方法，寫一個比較函數； 第二種：剛才用到了，寫一個函數對象。這兩種方式實作起來都比較簡單。
[cpp]
view plain
copy
print
?
- typedef pair<string, int> PAIR;
- bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {
- return lhs.second < rhs.second;
- }
- struct CmpByValue {
- bool operator()(const PAIR& lhs, const PAIR& rhs) {
- return lhs.second < rhs.second;
- }
- };
接下來，我們看下sort算法，是不是也像map一樣，可以讓我們自己指定元素間如何進行比較呢？
[cpp]
view plain
copy
print
?
- template <class RandomAccessIterator>
- void sort ( RandomAccessIterator first, RandomAccessIterator last );
- template <class RandomAccessIterator, class Compare>
- void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
我們看到，令人興奮的是，sort算法和map一樣，也可以讓我們指定元素間如何進行比較，即指定Compare。需要注意的是，map是在定義時指定的，是以傳參的時候直接傳入函數對象的類名，就像指定key和value時指定的類型名一樣；sort算法是在調用時指定的，需要傳入一個對象，當然這個也簡單，類名()就會調用構造函數生成對象。
這裡也可以傳入一個函數指針，就是把上面說的第一種方法的函數名傳過來。（應該是存在函數指針到函數對象的轉換，或者兩者調用形式上是一緻的，具體确切原因還不明白，希望知道的朋友給講下，先謝謝了。）
【參考代碼】
[cpp]
view plain
copy
print
?
- int main() {
- int> name_score_map;
- "LiMin"] = 90;
- "ZiLinMi"] = 79;
- "BoB"] = 92;
- "Bing",99));
- "Albert",86));
- //把map中元素轉存到vector中
- vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());
- sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
- // sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);
- for (int i = 0; i != name_score_vec.size(); ++i) {
- cout << name_score_vec[i] << endl;
- }
- return 0;
- }