Associative container

Topik ini membahas associative container terurut pada pustaka standar, yaitu std::set, std::map, std::multiset, dan std::multimap. Keempatnya mengelola elemen berdasarkan kunci yang selalu terurut naik, sehingga pencarian, penyisipan, dan penghapusan berjalan dalam $O(\log n)$. Pembahasan mencakup karakter masing-masing container, contoh pemakaiannya, serta jaminan urutan yang membuat iterasinya deterministik dan aman dicetak apa adanya.

Empat container terurut#

Keluarga ini terbagi menurut dua pertanyaan, yaitu apakah kunci menyimpan nilai pendamping dan apakah kunci yang sama boleh muncul lebih dari satu kali.

std::map dan std::set dideklarasikan melalui header <map> dan <set>, sedangkan std::multimap dan std::multiset berada di header yang sama. Setiap elemen std::map adalah std::pair dengan kunci yang bersifat const, sehingga kunci tidak boleh diubah setelah elemen terbentuk. Kunci ganda pada multiset dan multimap berarti dua entri boleh memakai kunci yang sama persis. Kedua entri tersebut tetap tersimpan sebagai elemen yang berbeda dan terhitung oleh count().

Secara internal, implementasi pustaka yang lazim seperti libstdc++ menyusun elemen dalam pohon merah-hitam, yaitu pohon pencarian seimbang yang tingginya tumbuh sebanding $O(\log n)$. Karena penyusunannya mengikuti kunci, urutan iterasi selalu naik menurut pembanding kunci, secara default std::less<Key>, dan urutan itu tidak bergantung pada urutan penyisipan. Pembanding lain dapat diberikan sebagai parameter template kedua apabila urutan lain diperlukan.

map: memetakan kunci ke nilai#

std::map<std::string, int> menyimpan pasangan kunci dan nilai, dan operator [] menyediakan dua akses sekaligus, yaitu membaca nilai kunci yang sudah ada dan menyisipkan kunci baru dengan nilai awal. Contoh berikut mencatat stok gudang berupa banyaknya sak barang, kemudian mencetak seluruhnya dan memeriksa satu barang yang belum tercatat.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stok;
    stok["beras"] = 24;
    stok["minyak"] = 10;
    stok["gula"] = 15;
    stok["beras"] += 6;              // kunci yang sudah ada diperbarui

    std::cout << "Isi gudang (" << stok.size() << " jenis):\n";
    for (const auto& [barang, jumlah] : stok) {
        std::cout << "- " << barang << ": " << jumlah << " sak\n";
    }

    auto cari = stok.find("telur");
    if (cari == stok.end()) {
        std::cout << "Telur belum tercatat\n";
    }
    return 0;
}

Isi gudang (3 jenis):
- beras: 30 sak
- gula: 15 sak
- minyak: 10 sak
Telur belum tercatat

Keluaran menampilkan barang dalam urutan abjad, bukan urutan penyisipan, karena pohon menyusun elemen menurut kunci. Perulangan dengan structured binding const auto& [barang, jumlah] memisahkan kunci dan nilai dari pasangannya tanpa penyalinan. Pemeriksaan keberadaan kunci dilakukan dengan find(), yang mengembalikan iterator, dan pembandingan terhadap end() adalah cara standar menyatakan bahwa kunci tidak ada.

set: kumpulan kunci unik#

std::set menyimpan kunci tanpa nilai pendamping dan menolak duplikat secara diam-diam, sehingga cocok untuk kumpulan keanggotaan seperti daftar hadir. Member function insert() mengembalikan sepasang nilai berisi iterator dan keberhasilan penyisipan, count() mengembalikan satu bila kunci ada dan nol bila tidak, sedangkan find() memberikan iterator bagi kunci yang dicari. Contoh berikut mencatat kehadiran dan mencoba menyisipkan satu nama yang sudah ada.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> hadir;
    hadir.insert("Ali");
    hadir.insert("Citra");
    hadir.insert("Ali");             // duplikat diabaikan, set tidak bertambah

    std::cout << "Banyak nama unik: " << hadir.size() << '\n';

    std::cout << "Daftar hadir:";
    for (const std::string& nama : hadir) {
        std::cout << ' ' << nama;
    }
    std::cout << '\n';

    std::cout << "Budi hadir? "
              << (hadir.count("Budi") == 1 ? "ya" : "tidak") << '\n';
    return 0;
}

Banyak nama unik: 2
Daftar hadir: Ali Citra
Budi hadir? tidak

Penyisipan kedua untuk nama Ali tidak menambah ukuran set, karena kunci duplikat diabaikan. Daftar hadir tetap tercetak terurut naik menurut abjad tanpa pengurutan eksplisit, dan pemeriksaan keanggotaan lewat count() berjalan dalam $O(\log n)$, jauh lebih murah daripada menelusuri seluruh daftar yang berjalan $O(n)$.

multiset dan multimap#

