Rust 使用迭代器處理元素序列

·ch13-02-iterators.md
commit f207d4125b28f51a9bd962b3232cdea925660073

迭代器模式允許你對(duì)一個(gè)序列的項(xiàng)進(jìn)行某些處理。迭代器（iterator）負(fù)責(zé)遍歷序列中的每一項(xiàng)和決定序列何時(shí)結(jié)束的邏輯。當(dāng)使用迭代器時(shí)，我們無需重新實(shí)現(xiàn)這些邏輯。

在 Rust 中，迭代器是 惰性的（lazy），這意味著在調(diào)用方法使用迭代器之前它都不會(huì)有效果。例如，示例 13-13 中的代碼通過調(diào)用定義于 Vec 上的 iter 方法在一個(gè) vector v1 上創(chuàng)建了一個(gè)迭代器。這段代碼本身沒有任何用處：

    let v1 = vec![1, 2, 3];

    let v1_iter = v1.iter();

示例 13-13：創(chuàng)建一個(gè)迭代器

一旦創(chuàng)建迭代器之后，可以選擇用多種方式利用它。在第三章的示例 3-5 中，我們使用迭代器和 for 循環(huán)在每一個(gè)項(xiàng)上執(zhí)行了一些代碼，雖然直到現(xiàn)在為止我們一直沒有具體討論調(diào)用 iter 到底具體做了什么。

示例 13-14 中的例子將迭代器的創(chuàng)建和 for 循環(huán)中的使用分開。迭代器被儲(chǔ)存在 v1_iter 變量中，而這時(shí)沒有進(jìn)行迭代。一旦 for 循環(huán)開始使用 v1_iter，接著迭代器中的每一個(gè)元素被用于循環(huán)的一次迭代，這會(huì)打印出其每一個(gè)值：

    let v1 = vec![1, 2, 3];

    let v1_iter = v1.iter();

    for val in v1_iter {
        println!("Got: {}", val);
    }

示例 13-14：在一個(gè) ?for? 循環(huán)中使用迭代器

在標(biāo)準(zhǔn)庫(kù)中沒有提供迭代器的語(yǔ)言中，我們可能會(huì)使用一個(gè)從 0 開始的索引變量，使用這個(gè)變量索引 vector 中的值，并循環(huán)增加其值直到達(dá)到 vector 的元素?cái)?shù)量。

迭代器為我們處理了所有這些邏輯，這減少了重復(fù)代碼并消除了潛在的混亂。另外，迭代器的實(shí)現(xiàn)方式提供了對(duì)多種不同的序列使用相同邏輯的靈活性，而不僅僅是像 vector 這樣可索引的數(shù)據(jù)結(jié)構(gòu).讓我們看看迭代器是如何做到這些的。

Iterator trait 和 next 方法

迭代器都實(shí)現(xiàn)了一個(gè)叫做 Iterator 的定義于標(biāo)準(zhǔn)庫(kù)的 trait。這個(gè) trait 的定義看起來像這樣：

pub trait Iterator {
    type Item;

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

    // 此處省略了方法的默認(rèn)實(shí)現(xiàn)
}

注意這里有一個(gè)我們還未講到的新語(yǔ)法：type Item 和 Self::Item，他們定義了 trait 的 關(guān)聯(lián)類型（associated type）。第十九章會(huì)深入講解關(guān)聯(lián)類型，不過現(xiàn)在只需知道這段代碼表明實(shí)現(xiàn) Iterator trait 要求同時(shí)定義一個(gè) Item 類型，這個(gè) Item 類型被用作 next 方法的返回值類型。換句話說，Item 類型將是迭代器返回元素的類型。

next 是 Iterator 實(shí)現(xiàn)者被要求定義的唯一方法。next 一次返回迭代器中的一個(gè)項(xiàng)，封裝在 Some 中，當(dāng)?shù)鹘Y(jié)束時(shí)，它返回 None。

