VecDeque dan BTreeMap

Topik ini membahas VecDeque<T> dan BTreeMap<K, V>, dua koleksi pustaka standar yang melengkapi Vec dan HashMap. VecDeque menyediakan antrean dua ujung dengan biaya konstan pada kedua sisinya, sedangkan BTreeMap menyediakan peta yang kuncinya selalu terurut. Pembahasan mencakup operasi kedua ujung antrean, penyimpanan pasangan kunci-nilai terurut, penyaringan rentang kunci dengan range, syarat Ord pada kunci, serta pertimbangan memilih struktur yang tepat di antara koleksi yang telah dibahas. Setelah membaca topik ini, struktur data dapat dipilih berdasarkan pola akses datanya, bukan berdasarkan kebiasaan penulisan.

Antrean dua ujung dengan VecDeque#

VecDeque<T> adalah singkatan dari double-ended queue, yaitu koleksi yang tumbuh dan menyusut pada dua ujungnya sekaligus. Implementasinya memakai penyangga melingkar (ring buffer): elemen disusun berdekatan di heap, dan ketika salah satu ujung fisik penyangga terisi, penyisipan berlanjut melingkar ke ruang kosong di ujung lainnya. Susunan tersebut membuat push_front, push_back, pop_front, dan pop_back bekerja dengan biaya konstan secara amortisasi. Perilaku ini berbeda dari Vec: push dan pop pada vektor memang murah di ujung belakang, tetapi penyisipan di depan vektor menggeser seluruh elemen yang sudah ada.

Metode front() dan back() mengintip elemen terdepan dan terbelakang tanpa mengeluarkannya, dan keduanya mengembalikan Option<&T> karena antrean dapat berada dalam keadaan kosong. Program berikut menyimulasikan antrean tiket pada sebuah loket layanan.

use std::collections::VecDeque;

fn main() {
    let mut antrean: VecDeque<&str> = VecDeque::new();

    antrean.push_back("tiket-001");
    antrean.push_back("tiket-002");
    antrean.push_back("tiket-003");
    antrean.push_back("tiket-004");
    println!("antrean           : {:?}", antrean);

    antrean.push_front("tiket-prioritas");
    println!("setelah push_front: {:?}", antrean);

    let dilayani = antrean.pop_front();
    println!("dilayani          : {:?}", dilayani);
    println!("antrean           : {:?}", antrean);

    println!("terdepan          : {:?}", antrean.front());
    println!("terbelakang       : {:?}", antrean.back());
}

antrean           : ["tiket-001", "tiket-002", "tiket-003", "tiket-004"]
setelah push_front: ["tiket-prioritas", "tiket-001", "tiket-002", "tiket-003", "tiket-004"]
dilayani          : Some("tiket-prioritas")
antrean           : ["tiket-001", "tiket-002", "tiket-003", "tiket-004"]
terdepan          : Some("tiket-001")
terbelakang       : Some("tiket-004")

Empat tiket masuk melalui push_back sehingga urutannya mengikuti urutan kedatangan. Pemanggilan push_front kemudian menempatkan tiket-prioritas paling depan tanpa menggeser empat elemen lain satu per satu, dan pop_front mengeluarkannya lebih dahulu untuk dilayani. Setelah itu front() menunjuk tiket-001 dan back() menunjuk tiket-004, sementara keempat elemen tetap berada pada urutan aslinya. Keluaran pop_front berupa Some("tiket-prioritas") karena metode tersebut mengembalikan Option<T>, sama seperti pop pada vektor. Diagram berikut merangkum keempat pintu operasi pada kedua ujung antrean.

Peta terurut dengan BTreeMap#

BTreeMap<K, V> menyimpan pasangan kunci-nilai di dalam pohon terurut yang dijaga tetap seimbang, sehingga setiap pencarian, penyisipan, dan penghapusan menempuh jumlah langkah yang sebanding dengan logaritma jumlah kunci. Perbedaan yang paling terasa dari HashMap terletak pada urutan: iterasi BTreeMap selalu berjalan menaik mengikuti urutan kunci, dan urutan tersebut sama pada setiap jalankan program. Metode range(rentang) memanfaatkan urutan itu dengan menghasilkan seluruh pasangan yang kuncinya berada pada rentang tertentu, tanpa membandingkan seluruh kunci satu per satu. Program berikut mencatat pembacaan suhu pada empat jam pengamatan.

