Iterator tự định nghĩa trong Rust

Ở trang Iterator, bạn đã dùng các iterator mà thư viện chuẩn cung cấp: vec.iter(), .map(), .filter(), .sum(). Nhưng bạn cũng có thể tạo iterator của riêng mình. Một bộ đếm ngược, dãy Fibonacci, các trang của một báo cáo, các dòng của một định dạng tệp riêng: bất cứ thứ gì đưa ra từng giá trị một đều có thể là một iterator.

Tin vui là: bạn chỉ phải viết một phương thức, next. Rust sẽ cho bạn mọi adapter (map, filter, take, sum, zip và hàng chục cái khác) miễn phí. Hãy nghĩ tới một máy phát số thứ tự. Bạn làm phần in ra số tiếp theo. Hàng chờ, màn hình và bảng “đang phục vụ số” đều tự động chạy.

Iterator đầu tiên của bạn: đếm ngược

Để biến một kiểu thành iterator, hãy triển khai trait Iterator. Nó cần hai thứ:

• type Item: loại giá trị mà iterator đưa ra (xem Trait nâng cao để biết thêm về associated type).
• fn next(&mut self) -> Option<Self::Item>: trả về Some(value) cho giá trị tiếp theo, hoặc None khi đã hết.

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None // đã xong
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let mut countdown = Countdown::new(3);

    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());

    for n in Countdown::new(3) {
        println!("{}...", n);
    }
    println!("Cất cánh!");
}

Kết quả:

Some(3)
Some(2)
Some(1)
None
None
3...
2...
1...
Cất cánh!

▶ Tự chạy thử

Vài điều cần để ý:

• next nhận &mut self vì nó thay đổi iterator. Struct nhớ nó đang ở đâu (current), và mỗi lần gọi sẽ đẩy nó tiến lên. Đó là lý do countdown phải là let mut.
• Trả về None nghĩa là “tôi xong rồi”. Vòng for gọi next liên tục và dừng ở None đầu tiên.
• Bộ đếm ngược của chúng ta tiếp tục trả về None sau khi đã xong. Như vậy là lịch sự, nhưng trait không bắt buộc điều đó: một số iterator có thể bắt đầu lại. Nếu bạn cần sự đảm bảo này, hãy gọi .fuse() trên bất kỳ iterator nào.

Một iterator vô tận: Fibonacci

Một iterator không nhất thiết phải kết thúc. Dãy Fibonacci (0, 1, 1, 2, 3, 5, 8, …) kéo dài mãi mãi: mỗi số là tổng của hai số đứng trước nó. Iterator chỉ cần nhớ hai số gần nhất:

struct Fibonacci {
    current: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        // checked_add trả về None khi tràn số, và `?` chuyển tiếp None đó,
        // nên iterator kết thúc thay vì sập khi các số trở nên quá lớn.
        let new_next = self.current.checked_add(self.next)?;
        self.current = self.next;
        self.next = new_next;
        Some(value)
    }
}

fn main() {
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first_ten);
}

Kết quả:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Tự chạy thử

.take(10) là chìa khóa. Không có nó, collect() sẽ cố gom toàn bộ dãy số. Với một iterator vô tận, hãy luôn giới hạn nó bằng thứ gì đó như take, take_while hoặc find.

Mọi adapter, miễn phí

Đây là phần hay nhất. Trait Iterator có khoảng 75 phương thức, và tất cả trừ next đều có cài đặt mặc định xây trên next. Vậy nên ngay khi bạn viết next, kiểu của bạn có thể dùng tất cả:

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let total: u32 = Countdown::new(5).sum();
    println!("Tổng: {}", total);

    let evens: Vec<u32> = Countdown::new(10).filter(|n| n % 2 == 0).collect();
    println!("Số chẵn: {:?}", evens);

    let labels: Vec<String> = Countdown::new(3).map(|n| format!("T-{}", n)).collect();
    println!("Nhãn: {:?}", labels);

    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("Bội số đầu tiên của 7: {:?}", multiple);

    let pairs: Vec<(u32, char)> = Countdown::new(3).zip(['a', 'b', 'c']).collect();
    println!("Ghép cặp: {:?}", pairs);
}

Kết quả:

