Tipe Data & Koleksi

BAB 16: Vector

Vec di Rust menyimpan banyak nilai sejenis di memori yang bisa bertumbuh, dibaca lewat indeks atau get, dengan panjang dan kapasitas yang terpisah.

Daftar nilai jarang diketahui panjangnya saat kode ditulis: berkas bisa berisi 3 baris hari ini dan 300 baris besok. Array menolak keadaan itu karena panjangnya bagian dari tipe, sehingga [i32; 3] tidak bisa menampung 4 nilai. Rust menyediakan Vec<T>, koleksi yang menyimpan elemen di memori yang bisa dialokasikan ulang saat jumlahnya bertambah.

Bab ini membahas cara membuat vector, menambah dan mengurangi isinya, membaca elemen dengan aman, serta menjelaskan hubungan antara panjang dan kapasitas. Setelah bab ini selesai, kamu dapat memilih antara indeks dan get, menulis fungsi yang menerima vector tanpa menyalinnya, dan menjelaskan mengapa penambahan elemen bisa membuat pinjaman lama ditolak. Semua contoh dikompilasi dengan rustc 1.100.0 dan dijalankan dari /tmp/latihan-rust/bab16.

Koleksi yang bisa bertumbuh

Vector dibuat dengan Vec::new atau macro vec!. Keduanya menghasilkan tipe yang sama, dan isi vector harus sejenis. Berkas v1_dasar.rs membuat 3 vector dengan 3 cara.

RSRUST
fn main() {
    let kosong: Vec<i32> = Vec::new();
    let nilai = vec![70, 85, 90];
    let nol = vec![0; 4];

    println!("kosong {:?} panjang {}", kosong, kosong.len());
    println!("nilai {:?} panjang {}", nilai, nilai.len());
    println!("nol {:?}", nol);
    println!("ukuran Vec<i32> di stack {} byte", std::mem::size_of::<Vec<i32>>());
}
CodeTEXT
kosong [] panjang 0
nilai [70, 85, 90] panjang 3
nol [0, 0, 0, 0]
ukuran Vec<i32> di stack 24 byte

vec![0; 4] membuat 4 elemen bernilai 0, dan bentuk vec![a, b, c] membuat vector dari daftar nilai. Anotasi Vec<i32> diperlukan pada Vec::new karena vector kosong tidak memberi petunjuk tipe apa pun, sementara pada vec![70, 85, 90] tipe disimpulkan dari isinya.

Jumlah 24 byte adalah ukuran struct Vec itu sendiri, bukan ukuran isinya. Angka itu berasal dari 3 bidang: penunjuk ke memori, panjang, dan kapasitas, masing-masing 8 byte pada mesin 64 bit. Elemen sebenarnya disimpan di memori terpisah, sehingga memindahkan variabel Vec tidak menyalin seluruh isinya.

Isi vector harus 1 tipe. Mencampur integer dan teks ditolak saat kompilasi.

RSRUST
fn main() {
    let nilai = vec![70, "delapan puluh"];

    println!("{:?}", nilai);
}
CodeTEXT
error[E0308]: mismatched types
 --> e4_campur.rs:2:26
  |
2 |     let nilai = vec![70, "delapan puluh"];
  |                          ^^^^^^^^^^^^^^^ expected integer, found `&str`

error: aborting due to 1 previous error

Pesan E0308 menunjuk elemen kedua sebagai penyebab, karena elemen pertama sudah menetapkan tipe {integer}. Dokumentasi Rust Book menyatakan vector hanya menyimpan nilai dengan tipe yang sama, dan tipe itu ditulis di dalam kurung sudut seperti Vec<i32>. Kalau data memang berbeda tipe, pilihannya adalah enum atau struct, bukan vector campuran.

Menambah dan mengurangi elemen

Penambahan memakai push, pengambilan dari ujung memakai pop, dan penghapusan berdasarkan posisi memakai remove. Variabelnya harus mut karena isi vector berubah.

RSRUST
fn main() {
    let mut nilai = vec![70, 85];

    nilai.push(90);
    println!("setelah push {:?}", nilai);
    println!("len {} capacity {}", nilai.len(), nilai.capacity());

    let terakhir = nilai.pop();
    println!("pop {:?}", terakhir);
    println!("sekarang {:?}", nilai);

    let dihapus = nilai.remove(0);
    println!("remove(0) {:?}", dihapus);
    println!("sisa {:?}", nilai);
}
CodeTEXT
setelah push [70, 85, 90]
len 3 capacity 4
pop Some(90)
sekarang [70, 85]
remove(0) 70
sisa [85]

