Trait Iterator

Metode next, sifat lazy, dan implementasi iterator manual.

Daftar isi

Topik ini membahas trait Iterator, yaitu protokol yang menjadi dasar seluruh iterasi di Rust. Pembahasan mencakup satu-satunya metode wajibnya bernama next, pemakaian Option sebagai penanda keadaan habis, sifat lazy yang menunda pekerjaan sampai nilai benar-benar diminta, serta penulisan implementasi Iterator untuk tipe bentukan sendiri. Setelah membaca topik ini, perilaku metode berantai seperti map dan filter dapat dijelaskan sampai ke mekanisme next yang mendasarinya, dan tipe baru dapat diubah menjadi iterator yang bekerja pada perulangan for.

Iterator sebagai protokol satu metode#

Trait Iterator mendefinisikan protokol satu arah untuk mengeluarkan nilai satu per satu. Satu-satunya metode yang wajib diimplementasikan adalah next, yang dipanggil berulang kali oleh pemakai iterator. Metode ini mengembalikan Option<Self::Item>, sehingga varian Some membawa nilai berikutnya, sedangkan None menyatakan bahwa nilai telah habis. Tipe terasosiasi Item menentukan jenis nilai yang dikeluarkan, misalnya i32 untuk iterator bilangan atau &T untuk iterator yang meminjam elemen milik koleksi lain.

rust Fragmen: bentuk inti trait Iterator

// tidak-dijalankan
trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    // puluhan metode lain, seperti map dan filter,
    // disediakan sebagai metode default di atas next
}

Metode next menerima &mut self karena iterator menyimpan state, biasanya berupa posisi kursor. Setiap pemanggilan memajukan kursor itu satu langkah, sehingga pemanggilan ketiga dan keempat pada iterator yang sama dapat menghasilkan nilai yang berbeda. Program berikut mengambil iterator dari vektor lewat iter(), lalu memanggil next empat kali secara manual.

rust metode-next.rs

fn main() {
    let angka = vec![10, 20, 30];
    let mut iter = angka.iter();

    println!("iterasi pertama : {:?}", iter.next());
    println!("iterasi kedua   : {:?}", iter.next());
    println!("iterasi ketiga  : {:?}", iter.next());
    println!("iterasi keempat : {:?}", iter.next());
}

text Keluaran

iterasi pertama : Some(10)
iterasi kedua   : Some(20)
iterasi ketiga  : Some(30)
iterasi keempat : None

Tiga pemanggilan pertama menghasilkan Some yang membawa referensi ke elemen vektor secara berurutan, dan vektor asalnya tetap utuh karena iter() hanya meminjam. Pemanggilan keempat menghasilkan None karena kursor telah melewati elemen terakhir. Diagram berikut merangkum alur tersebut.

Empat pemanggilan next() pada iterator tiga elemen

Setelah None keluar, iterator dinyatakan habis dan pemanggilan next berikutnya tetap mengembalikan None. Iterator tidak pernah kembali ke awal, sehingga nilai yang sudah dilewati tidak dapat ditarik ulang dari iterator yang sama. Perulangan for memakai trait IntoIterator untuk mengubah nilai menjadi iterator, lalu memanggil next secara berulang sampai None, dan itulah sebabnya blok perulangan berhenti dengan rapi tanpa penghitung indeks.

Sifat lazy: nilai dibuat saat diminta#

Iterator bersifat lazy, yakni tidak melakukan pekerjaan apa pun sampai next memintanya. Rangkaian metode berantai seperti map sekadar menyusun rencana perhitungan tanpa menjalankannya, karena map sendiri adalah iterator baru yang bekerja dengan memanggil next pada iterator di bawahnya. Akibatnya, pekerjaan terjadi tepat sebesar jumlah nilai yang diambil, bukan sebesar jumlah nilai sumbernya.

rust sifat-lazy.rs

fn main() {
    let data = vec![1, 2, 3, 4, 5];
    let mut pipa = data.iter().map(|&x| {
        println!("memproses {}", x);
        x * 10
    });

    println!("pipa siap, belum ada angka yang diproses");
    println!("hasil: {:?}", pipa.next());
    println!("hasil: {:?}", pipa.next());
    println!("dua elemen diambil, sisanya tidak pernah diproses");
}

text Keluaran

pipa siap, belum ada angka yang diproses
memproses 1
hasil: Some(10)
memproses 2
hasil: Some(20)
dua elemen diambil, sisanya tidak pernah diproses

Baris pertama keluaran membuktikan bahwa pembuatan pipa tidak memicu pemrosesan apa pun. Setiap pipa.next() kemudian menjalankan closure tepat satu kali untuk satu elemen, terlihat dari pesan memproses yang bergantian dengan baris hasil. Karena hanya dua nilai yang diminta, tiga elemen sisanya tidak pernah dihitung, sebab map tidak pernah ditanya tentang elemen ketiga dan seterusnya. Perilaku ini yang membuat operasi penyaringan mahal dapat berhenti lebih awal begitu jumlah nilai yang dibutuhkan terpenuhi.

