C++中地圖按鍵排序?qū)崿F(xiàn)示例

第C++中地圖按鍵排序?qū)崿F(xiàn)示例目錄正文創(chuàng)建過(guò)程中的排序創(chuàng)建升序創(chuàng)建降序生成一個(gè)范圍的降序通過(guò)鍵比較兩個(gè)元素key_comparekey_comp()constvalue_comparevalue_comp()const對(duì)用初始化器列表創(chuàng)建的地圖進(jìn)行排序結(jié)論

正文

一個(gè)地圖由鍵/值對(duì)組成。每一對(duì)都是一個(gè)元素。一個(gè)地圖中的所有鍵都是唯一的。一個(gè)地圖可以按鍵進(jìn)行排序。排序可以是升序或降序。升序是默認(rèn)的。地圖中的排序并不總是直接的。它需要一個(gè)比較函數(shù)對(duì)象。如果比較對(duì)象被忽略了，就會(huì)發(fā)生默認(rèn)的排序。

如果鍵是恒定的指向字符的指針，地圖就會(huì)按鍵的指針排序，而不是按鍵的字符串字?jǐn)?shù)排序。這幾乎不是任何人想要的?？紤]以下水果的鍵/值對(duì)和它們的外部顏色。

"plum"="purple"

"blackberry"="darkblue-black"

"watermelon"="green"

"apricot",="orange"

"papaya"="orange"

"banana"="yellow"

水果是鍵，而顏色是值。這個(gè)元素列表（鍵/值對(duì)）是沒(méi)有排序的。下面的程序創(chuàng)建了這個(gè)列表的映射，并按原樣顯示，沒(méi)有按字符串字面排序。

#includeiostream

#includemap

usingnamespacestd;

intmain()

mapconstchar*,constchar*

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

for(mapconstchar*,constchar*::iteratorit=mp.begin();it!=mp.end();it++)

coutit-first"="it-secondendl;

return0;

輸出結(jié)果是：

plum=purple

blackberry=darkblue-black

watermelon=green

apricot=orange

papaya=orange

banana=yellow

未按字符串字面排序，但按指針排序。要在C++程序中使用地圖，必須用include指令來(lái)包含地圖庫(kù)。

創(chuàng)建上述簡(jiǎn)單地圖的另一種方法是如下。

#includeiostream

#includemap

usingnamespacestd;

intmain()

mapconstchar*,constchar*mp({{"plum","purple"},{"blackberry","darkblue-black"},{"watermelon","green"},{"apricot","orange"},{"papaya","orange"},{"banana","yellow"}});

for(mapconstchar*,constchar*::iteratorit=mp.begin();it!=mp.end();it++)

coutit-first"="it-secondendl;

return0;

輸出結(jié)果是：

plum=purple

blackberry=darkblue-black

watermelon=green

apricot=orange

papaya=orange

banana=yellow

未按字符串字面排序，但按指針排序。如果鍵值是整數(shù)，輸出將按鍵值排序。在實(shí)踐中，許多地圖的鍵是字符串字面。這篇文章解釋了字符串字面的鍵是如何對(duì)地圖進(jìn)行排序的。

創(chuàng)建過(guò)程中的排序

構(gòu)建地圖的完整模板是：

templateclassKey,classT,classCompare=lessKey,classAllocator=allocatorpairconstKey,Tclassmap;

類(lèi)，Compare和Allocator，有默認(rèn)值。也就是說(shuō)，它們有默認(rèn)的專(zhuān)業(yè)化，不必在map聲明（實(shí)例化）中進(jìn)行類(lèi)型化。這里要關(guān)注的是比較類(lèi)。這個(gè)類(lèi)的名字是Compare，默認(rèn)的特殊化是less。lessKey意味著按升序排序。另一個(gè)選項(xiàng)是greater，意思是降序排序。

一個(gè)地圖在創(chuàng)建時(shí)通常是按鍵值排序的。如果鍵是constchar*，那么指向引號(hào)字面字符串的指針將被排序，而不是字面文本。要在創(chuàng)建過(guò)程中把字符串作為鍵進(jìn)行排序，字符串必須是由字符串類(lèi)實(shí)例化的字符串對(duì)象的字面意思。這意味著必須包括字符串庫(kù)和地圖庫(kù)。

創(chuàng)建升序

在下面的程序中，地圖被創(chuàng)建，升序排序。

#includeiostream

#includemap

#includestring

usingnamespacestd;

intmain()

mapstring,constchar*,lessstringmp;

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

for(mapstring,constchar*::iteratorit=mp.begin();it!=mp.end();it++)

coutit-first"="it-secondendl;

return0;

輸出結(jié)果是：

apricot=orange

banana=yellow

blackberry=darkblue-black

papaya=orange

plum=purple

watermelon=green

即使模板中省略了less，排序仍然會(huì)是升序的，因?yàn)閘ess是默認(rèn)的。

創(chuàng)建降序