pop mengembalikan Some(90), bukan angka 90, karena vector bisa saja kosong dan hasilnya None. remove(0) mengembalikan nilai yang dibuang dan menggeser elemen sesudahnya ke kiri, sehingga biayanya naik sebanding jumlah elemen yang bergeser. Untuk membuang elemen terakhir, pop lebih murah karena tidak ada yang digeser.

Vector yang dibuat dengan vec![70, 85] sudah punya kapasitas 4 sebelum push dijalankan. Kapasitas awal itu bukan janji bahasa, tetapi hasil alokasi yang dipilih implementasi, dan nilainya bisa berbeda pada versi pustaka lain.

Panjang, kapasitas, dan realokasi

Panjang adalah jumlah elemen yang ada, sedangkan kapasitas adalah ruang yang sudah disiapkan. Keduanya bergerak dengan pola berbeda saat elemen ditambah satu per satu.

RSRUST
fn main() {
    let mut nilai: Vec<i32> = Vec::new();
    println!("awal len {} capacity {}", nilai.len(), nilai.capacity());

    for i in 0..10 {
        nilai.push(i);
        println!("i {} len {} capacity {}", i, nilai.len(), nilai.capacity());
    }
}
CodeTEXT
awal len 0 capacity 0
i 0 len 1 capacity 4
i 1 len 2 capacity 4
i 2 len 3 capacity 4
i 3 len 4 capacity 4
i 4 len 5 capacity 8
i 5 len 6 capacity 8
i 6 len 7 capacity 8
i 7 len 8 capacity 8
i 8 len 9 capacity 16
i 9 len 10 capacity 16

Kapasitas naik dari 0 ke 4, lalu 8, lalu 16, setiap kali panjang melewati batas sebelumnya. Kenaikan itu bukan 1 per elemen, karena setiap kenaikan memindahkan seluruh elemen ke blok memori baru. Dokumentasi Vec menyebut kapasitas sebagai ruang yang disiapkan untuk elemen berikutnya, dan pengalokasian ulang bisa lambat kalau panjang melewati kapasitas.

Kalau jumlah elemen sudah diperkirakan, Vec::with_capacity(10) menyiapkan ruang lebih awal. Pada pengukuran terpisah, vector itu melaporkan len 0 dan capacity 10 sebelum 1 elemen pun diisi, sehingga 10 penambahan pertama tidak memicu realokasi. Memilih angka yang terlalu besar hanya membuang memori, jadi perkiraan yang wajar lebih baik daripada angka berlebih.

Membaca elemen dengan indeks dan get

Ada 2 cara membaca elemen: indeks dengan tanda kurung siku, atau get yang mengembalikan Option. Keduanya menerima nomor elemen mulai dari 0.

RSRUST
fn main() {
    let nilai = vec![70, 85, 90];

    println!("indeks 0 {}", nilai[0]);
    println!("get(0) {:?}", nilai.get(0));
    println!("get(9) {:?}", nilai.get(9));
    println!("first {:?} last {:?}", nilai.first(), nilai.last());
    println!("berisi 85 {}", nilai.contains(&85));
}
CodeTEXT
indeks 0 70
get(0) Some(70)
get(9) None
first Some(70) last Some(90)
berisi 85 true

nilai[0] langsung memberi angka, sedangkan nilai.get(0) memberi Some(70). Perbedaan itu penting saat indeks belum pasti: get(9) pada vector berisi 3 elemen menghasilkan None, dan program tetap berjalan. Rust Book menyebut 2 cara ini sebagai indeks dan method get, dengan hasil yang berbeda bentuk.

Method first dan last juga mengembalikan Option, sehingga vector kosong tidak memaksa pemanggil menebak nilai awal. contains memeriksa keberadaan nilai dan mengembalikan bool, yang berguna sebelum memanggil remove pada posisi yang belum diketahui.

Indeks di luar batas menghentikan program

Indeks yang melewati jumlah elemen tidak menghasilkan nilai kosong. Program berhenti saat baris itu dijalankan.

RSRUST
fn main() {
    let nilai = vec![70, 85, 90];

    println!("{}", nilai[3]);
}
CodeTEXT
thread 'main' (1597111) panicked at e1_batas.rs:4:25:
index out of bounds: the len is 3 but the index is 3
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Kode keluar program itu 101, dan pesannya menyebut the len is 3 but the index is 3. Angka di dalam tanda kurung setelah main adalah identitas thread, dan nilainya berubah pada setiap penjalanan, jadi jangan dipakai sebagai bagian pesan yang tetap. Baris terakhir menyarankan RUST_BACKTRACE=1 untuk melihat jejak pemanggilan.