Tổng: 15
Số chẵn: [10, 8, 6, 4, 2]
Nhãn: ["T-3", "T-2", "T-1"]
Bội số đầu tiên của 7: Some(98)
Ghép cặp: [(3, 'a'), (2, 'b'), (1, 'c')]

▶ Tự chạy thử

Đây là một ví dụ tuyệt vời cho thấy vì sao trait trong Rust hữu ích đến vậy. Bỏ vào một phương thức nhỏ, nhận về cả một hộp đồ nghề khổng lồ.

Iterator là lười

Các adapter như map và take tự chúng không làm gì cả. Chúng chỉ dựng lên một “kế hoạch”. Công việc chỉ diễn ra khi có thứ gì đó tiêu thụ (consume) iterator: một vòng for, collect, sum, v.v. Hãy chứng minh bằng một iterator in ra mỗi khi next được gọi:

struct Noisy {
    n: u32,
}

impl Iterator for Noisy {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        self.n += 1;
        println!("  next() được gọi, trả về {}", self.n);
        Some(self.n)
    }
}

fn main() {
    println!("Đang dựng chuỗi...");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("Chưa có gì chạy cả. Giờ bắt đầu tiêu thụ:");

    for value in chain {
        println!("nhận {}", value);
    }
    println!("Xong");
}

Kết quả:

Đang dựng chuỗi...
Chưa có gì chạy cả. Giờ bắt đầu tiêu thụ:
  next() được gọi, trả về 1
nhận 10
  next() được gọi, trả về 2
nhận 20
  next() được gọi, trả về 3
nhận 30
Xong

▶ Tự chạy thử

Có hai bài học ở đây. Thứ nhất, việc dựng chuỗi không in ra gì cả, hoàn toàn không có lời gọi next() nào. Thứ hai, các giá trị chảy qua từng cái một: một next, một map, một nhận, rồi tới giá trị kế tiếp. Không có danh sách ẩn nào ở giữa. Và Noisy không bao giờ kết thúc, vậy mà chương trình vẫn xong: sau ba phần tử, take(3) đơn giản là không hỏi thêm nữa.

Cho collection của bạn chạy được trong vòng for

Tới giờ, các struct của chúng ta chính là iterator. Nhưng thường thì bạn có một collection, một struct chứa các phần tử, và bạn muốn người khác lặp qua nó giống như lặp qua một Vec. Để làm vậy, bạn triển khai IntoIterator. Đó là trait mà vòng for dùng phía sau: for x in thing thật ra gọi thing.into_iter().

Các collection thường có ba cách lặp, và sẽ dễ hiểu hơn khi thấy chúng trên kiểu của chính bạn:

Bạn viết	Phương thức phía sau	Mỗi phần tử là	Collection sau đó
for s in &playlist	playlist.iter()	&String (chỉ đọc)	vẫn dùng được
for s in &mut playlist	playlist.iter_mut()	&mut String (sửa được)	vẫn dùng được
for s in playlist	playlist.into_iter()	String (sở hữu)	đã bị move, không còn

Đây là một Playlist hỗ trợ cả ba. Struct của chúng ta lưu bài hát trong một Vec, nên ta có thể đưa ra chính các iterator của Vec thay vì viết cái mới. (Tên bài hát được giữ bằng tiếng Anh vì ví dụ dùng .len() và .to_uppercase().)

struct Playlist {
    songs: Vec<String>,
}

impl Playlist {
    fn iter(&self) -> std::slice::Iter<'_, String> {
        self.songs.iter()
    }

    fn iter_mut(&mut self) -> std::slice::IterMut<'_, String> {
        self.songs.iter_mut()
    }
}

// Cho `for song in &playlist` chạy được
impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// Cho `for song in &mut playlist` chạy được
impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// Cho `for song in playlist` chạy được (và dùng hết playlist)
impl IntoIterator for Playlist {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;

    fn into_iter(self) -> Self::IntoIter {
        self.songs.into_iter()
    }
}

fn main() {
    let mut playlist = Playlist {
        songs: vec![String::from("intro"), String::from("main theme"), String::from("outro")],
    };

    for song in &playlist {
        println!("Đang đọc: {}", song);
    }

    for song in &mut playlist {
        *song = song.to_uppercase();
    }

    println!("Dài nhất: {:?}", playlist.iter().max_by_key(|s| s.len()));

    for song in playlist {
        println!("Lấy ra: {}", song);
    }
    // `playlist` đã bị move bởi vòng lặp cuối, nên không dùng được ở đây nữa.
}

