Wadah Unik dan Terurut di C++

6, 10, 2, 8, 4 adalah himpunan; 2, 4, 6, 8, 10 adalah himpunan bilangan bulat yang sama, disusun dalam urutan menaik. Dalam Matematika, himpunan memiliki elemen unik (elemen berbeda), dan artinya, tidak ada elemen yang muncul lebih dari satu kali. Selanjutnya, multiset adalah himpunan, di mana elemen apa pun dapat muncul lebih dari satu kali. 6, 6, 10, 2, 2, 8, 4, 4, 4 adalah multiset. 2, 2, 4, 4, 4, 6, 6, 8, 10 adalah multiset yang sama, tetapi dengan elemen yang disusun dalam urutan menaik. Artikel ini tidak membahas multiset. Ini berkaitan dengan struktur data C++ yang disebut, set.

Peta dalam perangkat lunak seperti array, tetapi ini adalah array dengan dua kolom, bukan satu. Kolom pertama memiliki kunci dan kolom kedua memiliki nilai. Setiap baris adalah satu pasang, membuat pasangan kunci/nilai. Kunci berhubungan langsung dengan nilainya.

Contoh peta adalah 'c',30, 'b',20, 'd',30, 'e',40, 'a',10. Pasangan kunci/nilai pertama yang disisipkan di sini, adalah 'c',3, di mana 'c' adalah kuncinya dan 30 adalah nilainya. Peta ini tidak diurutkan dengan kunci. Mengurutkan peta ini dengan kunci menghasilkan 'a',10, 'b',20, 'c',30, 'd',30, 'e',40. Perhatikan bahwa mungkin ada nilai yang digandakan, tetapi bukan kunci yang digandakan. Peta yang dipesan adalah peta yang dipesan dengan kunci.

Multiset adalah set, seperti multimap adalah peta. Ini berarti ada peta dengan kunci duplikat. Contoh multimap adalah 'a',10, 'b',20, 'b',20, 'c',30, 'c',30, 'd ',30, 'e',40. Dan seperti yang dinyatakan di atas, artikel ini tidak membahas multimap, melainkan membahas struktur data C++ yang disebut, map.

Dalam C++, struktur data adalah struktur dengan properti (anggota data) dan metode (fungsi anggota). Data struktur adalah daftar; satu set adalah daftar; peta adalah daftar pasangan kunci/nilai.

Artikel ini membahas dasar-dasar himpunan dan peta dalam C++, dan untuk lebih memahami artikel ini, pembaca harus memiliki pengetahuan dasar tentang C++.

Isi Artikel:

Kelas dan Objeknya
Membuat set atau peta
Dasar-dasar Iterator
Akses Elemen untuk set dan peta
Urutan Elemen dalam satu set atau peta
Fungsi Anggota Lain yang Biasa Digunakan
Kesimpulan

Kelas dan Objeknya:

Dalam C++, himpunan, peta, dan struktur serupa lainnya disebut kontainer. Kelas adalah unit umum dengan anggota data, yang merupakan variabel, dan fungsi anggota yang terkait. Ketika anggota data diberi nilai, sebuah objek terbentuk. Namun, sebuah objek terbentuk dalam proses yang disebut, instantiation. Karena sebuah kelas dapat menghasilkan nilai yang berbeda untuk variabel anggota data yang sama, objek yang berbeda kemudian dapat diinstansiasi dari kelas yang sama.

Dalam C++, set yang tidak dapat digunakan adalah kelas, serta peta yang tidak dapat digunakan. Ketika sebuah objek diinstansiasi dari set yang tidak dapat digunakan atau peta yang tidak dapat digunakan, objek tersebut menjadi struktur data yang sebenarnya. Dengan struktur data himpunan dan peta, anggota data utama adalah daftar. Nah, himpunan dan peta membentuk sekelompok wadah yang disebut, wadah asosiatif yang dipesan. Set tidak berurutan dan peta tidak berurutan juga ada, tetapi sayangnya hal itu tidak dibahas dalam artikel ini.