為了創(chuàng)建一個(gè)地圖，使其按鍵的降序排序，必須對(duì)比較專(zhuān)業(yè)化進(jìn)行編碼。下面的程序說(shuō)明了這一點(diǎn)。

#includeiostream

#includemap

#includestring

usingnamespacestd;

intmain()

mapstring,constchar*,greaterstringmp;

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

for(mapstring,constchar*::iteratorit=mp.begin();it!=mp.end();it++)

coutit-first"="it-secondendl;

return0;

輸出結(jié)果是：

watermelon=green

plum=purple

papaya=orange

blackberry=darkblue-black

banana=yellow

apricot=orange

生成一個(gè)范圍的降序

一個(gè)地圖的范圍可以按降序產(chǎn)生。這涉及到創(chuàng)建第二個(gè)地圖，它是第一個(gè)地圖的一個(gè)范圍。下面的程序說(shuō)明了這一點(diǎn)。

#includeiostream

#includemap

#includestring

usingnamespacestd;

intmain()

mapstring,constchar*

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

mapstring,constchar*::iteratoritB=mp.begin();

itB++;

mapstring,constchar*::iteratoritE=mp.end();

itE--;

mapstring,constchar*,greaterstringmpR(itB,itE);

for(mapstring,constchar*::iteratorit=mpR.begin();it!=mpR.end();it++)

coutit-first"="it-secondendl;

return0;

輸出結(jié)果是：

plum=purple

papaya=orange

blackberry=darkblue-black

banana=yellow

第一個(gè)地圖對(duì)象有六個(gè)元素，分別是

apricot=orange

banana=yellow

blackberry=darkblue-black

papaya=orange

plum=purple

watermelon=green

考慮的范圍是：

banana=yellow

blackberry=darkblue-black

papaya=orange

plum=purple

watermelon=green

在代碼中，itB++指向{香蕉，黃色}，itE-指向{西瓜，綠色}的范圍。在C++中處理一個(gè)范圍時(shí)，最后一個(gè)元素不參與操作。于是，輸出有四個(gè)元素，{西瓜，綠}被省略了。

第二個(gè)map的Compare模板參數(shù)的特化是greater。如果它是less或者省略，那么這個(gè)范圍會(huì)導(dǎo)致升序。

通過(guò)鍵比較兩個(gè)元素

key_comparekey_comp()const

這個(gè)成員函數(shù)返回map容器用來(lái)比較鍵的比較對(duì)象的副本。比較對(duì)象是一個(gè)函數(shù)對(duì)象。它將把兩個(gè)鍵作為參數(shù)，如果左鍵小于右鍵，則返回真。有了這個(gè)，代碼段應(yīng)該是。

key_comparekc=mp.key_comp();

boolbl=kc("watermelon","apricot");

key_compare不被編譯器識(shí)別。在這個(gè)代碼段中消除key_compare，在第二條語(yǔ)句中替換掉kc，結(jié)果是。

boolbl=mp.key_comp()("watermelon","apricot");

下面的程序說(shuō)明了key_comp()的使用。

#includeiostream

#includemap

#includestring

usingnamespacestd;

intmain()

mapstring,constchar*

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

boolbl=mp.key_comp()("watermelon","apricot");

coutblendl;

return0;

輸出結(jié)果是0，表示錯(cuò)誤。

上述代碼段的真正問(wèn)題是，key_compare的命名空間沒(méi)有得到很好的表達(dá)。如果這段代碼是

mapstring,constchar*::key_comparekc=mp.key_comp();

boolbl=kc("watermelon","apricot");

它本來(lái)可以工作（被編譯器接受）。

value_comparevalue_comp()const

這個(gè)成員函數(shù)與key_comp()類(lèi)似。注意：這里指的不是鍵/值對(duì)的值，而是鍵/值對(duì)的元素。所以，value_compare函數(shù)對(duì)象的兩個(gè)參數(shù)是迭代器元素。下面的程序使用value_comp()，在比較第一個(gè)和最后一個(gè)元素，{杏，橙}和{西瓜，綠}:

#includeiostream

#includemap

#includestring

usingnamespacestd;

intmain()

mapstring,constchar*,lessstringmp;

mp["plum"]="purple";

mp["blackberry"]="darkblue-black";

mp["watermelon"]="green";

mp["apricot"]="orange";

mp["papaya"]="orange";

mp["banana"]="yellow";

mapstring,constchar*::iteratoritB=mp.begin();

mapstring,constchar*::iteratoritE=mp.end();

itE--;

mapstring,constchar*::value_comparevc=mp.value_comp();

boolbl=vc(*itB,*itE);

coutblendl;

return0;

輸出是1，表示真。迭代器itB和itE被解讀為有它們的元素，用的是嵌套運(yùn)算符。

對(duì)用初始化器列表創(chuàng)建的地圖進(jìn)行排序

在下面的程序中，排序是降序的，鍵是字符串對(duì)象，從字符串類(lèi)實(shí)例化出來(lái)。

#includeiostream

#includestring

#inc