Perbedaan perilaku ini adalah alasan get dipakai saat indeks berasal dari input. Pada vector, indeks literal 3 pada contoh di atas tetap lolos kompilasi dan baru berhenti saat baris itu dijalankan, sehingga kompilator tidak bisa diandalkan untuk menangkap batas yang salah. Memilih get membuat kesalahan indeks menjadi nilai None yang bisa ditangani, bukan penghentian program.

Mengubah elemen dan mengurutkan isi

Elemen bisa diganti lewat indeks, diubah lewat iterator &mut, lalu diurutkan dengan sort. Semua operasi itu menuntut variabel mut.

RSRUST
fn main() {
    let mut nilai = vec![70, 85, 90];

    nilai[1] = 88;
    nilai[2] += 5;
    println!("{:?}", nilai);

    for isi in &mut nilai {
        *isi += 1;
    }
    println!("setelah iter_mut {:?}", nilai);

    nilai.sort();
    println!("setelah sort {:?}", nilai);
    println!("potongan {:?}", &nilai[1..3]);
}
CodeTEXT
[70, 88, 95]
setelah iter_mut [71, 89, 96]
setelah sort [71, 89, 96]
potongan [89, 96]

Di dalam for isi in &mut nilai, variabel isi bertipe &mut i32, sehingga penulisannya memakai *isi. Tanpa tanda bintang, yang ditulis adalah penunjuknya, bukan angka yang ditunjuk. Hasil sort pada data ini kebetulan sama dengan urutan sebelumnya, dan itu wajar karena isinya sudah naik.

Method sort di dokumentasi slice mengurutkan secara menaik, stabil, dengan biaya O(n * log(n)) pada kasus terburuk. Stabil berarti 2 elemen yang dianggap sama tidak bertukar posisi. &nilai[1..3] memotong vector menjadi slice berisi indeks 1 dan 2, dan hasilnya bisa dicetak langsung tanpa menyalin elemen.

Menulis elemen pada vector yang tidak mut menghasilkan kode E0596, bukan E0594 seperti pada array.

RSRUST
fn main() {
    let nilai = vec![70, 85, 90];
    nilai[0] = 100;
    println!("{:?}", nilai);
}
CodeTEXT
error[E0596]: cannot borrow `nilai` as mutable, as it is not declared as mutable
 --> e2_immutable.rs:3:5
  |
3 |     nilai[0] = 100;
  |     ^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
2 |     let mut nilai = vec![70, 85, 90];
  |         +++

error: aborting due to 1 previous error

Pesan itu memakai kata borrow karena penulisan ke indeks Vec melewati trait IndexMut, yang butuh pinjaman mutable. Pada array, penulisan bidang ditangani langsung oleh kompilator dan pesannya E0594. 2 kode berbeda untuk kesalahan yang tampak sama, dan keduanya sudah diukur di mesin ini.

Mengulang isi vector

Vector bisa diulang dengan for. Bentuk &nilai meminjam isinya, sedangkan nilai tanpa & memindahkan seluruh vector ke dalam loop.

RSRUST
fn main() {
    let nilai = vec![70, 85, 90];

    for isi in &nilai {
        print!("{} ", isi);
    }
    println!();

    let mut total = 0;
    for (posisi, isi) in nilai.iter().enumerate() {
        println!("posisi {} isi {}", posisi, isi);
        total += isi;
    }
    println!("total {} rata-rata {}", total, total as f64 / nilai.len() as f64);
}
CodeTEXT
70 85 90 
posisi 0 isi 70
posisi 1 isi 85
posisi 2 isi 90
total 245 rata-rata 81.66666666666667

enumerate memberi 2 nilai per putaran, yaitu posisi dan isi, sehingga nomor elemen tidak perlu dihitung manual dengan variabel tambahan. Pembagian memakai as f64 pada 2 sisi karena pembagian 2 integer di Rust menghasilkan integer, dan sisa pembagiannya dibuang.

Hasil rata-rata 81.66666666666667 menunjukkan batas presisi f64 saat dicetak. Angka itu bukan pembulatan ke 2 desimal, melainkan representasi terdekat yang bisa disimpan tipe tersebut. Untuk keperluan tampilan, pembulatan dilakukan saat mencetak dengan format seperti {:.2}.

Meminjam sambil menambah elemen