Membuat set atau peta:

Membuat instance set dari kelas setnya adalah membuat set; membuat instance peta dari kelas petanya adalah membuat peta. Objek yang dibuat diberi nama pilihan programmer.

Untuk membuat satu set, program harus dimulai dengan:

#termasuk
#termasuk
menggunakan namespace std;

Perhatikan arahan “#include ”, yang mencakup set library yang memiliki kelas set dari mana struktur data set akan dipakai.

Untuk membuat peta, program harus dimulai dengan:

#termasuk
#termasuk
menggunakan namespace std;

Perhatikan arahan “#include ”, yang mencakup pustaka peta yang memiliki kelas peta dari mana struktur data peta akan dipakai.

Sintaks untuk membuat himpunan kosong adalah:

set nama objek

Contoh:

set setObj;

Contoh untuk membuat set dengan konten adalah:

set setObj(6, 10, 2, 8, 4);

Sintaks untuk membuat peta kosong adalah:

peta nama objek

Contoh:

peta petaObj;

Contoh untuk membuat peta dengan konten adalah:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Dasar-dasar Iterator:

Iterator adalah pointer yang diuraikan, yang dapat digunakan untuk melintasi daftar struktur data dari awal hingga akhir.

Fungsi anggota begin()

Fungsi anggota begin() mengembalikan iterator yang menunjuk ke elemen pertama dari daftar. Contoh berikut mengilustrasikan ini untuk himpunan:

set setObj(6, 10, 2, 8, 4);
set:: iterator iter = setObj.mulai();
cout << *iter << '\n';

Perhatikan cara begin() telah digunakan dengan setObj dan operator titik. iter adalah objek iterator yang dikembalikan. Juga, perhatikan cara mendeklarasikannya. * adalah operator tipuan. Seperti yang digunakan dengan iter, ia mengembalikan elemen pertama dari set; elemen pertama adalah 2 bukannya 6 - lihat penjelasan di bawah.

Contoh berikut mengilustrasikan penggunaan fungsi begin() untuk peta:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
peta:: iterator iter = mapObj.mulai();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Perhatikan cara begin() telah digunakan dengan mapObj dan operator titik. iter adalah objek iterator yang dikembalikan. Juga, perhatikan cara mendeklarasikannya. "pertama", seperti yang digunakan di sini, mengacu pada kunci. "kedua" mengacu pada nilai yang sesuai dengan kunci. Amati bagaimana mereka telah digunakan dengan iter untuk mendapatkan komponen elemen awal dari daftar. Elemen pertama adalah a,10 bukan c,30 - lihat penjelasan di bawah.

Fungsi anggota "begin() const"

Fungsi anggota "begin() const" mengembalikan iterator yang menunjuk ke elemen pertama dari daftar ketika deklarasi set dimulai dengan const (untuk konstan). Dalam kondisi ini, nilai dalam daftar, yang dirujuk oleh iterator yang dikembalikan, tidak dapat diubah oleh iterator. Contoh berikut mengilustrasikan penggunaannya untuk himpunan:

himpunan konstan setObj(6, 10, 2, 8, 4);
set::const_iterator iter = setObj.mulai();
cout << *iter << '\n';

Perhatikan cara begin() telah digunakan dengan setObj dan operator titik. Tidak ada "const" yang diketik tepat setelah begin(). Namun, "const" telah mendahului deklarasi. iter di sini adalah objek iterator konstan yang dikembalikan, yang berbeda dari iterator normal. Juga, perhatikan cara mendeklarasikannya. * adalah operator tipuan; seperti yang digunakan dengan iter, ia mengembalikan elemen pertama dari set. Elemen pertama adalah 2 bukannya 6 - lihat penjelasan di bawah.

Contoh berikut mengilustrasikan penggunaan fungsi "begin() const" untuk peta:

peta konstan mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
peta::const_iterator iter = mapObj.mulai();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Perhatikan cara begin() telah digunakan dengan mapObj dan operator titik. Tidak ada "const" yang diketik tepat setelah begin(). Namun, "const" telah mendahului deklarasi. iter di sini adalah objek iterator konstan yang dikembalikan, yang berbeda dari iterator normal. Juga, perhatikan cara mendeklarasikannya. "pertama", seperti yang digunakan di sini, mengacu pada kunci; "kedua", seperti yang digunakan di sini, mengacu pada nilai yang sesuai dengan kunci. Amati bagaimana mereka telah digunakan dengan iter untuk mendapatkan komponen elemen awal dari daftar. Elemen pertama adalah a,10 bukan c,30 - lihat penjelasan di bawah.

Fungsi anggota akhir ()

Fungsi anggota end() mengembalikan iterator yang menunjuk tepat setelah akhir daftar. Contoh berikut mengilustrasikan ini untuk himpunan:

set setObj(6, 10, 2, 8, 4);
set:: iterator iter = setObj.akhir();
cout << *iter << '\n';

Perhatikan cara end() telah digunakan dengan setObj dan operator titik. iter adalah objek iterator yang dikembalikan. Juga, perhatikan cara mendeklarasikannya. * adalah operator tipuan; seperti yang digunakan dengan iter, ia mengembalikan elemen +1 terakhir dari set. Di komputer penulis, elemen +1 terakhir ini adalah 5, yang tidak ada dalam daftar. Jadi, berhati-hatilah untuk tidak menggunakan elemen ini.

Contoh berikut mengilustrasikan penggunaan fungsi end() untuk peta:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
peta:: iterator iter = mapObj.akhir();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Perhatikan cara end() telah digunakan dengan mapObj dan operator titik. iter adalah objek iterator yang dikembalikan. Juga, perhatikan cara mendeklarasikannya. * adalah operator tipuan; seperti yang digunakan dengan iter, ia mengembalikan elemen +1 terakhir dari peta. Di komputer penulis, elemen +1 terakhir ini adalah ,0, yang tidak ada dalam daftar. Jadi, berhati-hatilah untuk tidak menggunakan elemen ini.

Fungsi anggota "end() const"

Fungsi anggota "end() const" mengembalikan iterator yang menunjuk tepat setelah akhir daftar ketika deklarasi set dimulai dengan const (untuk konstanta). Dalam kondisi ini, nilai dalam daftar, yang dirujuk oleh iterator yang dikembalikan, tidak dapat diubah oleh iterator. Contoh berikut mengilustrasikan penggunaannya untuk himpunan:

himpunan konstan setObj(6, 10, 2, 8, 4);
set::const_iterator iter = setObj.akhir();
cout << *iter << '\n';

Perhatikan cara end() telah digunakan dengan setObj dan operator titik. Tidak ada "const" yang diketik tepat setelah akhir (). Namun, "const" telah mendahului deklarasi. iter adalah objek iterator yang dikembalikan. Juga, perhatikan cara mendeklarasikannya. * adalah operator tipuan; seperti yang digunakan dengan iter, ia mengembalikan elemen +1 terakhir dari set.

Contoh berikut mengilustrasikan penggunaan fungsi “end() const” untuk peta:

peta konstan mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
peta::const_iterator iter = mapObj.akhir();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Perhatikan cara end() telah digunakan dengan mapObj dan operator titik. Tidak ada "const" yang diketik tepat setelah akhir (). Namun, "const" telah mendahului deklarasi. iter adalah objek iterator konstan yang dikembalikan, yang berbeda dari iterator normal. Juga, perhatikan baik-baik cara mendeklarasikannya.

Akses Elemen untuk set dan peta:

Set

Dengan set, elemen dibaca menggunakan operator tipuan. Dua elemen pertama dari suatu himpunan dibaca dalam contoh berikut:

set setObj(6, 10, 2, 8, 4);
set:: iterator iter = setObj.mulai();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

