std::unordered_set

std::set menjamin urutan dan pencarian O(log n). std::unordered_set menawarkan tawar-menawar yang berbeda: buang urutan, dapat kecepatan. Dengan menyimpan elemen berdasarkan nilai hash-nya, pencarian, penyisipan, dan penghapusan berlangsung O(1) rata-rata — langsung ke “laci” yang tepat tanpa menelusuri pohon. Konsekuensinya harus dipahami sejak awal: urutan iterasi unordered_set tidak ditentukan standar dan bisa berbeda antar compiler, antar versi pustaka, bahkan antar program; iterasi dua kali pada program yang sama memang memberi urutan yang sama, tetapi itu detail implementasi, bukan janji. Chapter ini memperagakan hash set, menunjukkan cara aman mencetak isinya secara deterministik, dan membandingkannya dengan std::set.

Cara Kerja Hash dalam Satu Paragraf #

std::unordered_set menghitung angka hash dari setiap elemen lewat std::hash, lalu angka itu dimodulo jumlah bucket — laci-laci penyimpanan internal — untuk memilih laci tempat elemen tinggal. Mencari "cache" berarti menghitung hash-nya, melompat langsung ke laci yang sesuai, dan membandingkan sedikit kandidat saja. Rasio size / bucket_count disebut load factor; bila ia melewati batas tertentu, container melakukan rehash (membuat bucket baru dan memindahkan semua elemen), yang inilah sebabnya operasi O(1) hanya berlaku rata-rata — kadang-kadang satu operasi lebih berat dari biasanya.

Operasi Inti unordered_set #

Program berikut menguji keanggotaan, pencetakan terurut, data internal, dan penghapusan.

#include <algorithm>     // std::sort: mengurutkan salinan untuk output deterministik
#include <iostream>      // std::cout
#include <string>        // std::string
#include <unordered_set> // std::unordered_set
#include <vector>        // std::vector sebagai wadah salinan terurut

int main() {
    std::unordered_set<std::string> kata;
    kata.insert("thread");
    kata.insert("cache");
    kata.insert("system");
    kata.insert("cache");    // duplikat: tidak berpengaruh

    std::cout << "ukuran        : " << kata.size() << "\n";
    std::cout << "cache ada?    : " << (kata.contains("cache") ? "ya" : "tidak") << "\n";
    std::cout << "mutex ada?    : " << (kata.contains("mutex") ? "ya" : "tidak") << "\n";

    // URUTAN ITERASI unordered_set TIDAK DITENTUKKAN standar.
    // Agar output deterministik: salin ke vector, urutkan, baru cetak.
    std::vector<std::string> salinan(kata.begin(), kata.end());
    std::sort(salinan.begin(), salinan.end());
    std::cout << "isi terurut   :";
    for (const std::string& k : salinan) std::cout << ' ' << k;
    std::cout << "\n";

    // data internal hash: jumlah bucket dan beban rata-ratanya
    // (angka tetap untuk alur yang sama, tetapi bisa berbeda antar standard library)
    std::cout << "bucket_count  : " << kata.bucket_count() << "\n";
    std::cout << "load_factor   : " << kata.load_factor() << "\n";

    // erase lewat iterator find, bukan menyalin isi
    kata.erase(kata.find("system"));
    std::cout << "system ada?   : " << (kata.contains("system") ? "ya" : "tidak") << "\n";

    return 0;
}

Output yang Dihasilkan:

ukuran        : 3
cache ada?    : ya
mutex ada?    : tidak
isi terurut   : cache system thread
bucket_count  : 13
load_factor   : 0.230769
system ada?   : tidak

Mari kita bedah:

1. Baris 9-12 (menambah elemen): empat kali insert, tetapi size hanya 3 — duplikat "cache" ditolak diam-diam, sama seperti pada std::set.
2. Baris 15-16 (contains): fungsi contains (masuk standar sejak C++20) adalah cara paling terbaca menanyakan keberadaan. Di balik layar ia menghitung hash kunci dan melompat ke bucket-nya — inilah lompatan O(1) rata-rata yang menjadi alasan utama memakai unordered container.
3. Baris 20-24 (pola cetak deterministik): karena urutan iterasi hash set tidak dijamin, kita menyalin isinya ke std::vector, mengurutkan dengan std::sort, lalu mencetak salinannya. Jadilah output cache system thread yang sama di mesin mana pun. Pola ini wajib ketika isi unordered container ikut ditampilkan, disimpan, atau dibandingkan.
4. Baris 28-29 (data internal): bucket_count menunjukkan ada 13 laci untuk 3 elemen, dan load_factor karenanya 0.230769. Angka ini deterministik untuk alur program yang sama pada standard library yang sama, tetapi bisa berbeda antar implementasi (libstdc++, libc++, MSVC) — jadikan hanya referensi mental, bukan kontrak.
5. Baris 32 (erase): menghapus lewat find mengembalikan iterator ke elemen; erase menerima iterator itu dan melepas elemennya. Versi satu argumen nilai (kata.erase("system")) juga sah pada unordered_set.

Set vs unordered_set: Menimbang Keduanya #

Keduanya menyimpan nilai unik; pembedanya ada pada janji urutan dan profil kecepatan.

Hash set menyelesaikan pertanyaan keanggotaan dengan kilat. Chapter berikutnya melengkapi keluarga hash dengan pasangan kunci-nilai: std::unordered_map, dan aturan deterministik yang sama berlaku penuh di sana.

Rujukan resmi: cppreference — std::unordered_set , cppreference — unordered_set::contains , cppreference — unordered_set::load_factor .