Kết quả:

Đang đọc: intro
Đang đọc: main theme
Đang đọc: outro
Dài nhất: Some("MAIN THEME")
Lấy ra: INTRO
Lấy ra: MAIN THEME
Lấy ra: OUTRO

▶ Tự chạy thử

Khá nhiều dòng, nhưng mỗi impl đều có cùng một dạng: nói Item là gì, nói bạn trả về kiểu iterator nào (IntoIter), rồi trả nó về. 'a là một lifetime (vòng đời): nó nói rằng “các phần tử được mượn sống lâu bằng playlist được mượn”. Bạn có thể chép mẫu này cho hầu hết mọi collection bọc quanh một Vec.

Đi ngược và biết độ dài

Có hai trait nữa đáng để biết. Bạn không cần chúng thường xuyên, nhưng các adapter như .rev() và .len() phụ thuộc vào chúng:

• DoubleEndedIterator thêm next_back, lấy phần tử từ cuối. Nó mở khóa .rev().
• ExactSizeIterator hứa rằng iterator biết chính xác còn bao nhiêu phần tử. Nó mở khóa .len(). Bạn cũng cần đưa ra một size_hint chính xác trong Iterator.

// Đưa ra low, low+1, ..., high-1 (giống range low..high)
struct Between {
    low: u32,
    high: u32,
}

impl Iterator for Between {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        let value = self.low;
        self.low += 1;
        Some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let left = self.high.saturating_sub(self.low) as usize;
        (left, Some(left))
    }
}

impl DoubleEndedIterator for Between {
    fn next_back(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        self.high -= 1;
        Some(self.high)
    }
}

impl ExactSizeIterator for Between {}

fn main() {
    let backwards: Vec<u32> = Between { low: 1, high: 6 }.rev().collect();
    println!("{:?}", backwards);

    let mut both_ends = Between { low: 1, high: 6 };
    println!("đầu {:?}, cuối {:?}", both_ends.next(), both_ends.next_back());
    println!("còn lại {}", both_ends.len());
}

Kết quả:

[5, 4, 3, 2, 1]
đầu Some(1), cuối Some(5)
còn lại 3

▶ Tự chạy thử

Hai đầu tiến lại gần nhau, và iterator kết thúc khi chúng gặp nhau. impl ExactSizeIterator for Between {} để trống: len() dùng size_hint mà bạn đã viết.

Lối tắt: from_fn và successors

Viết một struct và một impl rất hợp cho các iterator bạn dùng lại nhiều lần. Còn với một iterator dùng nhanh một lần, thư viện chuẩn có hai hàm hỗ trợ trong std::iter:

• iter::from_fn(closure): gọi closure của bạn mỗi khi cần một giá trị. Closure trả về Some(value) hoặc None, giống hệt next.
• iter::successors(first, closure): bắt đầu với một giá trị đầu tiên, và closure tính mỗi giá trị tiếp theo từ giá trị trước đó. Trả về None thì kết thúc.

use std::iter;

fn main() {
    // from_fn: closure tự giữ trạng thái riêng (count)
    let mut count = 3;
    let countdown: Vec<u32> = iter::from_fn(|| {
        if count == 0 {
            None
        } else {
            count -= 1;
            Some(count + 1)
        }
    })
    .collect();
    println!("{:?}", countdown);

    // successors: mỗi giá trị được tính từ giá trị trước nó
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);

    // Fibonacci trong một dòng: mang theo hai số gần nhất dưới dạng một cặp
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

Kết quả:

[3, 2, 1]
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Tự chạy thử

powers tự dừng lại: lũy thừa tiếp theo của mười, 10.000.000.000, không vừa trong một u32, nên checked_mul trả về None và iterator kết thúc. Một quy tắc tốt: dùng các lối tắt này bên trong một hàm, và viết một struct có tên khi code khác cần tạo iterator đó, hoặc khi nó có nhiều trạng thái.

Lỗi thường gặp

Quên mut khi tự gọi next. next thay đổi iterator, nên biến phải là khả biến (mutable):

