Peta C++ diurutkan berdasarkan Kunci

Sebuah peta terdiri dari pasangan kunci/nilai. Setiap pasangan adalah elemen. Semua kunci dalam peta adalah unik. Peta dapat diurutkan berdasarkan kunci. Pengurutan dapat dilakukan secara Ascending atau Descending. Naik adalah default. Penyortiran dalam peta tidak selalu mudah. Dibutuhkan objek fungsi perbandingan. Jika objek perbandingan diabaikan, pengurutan default terjadi.

Jika kuncinya adalah penunjuk konstan ke karakter, peta diurutkan berdasarkan penunjuk kunci, dan bukan oleh literal string kunci. Ini hampir tidak diinginkan oleh siapa pun. Perhatikan pasangan kunci/nilai berikut dari buah-buahan dan warna luarnya:

    "plum" => "purple"
    "blackberry" => "dark blue-black"
    "watermelon" => "green"
    "apricot", => "orange"
     "papaya" => "orange"
    "banana" => "yellow"

Buah adalah kuncinya, dan warna adalah nilainya. Daftar elemen ini (pasangan kunci/nilai) tidak diurutkan. Program berikut membuat peta daftar ini apa adanya dan menampilkannya apa adanya, tidak diurutkan berdasarkan literal string:

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

Outputnya adalah:

    plum => purple
    blackberry => dark blue-black
    watermelon => green
    apricot => orange
    papaya => orange
    banana => yellow

tidak disortir oleh literal string, tetapi diurutkan berdasarkan pointer. Untuk menggunakan peta dalam program C++, pustaka peta harus disertakan dengan direktif include.

Cara lain untuk membuat peta sederhana di atas, adalah sebagai berikut:

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

Outputnya adalah:

    plum => purple
    blackberry => dark blue-black
    watermelon => green
    apricot => orange
    papaya => orange
    banana => yellow

tidak disortir oleh string literal, meskipun diurutkan berdasarkan pointer. Jika kunci adalah bilangan bulat, output akan diurutkan berdasarkan kunci. Dalam praktiknya, kunci dari banyak peta adalah literal string. Artikel ini menjelaskan bagaimana kunci string literal dapat mengurutkan peta.

Isi Artikel

Urutkan Selama Penciptaan

Template lengkap untuk konstruksi peta adalah:

    template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key, T>>> class map;

Kelas, Bandingkan dan Pengalokasi, memiliki nilai default. Artinya, mereka memiliki spesialisasi default, yang tidak harus diketik dalam deklarasi peta (instantiations). Yang menarik di sini adalah kelas perbandingan. Nama kelasnya adalah Bandingkan, dan spesialisasi defaultnya adalah “kurang<Kunci>”. “kurang<Kunci” berarti mengurutkan dalam urutan menaik. Pilihan lain adalah “lebih besar<Key>”, yang berarti urutkan secara menurun.

Peta biasanya dibuat diurutkan berdasarkan kunci selama pembuatan. Jika kuncinya adalah const char*, maka pointer ke string literal yang dikutip akan diurutkan, bukan teks literal. Untuk memiliki string sebagai kunci yang diurutkan selama pembuatan, string harus literal dari objek string yang dipakai dari kelas string. Ini berarti perpustakaan string harus disertakan, serta perpustakaan peta.

Membuat Ascending

Dalam program berikut, peta dibuat, diurutkan naik:

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

Outputnya adalah:

    apricot => orange
    banana => yellow
    blackberry => dark blue-black
    papaya => orange
    plum => purple
    watermelon => green

Bahkan jika less<string> dihilangkan dari template, pengurutan akan tetap naik karena less adalah defaultnya.

Membuat Menurun

Untuk membuat peta, sehingga diurutkan dalam urutan menurun berdasarkan kunci, spesialisasi Bandingkan harus dikodekan. Program berikut menggambarkan hal ini:

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

Outputnya adalah:

    watermelon => green
    plum => purple
    papaya => orange
    blackberry => dark blue-black
    banana => yellow
    apricot => orange