可以直接調(diào)用迭代器的 next 方法；示例 13-15 有一個(gè)測(cè)試展示了重復(fù)調(diào)用由 vector 創(chuàng)建的迭代器的 next 方法所得到的值：

文件名: src/lib.rs

    #[test]
    fn iterator_demonstration() {
        let v1 = vec![1, 2, 3];

        let mut v1_iter = v1.iter();

        assert_eq!(v1_iter.next(), Some(&1));
        assert_eq!(v1_iter.next(), Some(&2));
        assert_eq!(v1_iter.next(), Some(&3));
        assert_eq!(v1_iter.next(), None);
    }

示例 13-15：在迭代器上（直接）調(diào)用 next 方法

注意 v1_iter 需要是可變的：在迭代器上調(diào)用 next 方法改變了迭代器中用來記錄序列位置的狀態(tài)。換句話說，代碼 消費(fèi)（consume）了，或使用了迭代器。每一個(gè) next 調(diào)用都會(huì)從迭代器中消費(fèi)一個(gè)項(xiàng)。使用 for 循環(huán)時(shí)無需使 v1_iter 可變因?yàn)?nbsp;for 循環(huán)會(huì)獲取 v1_iter 的所有權(quán)并在后臺(tái)使 v1_iter 可變。

另外需要注意到從 next 調(diào)用中得到的值是 vector 的不可變引用。iter 方法生成一個(gè)不可變引用的迭代器。如果我們需要一個(gè)獲取 v1 所有權(quán)并返回?fù)碛兴袡?quán)的迭代器，則可以調(diào)用 into_iter 而不是 iter。類似的，如果我們希望迭代可變引用，則可以調(diào)用 iter_mut 而不是 iter。

消費(fèi)迭代器的方法

Iterator trait 有一系列不同的由標(biāo)準(zhǔn)庫(kù)提供默認(rèn)實(shí)現(xiàn)的方法；你可以在 Iterator trait 的標(biāo)準(zhǔn)庫(kù) API 文檔中找到所有這些方法。一些方法在其定義中調(diào)用了 next 方法，這也就是為什么在實(shí)現(xiàn) Iterator trait 時(shí)要求實(shí)現(xiàn) next 方法的原因。

這些調(diào)用 next 方法的方法被稱為 消費(fèi)適配器（consuming adaptors），因?yàn)檎{(diào)用他們會(huì)消耗迭代器。一個(gè)消費(fèi)適配器的例子是 sum 方法。這個(gè)方法獲取迭代器的所有權(quán)并反復(fù)調(diào)用 next 來遍歷迭代器，因而會(huì)消費(fèi)迭代器。當(dāng)其遍歷每一個(gè)項(xiàng)時(shí)，它將每一個(gè)項(xiàng)加總到一個(gè)總和并在迭代完成時(shí)返回總和。示例 13-16 有一個(gè)展示 sum 方法使用的測(cè)試：

文件名: src/lib.rs

    #[test]
    fn iterator_sum() {
        let v1 = vec![1, 2, 3];

        let v1_iter = v1.iter();

        let total: i32 = v1_iter.sum();

        assert_eq!(total, 6);
    }

示例 13-16：調(diào)用 ?sum? 方法獲取迭代器所有項(xiàng)的總和

調(diào)用 sum 之后不再允許使用 v1_iter 因?yàn)檎{(diào)用 sum 時(shí)它會(huì)獲取迭代器的所有權(quán)。

產(chǎn)生其他迭代器的方法

Iterator trait 中定義了另一類方法，被稱為 迭代器適配器（iterator adaptors），他們?cè)试S我們將當(dāng)前迭代器變?yōu)椴煌愋偷牡??？梢枣準(zhǔn)秸{(diào)用多個(gè)迭代器適配器。不過因?yàn)樗械牡鞫际嵌栊缘?，必須調(diào)用一個(gè)消費(fèi)適配器方法以便獲取迭代器適配器調(diào)用的結(jié)果。