Outputnya adalah 2, kemudian diikuti oleh 4 - lihat penjelasan di bawah ini. Untuk menunjuk elemen berikutnya dari daftar, iterator bertambah.

Catatan: Sebuah elemen tidak dapat diubah menggunakan operator tipuan untuk himpunan. Misalnya, “* iter = 9;” itu tidak mungkin.

peta

Peta terdiri dari pasangan kunci/nilai. Nilai dapat dibaca menggunakan kunci yang sesuai, dan diubah menggunakan kunci yang sama. Segmen kode berikut menggambarkan hal ini:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';

Outputnya adalah:

20
55

Operator titik belum digunakan di sini. Sebaliknya, itu adalah operator tanda kurung siku, yang mengambil kunci sebagai konten, yang telah digunakan.

Urutan Elemen dalam satu set atau peta:

Elemen dapat dimasukkan ke dalam set, dalam urutan apa pun. Namun, setelah dimasukkan, himpunan mengatur ulang elemen-elemennya dalam urutan menaik. Urutan menaik adalah urutan default. Jika diperlukan urutan menurun, maka himpunan harus dideklarasikan seperti pada contoh berikut:

set > setObj(6, 10, 2, 8, 4);

Jadi, setelah jenisnya, e.g., int, untuk template, ada koma, diikuti dengan "lebih besar"” dalam kurung sudut.

Elemen dapat dimasukkan ke dalam peta dalam urutan apa pun. Namun, setelah dimasukkan, peta mengatur ulang elemennya dalam urutan menaik berdasarkan kunci (hanya) sambil mempertahankan hubungan antara setiap kunci dan nilainya. Urutan menaik adalah urutan default; jika diperlukan urutan menurun, maka peta harus dideklarasikan seperti pada contoh berikut:

peta > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Jadi, setelah pasangan tipe, e.g., "char, int", untuk template, ada koma, diikuti dengan "lebih besar"” dalam kurung sudut.

Melintasi satu set

while-loop atau for-loop dengan iterator dapat digunakan untuk melintasi set. Contoh berikut menggunakan for-loop untuk melintasi set yang telah dikonfigurasi dalam urutan menurun:

set > setObj(6, 10, 2, 8, 4);
untuk (setel:: iterator iter = setObj.mulai(); iter != setObj.akhir(); ++ itu)

cout << *iter << ";

Outputnya adalah:

10 8 6 4 2

Menaikkan iterator mengarahkannya ke elemen berikutnya.

Melintasi peta

while-loop atau for-loop dengan iterator dapat digunakan untuk melintasi peta. Contoh berikut menggunakan for-loop untuk melintasi peta yang telah dikonfigurasi dalam urutan menurun:

peta > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
untuk (peta:: iterator iter = mapObj.mulai(); iter != petaObj.akhir(); ++ itu)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Outputnya adalah:

e, 40, d, 30, c, 30, b, 20, a, 10,

Menaikkan iterator mengarahkannya ke elemen berikutnya. "pertama", dalam kode, mengacu pada kunci dan "kedua" mengacu pada nilai yang sesuai. Perhatikan bagaimana nilai-nilai ini diperoleh untuk output.

Fungsi Anggota Lain yang Biasa Digunakan:

Ukuran() Fungsi

Fungsi ini mengembalikan bilangan bulat, yang merupakan jumlah elemen dalam daftar. Tetapkan contoh:

