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

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

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

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

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

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

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

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

8、tility頭文件中，還為pair重載了 運(yùn)算符，具體實(shí)現(xiàn)如下：這個(gè)less在兩種情況下返回true，第一種情況：_x.first < _y.first這個(gè)好理解，就是比較key，如果_x的key小于 _y的key則返回true。第二種情況有點(diǎn)費(fèi)解：！(_y.first < _x.first) && _x.second < _y.second當(dāng)然由于|運(yùn)算具有短路作用，即當(dāng)前面的條件不滿足是，才進(jìn)行第二種情況的判斷。第 種情況_x.first < _y.first 不成立，即 x.first >= _y.first 成立，在這個(gè)條件下，我們來(lái)分 析

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 )等價(jià)于 _x.first = _y.first ,也就是說(shuō)，第二種情況是在key相等的情況下，比較兩者的 value (second )。這里比較令人費(fèi)解

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

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