let countdown = Countdown { current: 3 };
println!("{:?}", countdown.next());

error[E0596]: cannot borrow `countdown` as mutable, as it is not declared as mutable
  --> src/main.rs:20:22
   |
20 |     println!("{:?}", countdown.next());
   |                      ^^^^^^^^^ cannot borrow as mutable
   |
help: consider changing this to be mutable
   |
19 |     let mut countdown = Countdown { current: 3 };
   |         +++

Trình biên dịch (bằng tiếng Anh) báo rằng không thể mượn countdown dưới dạng khả biến vì nó không được khai báo mut. Hãy thêm mut. (Vòng for không cần điều này: nó lấy iterator và tự lo việc đó cho bạn.)

Quên type Item. Trait cần biết bạn đưa ra thứ gì:

error[E0046]: not all trait items implemented, missing: `Item`
 --> src/main.rs:5:1
  |
5 | impl Iterator for Countdown {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `Item` in implementation
  |
  = help: implement the missing item: `type Item = /* Type */;`

Thông báo nói rằng phần impl còn thiếu Item. Hãy thêm type Item = u32; (hoặc kiểu mà iterator của bạn đưa ra) bên trong impl.

Gom một iterator vô tận. Fibonacci::new().collect::<Vec<_>>() (không có take) biên dịch bình thường, nhưng nó không bao giờ kết thúc theo cách hữu ích: nó chạy cho tới khi các số bị tràn, hoặc chạy mãi nếu next của bạn không bao giờ trả về None. Trình biên dịch không bắt được lỗi này. Khi một iterator có thể là vô tận, hãy luôn thêm take, take_while hoặc find trước khi tiêu thụ nó.

Tóm tắt

• Triển khai Iterator với type Item và fn next(&mut self) -> Option<Self::Item>. Trả về None khi đã xong.
• Khi đã có next, bạn nhận được map, filter, take, sum, zip và hàng chục phương thức khác miễn phí.
• Iterator là lười: không có gì xảy ra cho tới khi một vòng for, collect, sum, v.v. tiêu thụ chúng, và các phần tử chảy qua từng cái một.
• Triển khai IntoIterator cho &MyType, &mut MyType và MyType để hỗ trợ vòng for mượn, mượn khả biến, hoặc tiêu thụ.
• DoubleEndedIterator cho phép dùng .rev(); ExactSizeIterator cho phép dùng .len().
• Với iterator dùng nhanh một lần, hãy dùng std::iter::from_fn hoặc std::iter::successors.

Kiểm tra nhanh

Kiểm tra nhanh

1. next nên trả về gì khi iterator không còn phần tử nào?

0 Một Vec rỗng None Nó nên panic

2. Sau khi chỉ triển khai next, bạn có gọi được .map() và .sum() trên iterator của mình không?

Có, chúng là phương thức mặc định xây trên next Không, bạn phải triển khai từng cái Chỉ khi bạn triển khai thêm IntoIterator

3. Trong ví dụ về tính lười, next() được gọi lần đầu khi nào?

Khi viết .map() Khi viết .take(3) Khi vòng for bắt đầu tiêu thụ chuỗi

4. impl nào giúp for song in &playlist chạy được?

impl Iterator for Playlist impl<'a> IntoIterator for &'a Playlist impl IntoIterator for Playlist impl DoubleEndedIterator for Playlist

5. Bạn cần trait nào để .rev() chạy được trên iterator của mình?

ExactSizeIterator Clone IntoIterator DoubleEndedIterator

Điểm: 0 / 5

Đọc thêm

• Processing a Series of Items with Iterators — The Rust Book (tiếng Anh): Iterator và next hoạt động ra sao, và vì sao iterator là lười.
• Module std::iter (tiếng Anh): hướng dẫn chính thức về iterator, có một phần về tự triển khai iterator và về IntoIterator.
• Trait Iterator — tài liệu std (tiếng Anh): mọi adapter bạn nhận được miễn phí khi đã viết next.
• Iterators — Rust by Example (tiếng Anh): một ví dụ iterator Fibonacci ngắn mà bạn có thể chạy và sửa.
• std::iter::successors (tiếng Anh): tài liệu về cách dựng iterator từ một giá trị bắt đầu và một quy tắc “tiếp theo”.