set > setObj(6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

Outputnya adalah 5.

Contoh peta:

peta > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj.size() << '\n';

Outputnya adalah 5.

Sisipan () Fungsi

set

set tidak mengizinkan duplikat. Jadi, duplikat apa pun yang dimasukkan akan ditolak secara diam-diam. Dengan set, argumen ke fungsi insert() adalah nilai yang akan dimasukkan. Nilai dipasang ke dalam posisi, di mana urutan dalam himpunan tetap naik atau turun. Contoh:

set setObj(6, 10, 2, 8, 4);
setObj.masukkan(6);
setObj.masukkan (9);
setObj.masukkan (12);
untuk (setel:: iterator iter = setObj.mulai(); iter != setObj.akhir(); ++ itu)

cout << *iter << ";

Outputnya adalah:

2 4 6 8 9 10 12

Catatan: Fungsi anggota insert() dapat digunakan untuk mengisi himpunan kosong.

peta

peta tidak mengizinkan duplikat dengan kunci. Jadi, duplikat apa pun yang dimasukkan akan ditolak secara diam-diam. Dengan peta, argumen ke fungsi insert() adalah pasangan kunci/nilai dalam kurung kurawal. Elemen dipasang ke posisi dengan kunci, di mana urutan di peta tetap naik atau turun. Contoh:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
petaObj.masukkan('e',80);
petaObj.masukkan('f',50);
petaObj.masukkan('g',60);
untuk (peta:: iterator iter = mapObj.mulai(); iter != petaObj.akhir(); ++ itu)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Outputnya adalah:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Catatan: Fungsi anggota insert() dapat digunakan untuk mengisi peta kosong.

Fungsi kosong()

Fungsi ini mengembalikan nilai true jika daftar kosong, dan false jika sebaliknya. Tetapkan contoh:

set setObj(6, 10, 2, 8, 4);
bool ret = setObj.kosong();
cout << ret << '\n';

Outputnya adalah 0 untuk false, artinya himpunan di sini tidak kosong.

Contoh peta:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
bool ret = mapObj.kosong();
cout << ret << '\n';

Outputnya adalah 0 untuk false, artinya peta di sini tidak kosong.

Hapus() Fungsi

set

Perhatikan segmen kode berikut:

set setObj(10, 20, 30, 40, 50);
set:: iterator iter = setObj.mulai();
set::iterator itr = setObj.hapus(itu);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.hapus (itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

Outputnya adalah:

ukuran baru: 4
nilai berikutnya: 20
ukuran baru: 3
nilai berikutnya: 30

Fungsi erase() mengambil iterator yang menunjuk ke elemen sebagai argumen. Setelah menghapus elemen, fungsi erase() mengembalikan iterator yang menunjuk ke elemen berikutnya.

peta

Perhatikan segmen kode berikut:

peta mapObj('a',10,'b',20,'c',30,'d',40,'e',50);
peta:: iterator iter = mapObj.mulai();
peta::iterator itr = mapObj.hapus(itu);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.hapus (itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

Outputnya adalah:

ukuran baru: 4
pasangan nilai berikutnya: b,20
ukuran baru: 3
pasangan nilai berikutnya: c,30

Fungsi erase() mengambil iterator yang menunjuk ke elemen sebagai argumen. Setelah menghapus elemen, fungsi erase() mengembalikan iterator yang menunjuk ke elemen berikutnya.

Fungsi clear()

Fungsi clear() menghapus semua elemen dalam daftar. Tetapkan contoh:

set setObj(6, 10, 2, 8, 4);
setObj.bersih();
cout << setObj.size() << '\n';

Keluarannya 0.

contoh peta:

peta mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
petaObj.bersih();
cout << mapObj.size() << '\n';

Keluarannya 0.

Kesimpulan:

Struktur data yang ditetapkan dalam C++ adalah struktur di mana daftar elemen disimpan dalam urutan menaik secara default, atau dalam urutan menurun sesuai pilihan programmer. Semua elemen himpunan itu unik. Struktur data peta di C++ adalah struktur di mana daftarnya adalah hash dari pasangan kunci/nilai, disimpan dalam urutan menaik kunci secara default, atau dalam urutan menurun dari kunci pilihan programmer. Kuncinya juga unik, dan bisa ada nilai duplikat. Anggota data utama dari salah satu struktur adalah daftar. Salah satu struktur memiliki fungsi anggota, beberapa di antaranya umum digunakan.