C++中地圖按鍵排序實現範例

2022-07-20 22:00:12

正文

一個地圖由鍵/值對組成。每一對都是一個元素。一個地圖中的所有鍵都是唯一的。一個地圖可以按鍵進行排序。排序可以是升序或降序。升序是預設的。地圖中的排序並不總是直接的。它需要一個比較函數物件。如果比較物件被忽略了，就會發生預設的排序。

如果鍵是恆定的指向字元的指標，地圖就會按鍵的指標排序，而不是按鍵的字串字數排序。這幾乎不是任何人想要的。考慮以下水果的鍵/值對和它們的外部顏色。

    "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;
    }

輸出結果是。