Pinjaman ke elemen bisa batal kalau vector diubah, karena penambahan dapat memindahkan seluruh isi ke alamat baru. Kompilator menolak urutan itu sebelum program berjalan.

RSRUST
fn main() {
    let mut nilai = vec![1, 2, 3];
    let pertama = &nilai[0];

    nilai.push(4);
    println!("pertama {}", pertama);
}
CodeTEXT
error[E0502]: cannot borrow `nilai` as mutable because it is also borrowed as immutable
 --> e3_pinjam.rs:5:5
  |
3 |     let pertama = &nilai[0];
  |                    ----- immutable borrow occurs here
5 |     nilai.push(4);
  |     ^^^^^^^^^^^^^ mutable borrow occurs here
6 |     println!("pertama {}", pertama);
  |                            ------- immutable borrow later used here

error: aborting due to 1 previous error

Pesan E0502 menandai 3 baris: pinjaman pertama, penambahan yang bentrok, dan pemakaian pinjaman setelahnya. Perbaikannya adalah menyalin nilainya lebih dulu dengan let pertama = nilai[0]; karena i32 bisa disalin, atau menunda push sampai pinjaman tidak dipakai lagi.

Aturan ini bukan kehati-hatian berlebihan. push bisa mengalokasikan blok memori baru dan menyalin isi vector ke sana, sehingga penunjuk lama akan menunjuk memori yang sudah tidak dipakai. Kompilator menutup kemungkinan itu dengan menolak pinjaman yang masih hidup.

Vector sebagai parameter dan nilai kembalian

Fungsi yang hanya membaca isi vector sebaiknya menerima &[T], bukan &Vec<T>. Tipe slice menerima vector, array, dan potongan sekaligus, sehingga 1 fungsi bisa dipakai lebih luas.

RSRUST
fn rata_rata(nilai: &[i32]) -> f64 {
    let mut total = 0;
    for isi in nilai {
        total += isi;
    }
    total as f64 / nilai.len() as f64
}

fn di_atas_batas(nilai: &[i32], batas: i32) -> Vec<i32> {
    nilai.iter().filter(|isi| **isi > batas).copied().collect()
}

fn main() {
    let nilai = vec![70, 85, 90, 65];
    println!("rata-rata {}", rata_rata(&nilai));
    println!("di atas 75 {:?}", di_atas_batas(&nilai, 75));

    let disiapkan: Vec<i32> = Vec::with_capacity(10);
    println!("dengan kapasitas awal len {} capacity {}", disiapkan.len(), disiapkan.capacity());
}
CodeTEXT
rata-rata 77.5
di atas 75 [85, 90]
dengan kapasitas awal len 0 capacity 10

rata_rata bisa dipanggil dengan &nilai karena &Vec<i32> otomatis menyesuaikan diri menjadi &[i32]. di_atas_batas mengembalikan Vec<i32> baru, jadi pemanggil memiliki hasilnya dan vector asal tidak tersentuh. Rantai filter dan copied memilih elemen yang lolos lalu menyalin nilainya keluar dari referensi.

Bagian **isi > batas memakai 2 tanda bintang karena filter memberi &&i32: satu lapis dari iterator, satu lapis dari closure. Menulis *isi > batas gagal kompilasi dengan pesan tipe, dan kesalahan itu wajar terjadi saat pertama kali memakai filter pada referensi.

Latihan

  1. Buat vector berisi 5 nilai ujian, lalu cetak nilai tertinggi memakai iter().max().
  2. Tulis fungsi yang menerima &[i32] dan mengembalikan Vec<i32> berisi nilai yang berada di atas rata-rata.
  3. Ubah e1_batas.rs supaya memakai get(3) dan menampilkan pesan sendiri saat hasilnya None.
  4. Ukur kapasitas vector saat 20 elemen ditambahkan satu per satu, lalu bandingkan dengan Vec::with_capacity(20).

Ringkasan

Vec<T> menyimpan banyak nilai sejenis di memori yang bisa dialokasikan ulang, dengan panjang dan kapasitas sebagai 2 angka yang bergerak berbeda. Elemen dibaca lewat indeks yang berhenti saat keluar batas atau lewat get yang mengembalikan Option, dan isinya diubah dengan mut melalui indeks maupun iterator &mut. Pinjaman ke elemen tidak boleh hidup berdampingan dengan penambahan, karena realokasi memindahkan seluruh isi vector ke alamat baru.

Referensi

  1. The Rust Programming Language. Storing Lists of Values with Vectors.
  2. Rust Standard Library. Vec in std::vec.
  3. Rust Standard Library. Primitive Type slice.