C++STL中Map的按Key排序和按Value排序

1、C+ STL中Map的按Key排序和按 Value排序map是用來存放key, value鍵值對的數(shù)據(jù)結(jié)構(gòu)，可以很方便快速的根據(jù)key查到相應(yīng)的value。假如存儲學生和其成績（假定不存在重名，當然可以對重名加以區(qū)分），我們用map 來進行存儲就是個不錯的選擇。我們這樣定義，mapstring, int，其中學生姓名用 string類型，作為Key;該學生的成績用int類型，作為value。這樣一來，我們可以根據(jù)學生姓 名快速的查找到他的成績。但是，我們除了希望能夠查詢某個學生的成績，或許還想看看整體的情況。我們想把所有同學和他相應(yīng)的成績都輸出來， 并且按照我們想要的順序進行輸出： 比如按照學

2、生姓 名的順序進行輸出，或者按照學生成績的高低進行輸出。換句話說，我們希望能夠?qū)ap進行按Key排序或按Value排序，然后按序輸出其鍵值對的內(nèi)容。一、C+ STL中Map的按Key排序其實，為了實現(xiàn)快速查找，map內(nèi)部本身就是按序存儲的（比如紅黑樹）。在我們插入key, value鍵值對時，就會按照 key的大小順序進行存儲。這也是作為key的類型必須能夠進行 運算比較的原因?，F(xiàn)在我們用 string類型作為key,因此，我們的存儲就是按學 生姓名的字典排序儲存的?！緟⒖即a】【運行結(jié)果】AIbevt8G99BoB92LiMin90ZLLinHi79大家都知道m(xù)ap是stl里面的一個模板類

3、，現(xiàn)在我們來看下map的定義:它有四個參數(shù)，其中我們比較熟悉的有兩個：Key和Value。第四個是 Allocator ,用來定義存儲分配模型的，此處我們不作介紹。現(xiàn)在我們重點看下第三個參數(shù)：class Compare = less<Key>這也是一個class類型的，而且提供了默認值less<Key> 。 less是stl里面的一個函數(shù)對象，那么什么是函數(shù)對象呢？所謂的函數(shù)對象：即調(diào)用操作符的類，其對象常稱為函數(shù)對象（ function object ）,它們是 行為類似函數(shù)的對象。表現(xiàn)出一個函數(shù)的特征，就是通過對象名+（參數(shù)列表）'的方式使用一 個類，其實質(zhì)

4、是對operator。操作符的重載?，F(xiàn)在我們來看一下less的實現(xiàn)：它是一個帶模板的struct ,里面僅僅對（）運算符進行了重載，實現(xiàn)很簡單，但用起來很方便，這就是函數(shù)對象的優(yōu)點所在。stl中還為四則運算等常見運算定義了這樣的函數(shù)對象，與less相對的還有g(shù)reater :map這里指定less作為其默認比較函數(shù)（對象），所以我們通常如果不自己指定Compare ,map中鍵值對就會按照 Key的less順序進行組織存儲，因此我們就看到了上面代碼輸出結(jié) 果是按照學生姓名的字典順序輸出的，即 string的less序列。我們可以在定義 map的時候，指定它的第三個參數(shù)Compare，比如我們把

5、默認的less指定為 greater :【參考代碼】【運行結(jié)果】ZiLinKi 79LiMln 90BoB?2Bin99AIbevt 86現(xiàn)在知道如何為 map指定Compare類了，如果我們想自己寫一個compare的類，讓map按照我們想要的順序來存儲，比如，按照學生姓名的長短排序進行存儲，那該怎么做呢？其實很簡單，只要我們自己寫一個函數(shù)對象，實現(xiàn)想要的邏輯，定義map的時候把Compare 指定為我們自己編寫的這個就ok啦。是不是很簡單！這里我們不用把它定義為模板，直接指定它的參數(shù)為string類型就可以了。【參考代碼】【運行結(jié)果】BoB92Bin 9LiMin900 Ibc 好ZiLh