Implementasi Iterator untuk tipe sendiri#

Tipe bentukan sendiri menjadi iterator dengan mengimplementasikan trait Iterator, yaitu menentukan Item dan menulis next. Seluruh metode default seperti map, filter, dan sum diperoleh gratis karena semuanya dibangun di atas next. Implementasi next wajib memajukan state pada setiap pemanggilan, sebab state yang tidak berubah menghasilkan iterator yang mengeluarkan nilai yang sama tanpa henti.

rust hitung-mundur.rs

struct HitungMundur {
    sisa: i32,
}

impl HitungMundur {
    fn dari(sisa: i32) -> Self {
        HitungMundur { sisa }
    }
}

impl Iterator for HitungMundur {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        if self.sisa <= 0 {
            None
        } else {
            let sekarang = self.sisa;
            self.sisa -= 1;
            Some(sekarang)
        }
    }
}

fn main() {
    let mut roket = HitungMundur::dari(2);
    println!("panggilan manual: {:?}", roket.next());
    println!("panggilan manual: {:?}", roket.next());
    println!("panggilan manual: {:?}", roket.next());

    for n in HitungMundur::dari(3) {
        println!("luncur dalam {}", n);
    }
    println!("roket lepas");
}

text Keluaran

panggilan manual: Some(2)
panggilan manual: Some(1)
panggilan manual: None
luncur dalam 3
luncur dalam 2
luncur dalam 1
roket lepas

Medan sisa menjadi state kursor. Ketika nilainya masih positif, next menyimpan nilai saat ini, menurunkan sisa satu langkah, lalu mengembalikan Some(sekarang), dan ketika sisa mencapai nol, next mengembalikan None untuk selamanya. Perulangan for pada main memperlihatkan hasil gratis dari implementasi tersebut, yaitu tipe HitungMundur langsung dapat dipakai sebagai sumber perulangan tanpa pengindeksan manual. Manfaat yang sama berlaku untuk iterator tak berhingga berikut ini.

rust fibonacci.rs

struct Fibonacci {
    sekarang: u64,
    berikutnya: u64,
}

impl Fibonacci {
    fn baru() -> Self {
        Fibonacci { sekarang: 1, berikutnya: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let hasil = self.sekarang;
        self.sekarang = self.berikutnya;
        self.berikutnya = hasil + self.berikutnya;
        Some(hasil)
    }
}

fn main() {
    for n in Fibonacci::baru().take(8) {
        println!("{}", n);
    }
}

text Keluaran

Iterator Fibonacci tidak menyimpan koleksi apa pun, melainkan hanya dua medan yang bergeser pada setiap next, sehingga memori yang dipakai tetap dua bilangan berapa pun banyaknya nilai yang diambil. Metode next selalu mengembalikan Some, sehingga iterator ini tidak pernah habis, dan take(8) membatasi perulangan menjadi delapan nilai. Tanpa pembatas semacam itu, perulangan for atas iterator tak berhingga tidak akan pernah mencapai None dan program berjalan tanpa henti.

Kesalahan umum#

Menganggap None sebagai tanda untuk mengulang dari awal. None adalah keadaan akhir, bukan isyarat reset, sehingga pemanggilan next setelah None tetap menghasilkan None. Apabila nilai perlu dibaca ulang, buat iterator baru dari sumbernya, atau kumpulkan hasilnya lebih dulu ke dalam koleksi.

Lupa memajukan state pada next buatan sendiri. Implementasi yang mengembalikan Some tanpa mengubah state menghasilkan iterator tak berhingga yang mengeluarkan nilai sama terus-menerus, dan perulangan for di atasnya tidak akan berhenti. Pastikan setiap cabang yang mengembalikan Some juga menggeser kursor atau mengubah state penanda berikutnya.

Ringkasan#

Trait Iterator hanya mewajibkan next(&mut self) -> Option<Self::Item>, yang mengeluarkan satu nilai per pemanggilan dan None sebagai tanda habis.
Iterator bersifat lazy, sehingga pekerjaan terjadi hanya sebesar nilai yang diminta, dan rangkaian metode berantai tidak berjalan sampai digerakkan.
Implementasi Iterator untuk tipe sendiri memberi seluruh metode default secara gratis, termasuk pemakaian pada perulangan for.
Iterator tak berhingga sah adanya selama pemakaianya dibatasi pembatas seperti take, karena tidak ada koleksi yang perlu disiapkan di muka.

Referensi#

Trait Iterator — Rust standard library — Definisi trait, kontrak next, serta daftar lengkap metode default dan adapternya.
Processing a Series of Items with Iterators — The Rust Programming Language — Bab resmi tentang next, sifat lazy, dan implementasi iterator sendiri.
Iterator — Rust By Example — Contoh ringkas implementasi Iterator pada tipe bentukan.