use std::collections::BTreeMap;

fn main() {
    let mut suhu = BTreeMap::new();

    suhu.insert(20, 27.4);
    suhu.insert(8, 24.1);
    suhu.insert(12, 25.8);
    suhu.insert(16, 26.9);
    println!("debug peta : {:?}", suhu);
    println!("suhu jam 12 : {}", suhu[&12]);

    println!("mulai jam 12:");
    for (jam, nilai) in suhu.range(12..) {
        println!("  jam {jam} : {nilai}");
    }
}

debug peta : {8: 24.1, 12: 25.8, 16: 26.9, 20: 27.4}
suhu jam 12 : 25.8
mulai jam 12:
  jam 12 : 25.8
  jam 16 : 26.9
  jam 20 : 27.4

Pengisian dilakukan dengan urutan jam 20, 8, 12, dan 16, tetapi keluaran {:?} menampilkan peta dengan kunci 8, 12, 16, dan 20. Pohon terurut yang menjadi tempat penyimpanan mengatur posisi setiap kunci pada saat penyisipan, sehingga urutan masukan tidak berdampak pada urutan isi. Pengindeksan suhu[&12] membaca nilai jam 12 dengan cara yang sama seperti pengindeksan peta hash, termasuk perilaku panic apabila kunci yang diminta tidak ada. Iterasi range(12..) kemudian menghasilkan tiga pasangan mulai jam 12 sampai jam 20, karena rentang tanpa batas atas mencakup seluruh kunci yang lebih besar atau sama dengan 12.

Kunci terurut dengan Ord#

Pohon terurut menempatkan setiap kunci berdasarkan hasil perbandingannya terhadap kunci lain, sehingga tipe kunci wajib mengimplementasikan trait Ord beserta seluruh prasyaratnya, yaitu PartialOrd, Eq, dan PartialEq. Bilangan bulat, String, dan &str sudah memenuhi keempat trait tersebut, sedangkan struct buatan sendiri belum memilikinya. Program kecil berikut menolak dikompilasi karena struct Jam dipakai sebagai kunci tanpa derive apa pun.

export PATH="$HOME/.cargo/bin:$PATH"
# buat program yang memakai struct sebagai kunci BTreeMap tanpa derive Ord
printf 'use std::collections::BTreeMap;\n\nstruct Jam {\n    nomor: u32,\n}\n\nfn main() {\n    let mut peta = BTreeMap::new();\n    peta.insert(Jam { nomor: 8 }, 24.1);\n    println!("{}", peta.len());\n}\n' > salah-urut.rs
# kompilasi ditolak karena kunci BTreeMap wajib mengimplementasikan Ord
rustc --edition=2021 salah-urut.rs 2>&1 | sed -n '1,16p'

error[E0277]: the trait bound `Jam: Ord` is not satisfied
 --> salah-urut.rs:9:10
  |
9 |     peta.insert(Jam { nomor: 8 }, 24.1);
  |          ^^^^^^ ---------------- `Jam` doesn't satisfy the trait bound
  |          |
  |          the trait `Ord` is not implemented for `Jam`
  |
note: required by a bound in `BTreeMap::<K, V, A>::insert`
 --> /rustc/58cf8f9c35b355199727627d07ae34a4e2846d67/library/alloc/src/collections/btree/map.rs:1045:4
help: consider annotating `Jam` with `#[derive(Ord)]`
  |
