Container sekuensial menjaga urutan kedatangan elemen; std::set menjaga urutan yang berbeda: urutan nilai itu sendiri. Set adalah koleksi yang menjamin dua hal sekaligus — tidak ada duplikat, dan isi selalu terurut menaik — dengan biaya penyisipan, pencarian, dan penghapusan O(log n). Di balik layar ia dibangun sebagai balanced binary search tree (implementasi umumnya red-black tree), sehingga setiap kali kita berjalan dari begin() ke end(), data keluar dalam urutan naik tanpa perlu std::sort. Saudaranya, std::multiset, melonggarkan satu aturan: nilai yang sama boleh muncul beberapa kali. Chapter ini mengoperasikan keduanya sekaligus memperlihatkan konsekuensi terurutnya.

set: Unik dan Terurut Sejak Awal #

Cara paling cepat memahami std::set adalah memberinya data berantakan dan melihat apa yang keluar. Program berikut memuat tujuh nilai yang banyak duplikatnya, lalu menguji operasi inti set satu per satu.

cpp 
#include <iostream>  // std::cout
#include <set>       // std::set dan std::multiset
#include <string>    // std::string
#include <vector>    // std::vector sebagai sumber data

int main() {
    std::vector<int> mentah = {42, 17, 42, 8, 17, 99, 8};

    // set dari rentang: duplikat dibuang otomatis, isi langsung terurut
    std::set<int> unik(mentah.begin(), mentah.end());
    std::cout << "Isi set           :";
    for (int x : unik) std::cout << ' ' << x;
    std::cout << "\n";
    std::cout << "Ukuran            : " << unik.size() << "\n";

    // insert nilai yang sudah ada: set menolak, ukuran tak berubah
    auto hasil = unik.insert(17);
    std::cout << "insert(17) lagi   : berhasil="
              << (hasil.second ? "ya" : "tidak") << "\n";
    std::cout << "Ukuran setelahnya : " << unik.size() << "\n";

    // count: 1 bila ada, 0 bila tidak (set tidak menyimpan duplikat)
    std::cout << "count(42)         : " << unik.count(42) << "\n";
    std::cout << "count(50)         : " << unik.count(50) << "\n";

    // erase berdasarkan nilai; find mengembalikan iterator (end() = tidak ada)
    unik.erase(8);
    std::cout << "Setelah erase(8)  :";
    for (int x : unik) std::cout << ' ' << x;
    std::cout << "\n";
    std::cout << "find(99) ketemu?  : "
              << (unik.find(99) != unik.end() ? "ya" : "tidak") << "\n";

    // kunci string ikut terurut menurut urutan leksikografis
    std::set<std::string> buah = {"mangga", "apel", "jeruk", "durian"};
    std::cout << "set string        :";
    for (const std::string& b : buah) std::cout << ' ' << b;
    std::cout << "\n";

    // multiset: duplikat diperbolehkan
    std::multiset<int> dupe(mentah.begin(), mentah.end());
    std::cout << "multiset size     : " << dupe.size() << "\n";
    std::cout << "multiset count(17): " << dupe.count(17) << "\n";
    std::cout << "multiset count(99): " << dupe.count(99) << "\n";

    return 0;
}

Output yang Dihasilkan:

text 
Isi set           : 8 17 42 99
Ukuran            : 4
insert(17) lagi   : berhasil=tidak
Ukuran setelahnya : 4
count(42)         : 1
count(50)         : 0
Setelah erase(8)  : 17 42 99
find(99) ketemu?  : ya
set string        : apel durian jeruk mangga
multiset size     : 7
multiset count(17): 2
multiset count(99): 1

Mari kita bedah:

  1. Baris 10 (std::set<int> unik(...)): konstruktor menerima sepasang iterator — tujuh nilai masuk, empat yang keluar. Duplikat 42, 17, dan 8 dibuang secara diam-diam, dan iterasi menghasilkan 8 17 42 99 tanpa satu baris kode pengurutan pun.
  2. Baris 17-19 (unik.insert(17)): kembalian insert adalah std::pair yang anggota keduanya berbunyi: iterator ke elemen (lama atau baru) dan tanda berhasil atau tidak. Karena 17 sudah ada, hasil.second bernilai false dan ukuran tetap 4. Pasangan kembalian semacam ini kita bongkar lebih nyaman dengan structured bindings pada Chapter std::pair dan std::tuple.
  3. Baris 23-24 (count): pada set, count hanya bisa mengembalikan 1 atau 0 — duplikat tidak diizinkan, sehingga keberadaan nilai cukup ditanyakan dengan angka satu digit.
  4. Baris 27 (unik.erase(8)): menghapus berdasarkan nilai langsung, tidak perlu iterator. Pencariannya sendiri memanfaatkan struktur pohon, jadi tetap O(log n).
  5. Baris 31-32 (find): find mengembalikan iterator ke elemen; bila tidak ditemukan, kembalian sama dengan end(). Pola find(x) != set.end() adalah cara paling idiomatik menanyakan keberadaan.
  6. Baris 35-38 (set string): pengurutan mengikuti urutan operator< tipe kuncinya; untuk string berarti urutan leksikografis — apel durian jeruk mangga.
  7. Baris 41-44 (multiset): size kembali 7 karena duplikat dipertahankan, dan count(17) kini bisa melampaui satu. Multiset dipakai ketika frekuensi bernilai: contohnya menghitung berapa kali suatu nomor muncul.

Karakteristik yang Perlu Diketahui #

Dua sifat std::set sering menjadi kejutan bagi pemula. Pertama, elemen di dalamnya tidak bisa diubah lewat iterator: compiler menolak *it = 99 karena mengubah nilai tengah pohon bisa merusak urutannya. Cara yang benar adalah menghapus nilai lama lalu menyisipkan nilai baru. Kedua, std::set tidak hanya unik tetapi juga selalu siap dibaca urut — kualitas yang kita bayar dengan O(log n) pada setiap operasi.

Pencarian O(log n) memang cepat, tetapi ada tipe set yang berani berjanji O(1) rata-rata dengan cara berbeda total — hash set. Itulah std::unordered_set yang kita bedah dua chapter lagi.

Rujukan resmi: cppreference — std::set , cppreference — std::multiset , cppreference — set::insert .