Tutorial Struktur Data Map Pada C++

Artikel ini adalah rangkaian tutorial struktur data pada C++ untuk persiapan Kompetisi Sains Nasional bidang Komputer 2020. Pada artikel ini kita akan bahas Struktur Data Map. Cek juga artikel sebelumnya tentang struktur data Vector.

TL;DR; Bagi yang agak pingin cepat, bisa baca tutorial di codingannya langsung di link berikut ini https://ideone.com/1Y7b2b

Apa itu struktur data map?

Untuk memudahkan membayangkan, kita bisa lihat langsung contoh bagaimana pemakaian Struktur data Map ini. Map terasa mirip dengan array namun dengan index yang memungkinkan untuk berupa tipe data selain integer (mirip dengan dictionary di Python). Pada map, indeks tersebut diberi nama “key”.

Di C++ ada 2 jenis struktur data map, yakni std::map dan std::unordered_map. Kedua struktur data tersebut secarafungsi bisa dibilang hampir sama, yang membedakan adalah implementasi dibaliknya. Pada std::map digunakan Self-Balancing Tree khususnya Red-Black Tree, sedangkan pada std::unordered_map digunakan hash table.

Perbedaan tersebut memunculkan dua karakteristik unik (sesuai namanya). Pada std::map, data disimpan secara terurut menaik berdasar key nya, sedangkan unordered map tidak terurut. Detailnya bisa dicek di bagian “Iterasi” di bawah.

Inisialisasi Map

Untuk menggunakan map ataupun unordered map, pertama-tama kita harus mengimport terlebih dahulu library yang sesuai

#include <map>
#include <unordered_map>
using namespace std;

Lalu untuk membuat variabelnya kita perlu menentukan tipe data dari key dan valuenya dengan format `<key, value>`

map<string, int> m;
unorederd_map<string, int> u;

Pada contoh di atas berarti kita membuat variabel m yang merupakan Map dan variabel u yang bertipe unordered map dengan key bertipe string dan value betipe integer.

Insert & Search

Proses penambahan nilai atau insert pada map ataupun unordered map terbilang sama dengan array. Kita cukup menuliskan indeksnya yang berupa key lalu memberi nilai integer sebagai valuenya.

m["candi"] = 17;
u["budi"] = 29;

Begitu juga untuk mendapatkan nilainya, kita cukup memanggil key yang sesuai.

cout << "'candi' value from m: "<< m["candi"] << endl;

Iterasi

Proses iterasi atau menelusuri isi map tentu agak berbeda dengan array karena tidak ada indeks angka. Oleh karenanya untuk iterasi struktur data map kita membutuhkan sebuah variabel spesial yang disebut iterator. Iterator ini memiliki tipe yang harus sama dengan struktur data yang ingin diiterasi. Cara membuatnya seperti ini

map<string, int>::iterator im; // iterator untuk m
unordered_map<string, int>::iterator iu; // iterator untuk u

Lalu proses iterasi dilakukan seperti berikut (prosesnya sama juga untuk unordered map):

for(im=m.begin();im!=m.end();im++){
    cout << "key: " << im->first << endl;
    cout << "value: " << im->second << endl;
}

Silakan cek kode lengkapnya di Ideone ini. Jika di-outputkan akan tampak ketika kita mengiterasi variabel m dan mengoutputkan hasilnya, datanya akan terurut berdasarkan key-nya. Sedangkan untuk unordered map data tidak terurut sama sekali, bahkan bisa berbeda dengan urutan kita saat memasukkan.

// Iterasi data map
key: adi,  value: 18
key: budi,  value: 29
key: candi,  value: 17

// Iterasi data unordered_map
key: adi,  value: 18
key: candi,  value: 17
key: budi,  value: 29

Contoh latihan

About the author

Rian Adam

Lecturer at Universitas Islam Indonesia; Machine Learning Enthusiast

View all posts

Leave a Reply