3 + #[derive(Ord)]
4 | struct Jam {
  |

Pesan error menyebut Ord sebagai trait yang tidak diimplementasikan untuk Jam, lalu menawarkan derive sebagai perbaikan. Derive yang lengkap untuk kunci struct mencakup empat trait sekaligus, yaitu #[derive(PartialEq, Eq, PartialOrd, Ord)], dan perbandingannya mengikuti urutan penulisan field pada deklarasi struct. Penolakan ini sejajar dengan syarat Eq dan Hash pada kunci HashMap, sehingga pola perbaikannya pun sama: satu baris derive pada deklarasi tipe kunci. Setelah derive dipasang, seluruh operasi peta bekerja tanpa kode perbandingan tambahan.

Syarat Ord juga menyaring tipe tertentu sejak awal. Bilangan pecahan f64 hanya mengimplementasikan PartialOrd karena nilai NaN tidak dapat dibandingkan secara total dengan nilai lain. Akibatnya, f64 ditolak sebagai kunci kecuali apabila dibungkus tipe lain yang menetapkan urutan totalnya. Kesalahan semacam ini muncul pada saat kompilasi dengan bentuk error yang sama seperti contoh sebelumnya, bukan menjadi kejutan saat program berjalan.

Memilih struktur yang tepat#

Empat koleksi yang dibahas pada modul ini dibedakan oleh pola akses datanya, dan pilihan yang tepat mengikuti pola akses tersebut, bukan nama yang kebetulan lebih dikenal. Tabel berikut merangkum perbandingannya.

Vec tetap menjadi pilihan awal untuk daftar yang urutannya dijaga oleh logika program, karena pengindeksannya paling murah dan iterasinya paling sederhana. VecDeque mengambil alih begitu elemen juga perlu keluar-masuk di depan, misalnya pada antrean tugas atau jendela geser. HashMap dipakai ketika asosiasi kunci-nilai menjadi inti masalah dan urutan tidak penting, sedangkan BTreeMap dipakai ketika urutan kunci, rentang kunci, atau kestabilan keluaran antar-jalankan menjadi kebutuhan. Pertukarannya sederhana: peta hash lebih cepat secara rata-rata tetapi tidak menjamin urutan, sedangkan peta terurut menjaga urutan dengan biaya logaritmik. Mulailah dari Vec atau HashMap, lalu berpindah setelah pola akses pada kode menunjukkan struktur yang lebih cocok.

Kesalahan umum#

Memakai Vec sebagai antrean dengan remove(0). Pemanggilan remove(0) pada vektor menggeser seluruh elemen setelahnya satu langkah ke depan, sehingga antrean yang sibuk menanggung kerja yang berbanding lurus dengan panjangnya. VecDeque dirancang untuk pola keluar di depan dan masuk di belakang, dan penggantiannya tidak mengubah logika program karena metode push_back dan pop_front tersedia dengan makna yang sama. Biaya penggeserannya tidak terlihat pada data kecil, sehingga keputusan berganti struktur sering baru diambil setelah antrean tumbuh besar, padahal penggantian sejak awal tidak memerlukan perombakan kode.

Mengharapkan BTreeMap mengurutkan nilai. Urutan peta terurut mengikuti kunci saja, sehingga posisi setiap pasangan ditentukan oleh kuncinya, bukan oleh nilainya. Ketika keluaran perlu terurut menurut nilai, kumpulkan isi peta ke dalam Vec berisi pasangan (kunci, nilai), lalu urutkan vektor tersebut dengan sort_by_key yang menggunakan nilai sebagai kunci pengurutannya. Peta tetap menjadi tempat penyimpanan yang tepat, dan pengurutan menurut nilai cukup dikerjakan pada tahap penyusunan keluarannya.

Ringkasan#

• VecDeque<T> adalah antrean dua ujung berbasis penyangga melingkar, dengan push_front, push_back, pop_front, dan pop_back yang berbiaya konstan secara amortisasi.
• front() dan back() mengintip ujung antrean melalui Option<&T>, sehingga keadaan kosong ditangani tanpa panic.
• BTreeMap<K, V> menyimpan pasangan dalam pohon terurut: iterasinya menaik mengikuti kunci, stabil antar-jalankan, dan range menyaring rentang kunci tanpa memeriksa seluruh isi.
• Kunci BTreeMap wajib mengimplementasikan Ord beserta prasyaratnya, dan struct kunci memperolehnya melalui #[derive(PartialEq, Eq, PartialOrd, Ord)].
• Pilihan koleksi mengikuti pola akses: ujung belakang saja memakai Vec, dua ujung memakai VecDeque, kunci acak memakai HashMap, dan kunci terurut memakai BTreeMap.

Referensi#

• std::collections — Rust standard library — Ikhtisar seluruh koleksi bawaan beserta panduan resmi memilih koleksi yang tepat.
• Struct VecDeque — Rust standard library — Dokumentasi metode antrean dua ujung, termasuk push_front, pop_front, dan front.
• Struct BTreeMap — Rust standard library — Dokumentasi peta terurut, termasuk range dan syarat trait untuk kuncinya.
• Error code E0277 — Rust compiler — Indeks resmi untuk pesan error trait bound yang tidak terpenuhi.