6、iMi7?二、C+ STL 中 Map 的按 Value 排序在第一部分中，我們借助map提供的參數(shù)接口，為它指定相應(yīng)Compare類，就可以實現(xiàn)對map按Key排序，是在創(chuàng)建 map并不斷的向其中添加元素的過程中就會完成排 序?，F(xiàn)在我們想要從map中得到學生按成績的從低到高的次序輸出，該如何實現(xiàn)呢？換句話說，該如何實現(xiàn) Map的按Value排序呢？第一反應(yīng)是利用stl中提供的sort算法實現(xiàn)，這個想法是好的，不幸的是， sort算法 有個限制，利用sort算法只能對序列容器進行排序，就是線性的（如vector, list, deque ）。map也是一個集合容器，它里面存儲的元素是 pair

7、,但是它不是線性存儲的（前面提過， 像紅黑樹），所以利用sort不能直接和map結(jié)合進行排序。雖然不能直接用sort對map進行排序，那么我們可不可以迂回一下，把 map中的元 素放到序列容器（如 vector）中，然后再對這些元素進行排序呢？這個想法看似是可行的。 要對序列容器中的元素進行排序，也有個必要條件：就是容器中的元素必須是可比較的，也就是實現(xiàn)了 操作的。那么我們現(xiàn)在就來看下map中的元素滿足這個條件么？我們知道m(xù)ap中的元素類型為 pair,具體定義如下：pair也是一個模板類，這樣就實現(xiàn)了良好的通用性。它僅有兩個數(shù)據(jù)成員first和second ,即key和value ,而且在u

8、tility頭文件中，還為pair重載了 運算符，具體實現(xiàn)如下：這個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 成立，在這個條件下，我們來分 析

9、下 !(_y.first < _x.first)&& _x.second < _y.second!(_y.first < _x.first),看清出，這里是 y 的 key不小于x的key ,結(jié)合前提條件，x.first< _y.first 不成立，即 x的key不小于y的key即：！(_y.first < _x.first)&&!(_x.first < _y.first )等價于 _x.first = _y.first ,也就是說，第二種情況是在key相等的情況下，比較兩者的 value (second )。這里比較令人費解

10、的地方就是，為什么不直接寫 _x.first = _y.first呢？這么寫看似費解,但其實也不無道理：前面講過，作為 map的key必須實現(xiàn) <操作符的重載，但是并不保證 =符也被重載了，如果 key沒有提供=，那么，_x.first = _y.first這樣寫就錯了。由此可見，stl中的代碼是相當嚴謹?shù)?，值得我們好好研讀。現(xiàn)在我們知道了 pair類重載了 <符，但是它并不是按照value進行比較的，而是先對 key進行比較，key相等時候才對value進行比較。顯然不能滿足我們按value進行排序的要求。而且，既然pair已經(jīng)重載了 <符，而且我們不能修改其實現(xiàn)，又不能在

11、外部重復(fù)實現(xiàn)重載<符。如果pair類本身沒有重載 <符，那么我們按照上面的代碼重載符，是可以實現(xiàn)對 pair的按value比較的?，F(xiàn)在這樣做不行了，甚至會出錯(編譯器不同，嚴格的就報錯)。那么我們?nèi)绾螌崿F(xiàn)對 pair按value進行比較呢？第一種：是最原始的方法，寫一個比較函數(shù)；第二種：剛才用到了，寫一個函數(shù)對象。這兩種方式實現(xiàn)起來都比較簡單。接下來，我們看下 sort算法，是不是也像 map 一樣，可以讓我們自己指定元素間如何進行 比較呢？我們看到，令人興奮的是，sort算法和map 一樣，也可以讓我們指定元素間如何進行比較， 即指定Compare。需要注意的是，map是在定義時指定的，所以傳參的時候直接傳入函數(shù) 對象的類名，就像指定 key和value時指定的類型名一樣；sort算法是在調(diào)用時指定的，需 要傳入一個對