Memproduksi Rentang Menurun

Rentang peta dapat diproduksi dalam urutan menurun. Ini melibatkan pembuatan peta kedua, yang merupakan rentang dari peta pertama. Program berikut menggambarkan hal ini:

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

Outputnya adalah:

    plum => purple
    papaya => orange
    blackberry => dark blue-black
    banana => yellow

Objek peta pertama memiliki enam elemen yaitu:

    apricot => orange
    banana => yellow
    blackberry => dark blue-black
    papaya => orange
    plum => purple
    watermelon => green

Kisaran yang dipertimbangkan adalah:

    banana => yellow
    blackberry => dark blue-black
    papaya => orange
    plum => purple
    watermelon => green

Dalam kode, “itB++” menunjuk ke {“pisang”, “kuning”} dan “itE–” menunjuk ke {“semangka”, “hijau”} untuk rentang. Saat menangani rentang dalam C++, elemen terakhir tidak terlibat dalam manipulasi. Dan output memiliki empat elemen dengan {“semangka”, “hijau”} dihilangkan.

Spesialisasi parameter template Bandingkan peta kedua lebih besar<string>. Jika kurang<string> atau dihilangkan, rentang akan menghasilkan urutan menaik.

Membandingkan dua Elemen dengan Kunci

key_compare key_comp() const

Fungsi anggota ini mengembalikan copyan objek perbandingan yang digunakan oleh wadah peta untuk membandingkan kunci. Objek perbandingan adalah objek fungsi. Dibutuhkan dua kunci sebagai argumen dan mengembalikan true jika kunci kiri kurang dari kanan. Dengan itu, segmen kode harus:

        key_compare kc = mp.key_comp();
        bool bl = kc("watermelon", "apricot");

key_compare tidak dikenali oleh kompiler. Menghilangkan key_compare di segmen kode ini, dengan mengganti kc dalam pernyataan kedua, menghasilkan:

        bool bl = mp.key_comp()("watermelon", "apricot");

Program berikut mengilustrasikan useran 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;
    }

Outputnya adalah 0 untuk false.

Masalah sebenarnya dengan segmen kode di atas adalah, namespace untuk key_compare, tidak diungkapkan dengan baik. Jika segmen itu,

        map<string, const char*>::key_compare kc = mp.key_comp();
        bool bl = kc("watermelon", "apricot");

Itu akan berhasil (diterima oleh kompiler).

nilai_bandingkan nilai_comp() const

Fungsi anggota ini mirip dengan key_comp(). Catatan: di sini bukan nilai dari pasangan kunci/nilai yang dimaksud; itu adalah elemen dari pasangan kunci/nilai. Jadi, dua argumen untuk objek fungsi value_compare adalah elemen iterator. Program berikut menggunakan value_comp(), dalam membandingkan elemen pertama dan terakhir, {“apricot”, “orange”} dan {“semangka”, “hijau”} :

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

Outputnya adalah 1, untuk benar. Iterator itB dan itE didereferensi untuk memiliki elemennya, dengan operator tipuan.

Penyortiran Peta yang Dibuat dengan Daftar Penginisialisasi

Dalam program berikut, di mana pengurutan menurun, kuncinya adalah objek string, yang dibuat dari kelas string:

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

Outputnya adalah:

    watermelon => green
    plum => purple
    papaya => orange
    blackberry => dark blue-black
    banana => yellow
    apricot => orange

Kesimpulan

Peta dibuat diurutkan berdasarkan kunci, menaik. Ascending adalah urutan default. Untuk menurunkannya, tambahkan spesialisasi parameter template, lebih besar sebagai argumen ketiga, ke dalam daftar argumen template. Catatan: jika kuncinya adalah string, mereka harus diinstansiasi dari kelas string, seperti yang diilustrasikan di atas. Kunci string sebagai const-char* atau char-arr[], diakhiri dengan pointer yang diurutkan dan bukan literalnya.

Related Posts