示例 13-17 展示了一個(gè)調(diào)用迭代器適配器方法 map 的例子，該 map 方法使用閉包來調(diào)用每個(gè)元素以生成新的迭代器。 這里的閉包創(chuàng)建了一個(gè)新的迭代器，對(duì)其中 vector 中的每個(gè)元素都被加 1。不過這些代碼會(huì)產(chǎn)生一個(gè)警告：

文件名: src/main.rs

    let v1: Vec<i32> = vec![1, 2, 3];

    v1.iter().map(|x| x + 1);

示例 13-17：調(diào)用迭代器適配器 ?map? 來創(chuàng)建一個(gè)新迭代器

得到的警告是：

$ cargo run
   Compiling iterators v0.1.0 (file:///projects/iterators)
warning: unused `Map` that must be used
 --> src/main.rs:4:5
  |
4 |     v1.iter().map(|x| x + 1);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_must_use)]` on by default
  = note: iterators are lazy and do nothing unless consumed

warning: `iterators` (bin "iterators") generated 1 warning
    Finished dev [unoptimized + debuginfo] target(s) in 0.47s
     Running `target/debug/iterators`

示例 13-17 中的代碼實(shí)際上并沒有做任何事；所指定的閉包從未被調(diào)用過。警告提醒了我們?yōu)槭裁矗旱鬟m配器是惰性的，而這里我們需要消費(fèi)迭代器。

為了修復(fù)這個(gè)警告并消費(fèi)迭代器獲取有用的結(jié)果，我們將使用第十二章示例 12-1 結(jié)合 env::args 使用的 collect 方法。這個(gè)方法消費(fèi)迭代器并將結(jié)果收集到一個(gè)數(shù)據(jù)結(jié)構(gòu)中。

在示例 13-18 中，我們將遍歷由 map 調(diào)用生成的迭代器的結(jié)果收集到一個(gè) vector 中，它將會(huì)含有原始 vector 中每個(gè)元素加 1 的結(jié)果：

文件名: src/main.rs

    let v1: Vec<i32> = vec![1, 2, 3];

    let v2: Vec<_> = v1.iter().map(|x| x + 1).collect();

    assert_eq!(v2, vec![2, 3, 4]);

示例 13-18：調(diào)用 ?map? 方法創(chuàng)建一個(gè)新迭代器，接著調(diào)用 ?collect? 方法消費(fèi)新迭代器并創(chuàng)建一個(gè) vector

因?yàn)?nbsp;map 獲取一個(gè)閉包，可以指定任何希望在遍歷的每個(gè)元素上執(zhí)行的操作。這是一個(gè)展示如何使用閉包來自定義行為同時(shí)又復(fù)用 Iterator trait 提供的迭代行為的絕佳例子。

使用閉包獲取環(huán)境

現(xiàn)在我們介紹了迭代器，讓我們展示一個(gè)通過使用 filter 迭代器適配器和捕獲環(huán)境的閉包的常規(guī)用例。迭代器的 filter 方法獲取一個(gè)使用迭代器的每一個(gè)項(xiàng)并返回布爾值的閉包。如果閉包返回 true，其值將會(huì)包含在 filter 提供的新迭代器中。如果閉包返回 false，其值不會(huì)包含在結(jié)果迭代器中。

示例 13-19 展示了使用 filter 和一個(gè)捕獲環(huán)境中變量 shoe_size 的閉包，這樣閉包就可以遍歷一個(gè) Shoe 結(jié)構(gòu)體集合以便只返回指定大小的鞋子：

文件名: src/lib.rs

#[derive(PartialEq, Debug)]
struct Shoe {
    size: u32,
    style: String,
}

fn shoes_in_size(shoes: Vec<Shoe>, shoe_size: u32) -> Vec<Shoe> {
    shoes.into_iter().filter(|s| s.size == shoe_size).collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn filters_by_size() {
        let shoes = vec![
            Shoe {
                size: 10,
                style: String::from("sneaker"),
            },
            Shoe {
                size: 13,
                style: String::from("sandal"),
            },
            Shoe {
                size: 10,
                style: String::from("boot"),
            },
        ];

        let in_my_size = shoes_in_size(shoes, 10);

        assert_eq!(
            in_my_size,
            vec![
                Shoe {
                    size: 10,
                    style: String::from("sneaker")
                },
                Shoe {
                    size: 10,
                    style: String::from("boot")
                },
            ]
        );
    }
}

示例 13-19：使用 filter 方法和一個(gè)捕獲 shoe_size 的閉包

shoes_in_my_size 函數(shù)獲取一個(gè)鞋子 vector 的所有權(quán)和一個(gè)鞋子大小作為參數(shù)。它返回一個(gè)只包含指定大小鞋子的 vector。

shoes_in_my_size 函數(shù)體中調(diào)用了 into_iter 來創(chuàng)建一個(gè)獲取 vector 所有權(quán)的迭代器。接著調(diào)用 filter 將這個(gè)迭代器適配成一個(gè)只含有那些閉包返回 true 的元素的新迭代器。

閉包從環(huán)境中捕獲了 shoe_size 變量并使用其值與每一只鞋的大小作比較，只保留指定大小的鞋子。最終，調(diào)用 collect 將迭代器適配器返回的值收集進(jìn)一個(gè) vector 并返回。

這個(gè)測(cè)試展示當(dāng)調(diào)用 shoes_in_my_size 時(shí)，我們只會(huì)得到與指定值相同大小的鞋子。

實(shí)現(xiàn) Iterator trait 來創(chuàng)建自定義迭代器

我們已經(jīng)展示了可以通過在 vector 上調(diào)用 iter、into_iter 或 iter_mut 來創(chuàng)建一個(gè)迭代器。也可以用標(biāo)準(zhǔn)庫(kù)中其他的集合類型創(chuàng)建迭代器，比如哈希 map。另外，可以實(shí)現(xiàn) Iterator trait 來創(chuàng)建任何我們希望的迭代器。正如之前提到的，定義中唯一要求提供的方法就是 next 方法。一旦定義了它，就可以使用所有其他由 Iterator trait 提供的擁有默認(rèn)實(shí)現(xiàn)的方法來創(chuàng)建自定義迭代器了！

作為展示，讓我們創(chuàng)建一個(gè)只會(huì)從 1 數(shù)到 5 的迭代器。首先，創(chuàng)建一個(gè)結(jié)構(gòu)體來存放一些值，接著實(shí)現(xiàn) Iterator trait 將這個(gè)結(jié)構(gòu)體放入迭代器中并在此實(shí)現(xiàn)中使用其值。

示例 13-20 有一個(gè) Counter 結(jié)構(gòu)體定義和一個(gè)創(chuàng)建 Counter 實(shí)例的關(guān)聯(lián)函數(shù) new：

文件名: src/lib.rs

struct Counter {
    count: u32,
}

impl Counter {
    fn new() -> Counter {
        Counter { count: 0 }
    }
}

示例 13-20：定義 Counter 結(jié)構(gòu)體和一個(gè)創(chuàng)建 count 初值為 0 的 Counter 實(shí)例的 new 函數(shù)

Counter 結(jié)構(gòu)體有一個(gè)字段 count。這個(gè)字段存放一個(gè) u32 值，它會(huì)記錄處理 1 到 5 的迭代過程中的位置。count 是私有的因?yàn)槲覀兿Ｍ?nbsp;Counter 的實(shí)現(xiàn)來管理這個(gè)值。new 函數(shù)通過總是從為 0 的 count 字段開始新實(shí)例來確保我們需要的行為。

接下來將為 Counter 類型實(shí)現(xiàn) Iterator trait，通過定義 next 方法來指定使用迭代器時(shí)的行為，如示例 13-21 所示：

文件名: src/lib.rs

impl Iterator for Counter {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.count < 5 {
            self.count += 1;
            Some(self.count)
        } else {
            None
        }
    }
}

示例 13-21：在 Counter 結(jié)構(gòu)體上實(shí)現(xiàn) Iterator trait

這里將迭代器的關(guān)聯(lián)類型 Item 設(shè)置為 u32，意味著迭代器會(huì)返回 u32 值集合。再一次，這里仍無需擔(dān)心關(guān)聯(lián)類型，第十九章會(huì)講到。

我們希望迭代器對(duì)其內(nèi)部狀態(tài)加一，這也就是為何將 count 初始化為 0：我們希望迭代器首先返回 1。如果 count 值小于 6，next 會(huì)返回封裝在 Some 中的當(dāng)前值，不過如果 count 大于或等于 6，迭代器會(huì)返回 None。

使用 Counter 迭代器的 next 方法

一旦實(shí)現(xiàn)了 Iterator trait，我們就有了一個(gè)迭代器！示例 13-22 展示了一個(gè)測(cè)試用來演示使用 Counter 結(jié)構(gòu)體的迭代器功能，通過直接調(diào)用 next 方法，正如示例 13-15 中從 vector 創(chuàng)建的迭代器那樣：

文件名: src/lib.rs

    #[test]
    fn calling_next_directly() {
        let mut counter = Counter::new();

        assert_eq!(counter.next(), Some(1));
        assert_eq!(counter.next(), Some(2));
        assert_eq!(counter.next(), Some(3));
        assert_eq!(counter.next(), Some(4));
        assert_eq!(counter.next(), Some(5));
        assert_eq!(counter.next(), None);
    }

示例 13-22：測(cè)試 next 方法實(shí)現(xiàn)的功能

這個(gè)測(cè)試在 counter 變量中新建了一個(gè) Counter 實(shí)例并接著反復(fù)調(diào)用 next 方法，來驗(yàn)證我們實(shí)現(xiàn)的行為符合這個(gè)迭代器返回從 1 到 5 的值的預(yù)期。

使用自定義迭代器中其他 Iterator trait 方法

通過定義 next 方法實(shí)現(xiàn) Iterator trait，我們現(xiàn)在就可以使用任何標(biāo)準(zhǔn)庫(kù)定義的擁有默認(rèn)實(shí)現(xiàn)的 Iterator trait 方法了，因?yàn)樗麄兌际褂昧?nbsp;next 方法的功能。

例如，出于某種原因我們希望獲取 Counter 實(shí)例產(chǎn)生的值，將這些值與另一個(gè) Counter 實(shí)例在省略了第一個(gè)值之后產(chǎn)生的值配對(duì)，將每一對(duì)值相乘，只保留那些可以被三整除的結(jié)果，然后將所有保留的結(jié)果相加，這可以如示例 13-23 中的測(cè)試這樣做：

文件名: src/lib.rs

    #[test]
    fn using_other_iterator_trait_methods() {
        let sum: u32 = Counter::new()
            .zip(Counter::new().skip(1))
            .map(|(a, b)| a * b)
            .filter(|x| x % 3 == 0)
            .sum();
        assert_eq!(18, sum);
    }

示例 13-23：使用自定義的 Counter 迭代器的多種方法

注意 zip 只產(chǎn)生四對(duì)值；理論上第五對(duì)值 (5, None) 從未被產(chǎn)生，因?yàn)?nbsp;zip 在任一輸入迭代器返回 None 時(shí)也返回 None。

所有這些方法調(diào)用都是可能的，因?yàn)槲覀冎付?nbsp;next 方法如何工作，而標(biāo)準(zhǔn)庫(kù)則提供了其它調(diào)用 next 的方法的默認(rèn)實(shí)現(xiàn)。