std::multimap melonggarkan aturan keunikan, yaitu satu kunci boleh membawa banyak entri, sehingga satu hari jadwal boleh memuat beberapa petugas. Karena operator [] memerlukan kunci yang unik, multimap menyisipkan entri lewat insert(). Pembacaan seluruh entri satu kunci dikerjakan lewat equal_range(), yang mengembalikan sepasang iterator berupa awal dan akhir rentang kunci tersebut.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> piket;
    piket.insert({"Senin", "Ali"});
    piket.insert({"Senin", "Budi"});
    piket.insert({"Rabu", "Citra"});
    piket.insert({"Jumat", "Dewi"});

    std::cout << "Petugas hari Senin:\n";
    auto jangkauan = piket.equal_range("Senin");
    for (auto it = jangkauan.first; it != jangkauan.second; ++it) {
        std::cout << "- " << it->second << '\n';
    }

    std::cout << "Banyak entri Senin: " << piket.count("Senin") << '\n';
    return 0;
}

Petugas hari Senin:
- Ali
- Budi
Banyak entri Senin: 2

std::multiset bersifat serupa untuk kunci tanpa nilai, yaitu menerima duplikat dan memberikan banyaknya kemunculan lewat count(). Elemen duplikatnya selalu berdampingan dalam urutan iterasi, sehingga equal_range() dan lower_bound() beserta upper_bound() menjadi cara standar mengambil satu kelompok kunci yang sama sekaligus.

Urutan dan kompleksitas#

Jaminan urutan inilah pembeda terpenting dari unordered container. Iterasi atas map, set, multiset, dan multimap selalu menghasilkan kunci secara naik, sehingga program yang mencetak isi container terurut memperoleh keluaran yang sama di pustaka mana pun. Jaminan tersebut berguna ketika hasil perlu ditampilkan kepada pengguna, ketika dua potong program dibandingkan, dan ketika keluaran uji otomatis perlu stabil.

Kompleksitas operasi dasarnya adalah $O(\log n)$ untuk pencarian, penyisipan, dan penghapusan, karena tinggi pohon seimbang tumbuh logaritmik terhadap banyaknya elemen. Penelusuran seluruh elemen tetap $O(n)$. Satu jaminan lain yang sering diperlukan adalah kestabilan, yaitu penyisipan tidak pernah membatalkan iterator, referensi, maupun pointer yang menunjuk elemen yang sudah ada, karena pohon hanya memperbaiki tautan antar-simpul dan tidak memindahkan elemen dalam memori.

Konsekuensi pemilihan ini perlu ditimbang terhadap kebutuhan. Apabila urutan kunci tidak diperlukan dan pencarian terjadi sangat sering, unordered container menawarkan rata-rata $O(1)$ dengan biaya urutan yang tak terduga, sebagaimana dibahas pada topik unordered container. Apabila urutan terurut dibutuhkan, baik untuk keluaran maupun untuk operasi seperti lower_bound(), associative container terurut adalah pilihan yang tepat.

Kesalahan umum#

Tiga kesalahan berikut sering muncul pada pemakaian associative container terurut.

1. Membaca kunci yang belum ada lewat operator []. Pada std::map, ekspresi stok["telur"] untuk kunci yang belum tercatat justru menyisipkan elemen baru bernilai nol, sehingga ukuran map berubah tanpa disengaja. Gunakan find() untuk membaca, atau at() yang melempar std::out_of_range bila kunci tidak ada.
2. Memakai operator [] pada set, multiset, dan multimap. Ketiganya tidak menyediakannya, karena set tidak mempunyai nilai pendamping dan multimap tidak menjamin keunikan kunci. Penyisipannya dikerjakan lewat insert().
3. Mengharapkan urutan iterasi mengikuti urutan penyisipan. Penyusunannya menurut kunci, sehingga entri yang disisipkan pertama belum tentu tercetak pertama. Apabila urutan penyisipan memang diperlukan, simpan pasangan nilainya di std::vector dan gunakan map hanya sebagai indeks.

Ringkasan#

• Associative container terurut terdiri atas set, map, multiset, dan multimap, yang dibedakan menurut ada tidaknya nilai pendamping dan kebolehan kunci ganda.
• Implementasinya berbasis pohon seimbang, sehingga pencarian, penyisipan, dan penghapusan berjalan dalam $O(\log n)$, sedangkan iterasinya selalu menghasilkan kunci secara naik dan deterministik.
• Operator [] hanya tersedia pada map dan menyisipkan elemen bila kunci belum ada, sedangkan pemeriksaan keberadaan yang aman memakai find(), count(), atau at().

Referensi#

• std::map — cppreference.com — Dokumentasi map beserta jaminan kompleksitas dan sifat kuncinya.
• std::set — cppreference.com — Dokumentasi set beserta insert dan kebijakan kunci uniknya.
• std::multimap — cppreference.com — Dokumentasi multimap beserta equal_range dan count.
• std::multiset — cppreference.com — Dokumentasi multiset yang menerima kunci duplikat.
• Associative containers — libstdc++ manual, GNU — Penjelasan associative container menurut implementasi GNU C++.