C++中地圖按鍵排序實現示例
正文
一個地圖由鍵/值對組成。每一對都是一個元素。一個地圖中的所有鍵都是唯一的。一個地圖可以按鍵進行排序。排序可以是升序或降序。升序是默認的。地圖中的排序並不總是直接的。它需要一個比較函數對象。如果比較對象被忽略瞭,就會發生默認的排序。
如果鍵是恒定的指向字符的指針,地圖就會按鍵的指針排序,而不是按鍵的字符串字數排序。這幾乎不是任何人想要的。考慮以下水果的鍵/值對和它們的外部顏色。
"plum" => "purple" "blackberry" => "dark blue-black" "watermelon" => "green" "apricot", => "orange" "papaya" => "orange" "banana" => "yellow"
水果是鍵,而顏色是值。這個元素列表(鍵/值對)是沒有排序的。下面的程序創建瞭這個列表的映射,並按原樣顯示,沒有按字符串字面排序。
#include <iostream> #include <map> using namespace std; int main() { map<const char*, const char*> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是:
plum => purple
blackberry => dark blue-black
watermelon => green
apricot => orange
papaya => orange
banana => yellow
未按字符串字面排序,但按指針排序。要在C++程序中使用地圖,必須用include指令來包含地圖庫。
創建上述簡單地圖的另一種方法是如下。
#include <iostream> #include <map> using namespace std; int main() { map<const char*, const char*> mp({{"plum","purple"}, {"blackberry","dark blue-black"}, {"watermelon","green"}, {"apricot","orange"}, {"papaya","orange"}, {"banana","yellow"}}); for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是:
plum => purple
blackberry => dark blue-black
watermelon => green
apricot => orange
papaya => orange
banana => yellow
未按字符串字面排序,但按指針排序。如果鍵值是整數,輸出將按鍵值排序。在實踐中,許多地圖的鍵是字符串字面。這篇文章解釋瞭字符串字面的鍵是如何對地圖進行排序的。
創建過程中的排序
構建地圖的完整模板是:
template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key, T>>> class map;
類,Compare和Allocator,有默認值。也就是說,它們有默認的專業化,不必在map聲明(實例化)中進行類型化。這裡要關註的是比較類。這個類的名字是Compare,默認的特殊化是 "less"。"less<Key "意味著按升序排序。另一個選項是 "greater",意思是降序排序。
一個地圖在創建時通常是按鍵值排序的。如果鍵是const char*,那麼指向引號字面字符串的指針將被排序,而不是字面文本。要在創建過程中把字符串作為鍵進行排序,字符串必須是由字符串類實例化的字符串對象的字面意思。這意味著必須包括字符串庫和地圖庫。
創建升序
在下面的程序中,地圖被創建,升序排序。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, const char*, less<string>> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是:
apricot => orange
banana => yellow
blackberry => dark blue-black
papaya => orange
plum => purple
watermelon => green
即使模板中省略瞭less,排序仍然會是升序的,因為less是默認的。
創建降序
為瞭創建一個地圖,使其按鍵的降序排序,必須對比較專業化進行編碼。下面的程序說明瞭這一點。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, const char*, greater<string>> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是:
watermelon => green
plum => purple
papaya => orange
blackberry => dark blue-black
banana => yellow
apricot => orange
生成一個范圍的降序
一個地圖的范圍可以按降序產生。這涉及到創建第二個地圖,它是第一個地圖的一個范圍。下面的程序說明瞭這一點。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, const char*> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; map<string, const char*>::iterator itB = mp.begin(); itB++; map<string, const char*>::iterator itE = mp.end(); itE--; map<string, const char*, greater<string>> mpR(itB, itE); for (map<string, const char*>::iterator it = mpR.begin(); it != mpR.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是:
plum => purple
papaya => orange
blackberry => dark blue-black
banana => yellow
第一個地圖對象有六個元素,分別是
apricot => orange banana => yellow blackberry => dark blue-black papaya => orange plum => purple watermelon => green
考慮的范圍是:
banana => yellow blackberry => dark blue-black papaya => orange plum => purple watermelon => green
在代碼中,"itB++"指向{"香蕉","黃色"},"itE-"指向{"西瓜","綠色"}的范圍。在C++中處理一個范圍時,最後一個元素不參與操作。於是,輸出有四個元素,{"西瓜","綠"}被省略瞭。
第二個map的Compare模板參數的特化是 greater。如果它是less或者省略,那麼這個范圍會導致升序。
通過鍵比較兩個元素
key_compare key_comp() const
這個成員函數返回map容器用來比較鍵的比較對象的副本。比較對象是一個函數對象。它將把兩個鍵作為參數,如果左鍵小於右鍵,則返回真。有瞭這個,代碼段應該是。
key_compare kc = mp.key_comp(); bool bl = kc("watermelon", "apricot");
key_compare不被編譯器識別。在這個代碼段中消除key_compare,在第二條語句中替換掉kc,結果是。
bool bl = mp.key_comp()("watermelon", "apricot");
下面的程序說明瞭key_comp()的使用。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, const char*> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; bool bl = mp.key_comp()("watermelon", "apricot"); cout << bl << endl; return 0; }
輸出結果是0,表示錯誤。
上述代碼段的真正問題是,key_compare的命名空間沒有得到很好的表達。如果這段代碼是
map<string, const char*>::key_compare kc = mp.key_comp(); bool bl = kc("watermelon", "apricot");
它本來可以工作(被編譯器接受)。
value_compare value_comp() const
這個成員函數與key_comp()類似。註意:這裡指的不是鍵/值對的值,而是鍵/值對的元素。所以,value_compare函數對象的兩個參數是迭代器元素。下面的程序使用value_comp(),在比較第一個和最後一個元素,{"杏","橙"}和{"西瓜","綠"}:
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, const char*, less<string>> mp; mp["plum"] = "purple"; mp["blackberry"] = "dark blue-black"; mp["watermelon"] = "green"; mp["apricot"] = "orange"; mp["papaya"] = "orange"; mp["banana"] = "yellow"; map<string, const char*>::iterator itB = mp.begin(); map<string, const char*>::iterator itE = mp.end(); itE--; map<string, const char*>::value_compare vc = mp.value_comp(); bool bl = vc(*itB, *itE); cout << bl << endl; return 0; }
輸出是1,表示真。迭代器itB和itE被解讀為有它們的元素,用的是嵌套運算符。
對用初始化器列表創建的地圖進行排序
在下面的程序中,排序是降序的,鍵是字符串對象,從字符串類實例化出來。
#include <iostream> #include <string> #include <map> using namespace std; int main() { map<string, const char*, greater<string>> mp({{"plum","purple"}, {"blackberry","dark blue-black"}, {"watermelon","green"}, {"apricot","orange"}, {"papaya","orange"}, {"banana","yellow"}}); for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++) cout << it->first << " => " << it->second << endl; return 0; }
輸出結果是。
watermelon => green
plum => purple
papaya => orange
blackberry => dark blue-black
banana => yellow
apricot => orange
結論
一個地圖的創建是按照鍵來排序的,升序。升序是默認的順序。要想讓它降序,請在模板參數列表中加入模板參數的特殊化,即作為第三個參數的大號。註意:如果鍵值是字符串,它們必須從字符串類中實例化出來,如上圖所示。作為const-char*或char-arr[]的字符串鍵,其指針最終會被排序,而不是其字面意義。
以上就是C++中地圖按鍵排序實現示例的詳細內容,更多關於C++地圖按鍵排序的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- C++11 強類型枚舉相關總結
- Python+OpenCV實現圖片及視頻中選定區域顏色識別
- python入門turtle庫實現螺旋曲線圖的方法示例
- Python可視化學習之matplotlib內置單顏色
- 一文搞懂C++中string容器的構造及使用