【Rust 进阶教程】 02 详解迭代器（1）

0x00 开篇

在 《学习日记 21课》我们仅仅是简单介绍了迭代器的基础使用方法。在平时的工作中，迭代器的使用频率是非常高的，再加上 Rust 所有权的概念，这就可能导致迭代器的理解有了一定的难度。本篇文章我们将更深入的认识迭代器。本篇文章阅读时间大约 8 分钟。

0x01 Iterator

前面我们了解到，迭代器是一个 trait，源码如下：

pub trait Iterator {
    type Item;
    
    fn next(&mut self) -> Option<Self::Item>;
    
    fn for_each<F>(self, f: F) where
        Self: Sized,
        F: FnMut(Self::Item), {
        // ...
    }
    // 其它所有方法...
}

在 Rust 中，迭代器是惰性的，只有当在被调用时才会执行相应的操作。惰性迭代器 的设计目的是为了减少内存占用和提高效率。因为迭代器只有在被调用时才执行，所以不需要在创建时保存所有的结果，这样可以减少内存占用。解释下它的字段，字段 Item 就是迭代器返回的类型了，next 只能返回 Some 或者 None，当第一次返回 None 时，迭代器将终止（为什么将第一次加粗，后面会解释）。

0x02 IntoIterator

我们通常习惯使用 for 来遍历 Vec 向量。那其实它就需要来实现 core::iter::traits::IntoIterator（接口定义如下）。

pub trait IntoIterator {
    type Item;

    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}

像下面类似的代码：

	// for 遍历
    let mut vec = vec![1, 2, 3];
    for i in vec {
        println!("{}", i);
    }

    // 等价简写为下面的代码
    let mut vec = vec![1, 2, 3];
    let mut iterator = vec.into_iter();
    while let Some(i) = iterator.next() {
        println!("{}", i);
    }

其实等价于先执行了 into_iter() 方法，将其转化为一个迭代器，然后再执行迭代器 IntoIter 的 next 方法，当返回 None 是结束循坏。下面是调试过程的 gif 图，可以清楚的看到 for 循坏执行的内部逻辑。

另外，所有的迭代器都会自动实现 IntoIterator ，这也就意味着所有实现 Iterator 的都会自动实现 IntoIterator。因而我们会有一个 into_iter() 方法。一般情况下，我们并不需要手动实现。示例代码如下：

struct Example(i32);

// 为Example实现一个迭代器
impl Iterator for Example {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        // 如果它的值 % 10 != 0 则返回 Some，否则返回None
        return if self.0 % 10 == 0 {
            self.0 += 1;
            Some(self.0)
        } else {
            self.0 += 1;
            None
        };
    }
}

fn main() {
    let example = Example(8);
    for item in example.into_iter() {
        println!("item = {}", item);
    }
}
// 运行结果
// item = 9
// item = 10

0x03 熔断（fuse）

迭代器存在 Some、None 交替返回时，如何终止？

仔细看上面的代码，当我创建了 let example = Example(8)， 执行迭代器方法累加到 10 时，它返回 None。如果我再次执行 next() 它又会自增 1，返回 Some。会出现 Some、None 交替返回的情况。但是当迭代器第一次返回 None 时就会终止。

如何熔断？

对于大部分的迭代器（next 方法）都不会出现 None 、Some 交替返回的现象，上面的示例基本是意外了。但是为防止这种意外发生，  Rust 提供了 熔断 的方法，一旦迭代的值出现 None，后续不会再次出现 Some。在创建 Example 后，调用 fuse 方法，即可触发熔断机制。示例代码如下：

fn main() {
	let mut example = Example(8);
    println!("未熔断 {:?}", example.next());
    println!("未熔断 {:?}", example.next());
    println!("未熔断 {:?}", example.next());
    println!("未熔断 {:?}", example.next());
    println!("未熔断 {:?}", example.next());

    println!("---------------------");

    let mut example = Example(8).fuse();
    println!("熔断后 {:?}", example.next());
    println!("熔断后 {:?}", example.next());
    println!("熔断后 {:?}", example.next());
    println!("熔断后 {:?}", example.next());
    println!("熔断后 {:?}", example.next());
}
// 运行结果
// 未熔断 Some(9)
// 未熔断 Some(10)
// 未熔断 None
// 未熔断 Some(12)
// 未熔断 Some(13)
// ---------------------
// 熔断后 Some(9)
// 熔断后 Some(10)
// 熔断后 None
// 熔断后 None
// 熔断后 None

fuse 的原理（扩展阅读）

fuse 的场景应该比较少见，简单解释下原理吧。先上源码：

// std::iter::traits::Iterator 
fn fuse(self) -> Fuse<Self>
    where
        Self: Sized,
    {
        Fuse::new(self)
    }

// std::iter::adapters::fuse
// Fuse 结构体
pub struct Fuse<I> {
    iter: Option<I>,
}

// Fuse 的 next 方法
#[inline]
fn next(&mut self) -> Option<Self::Item> {
   FuseImpl::next(self)
}

// Fuse 实现类
impl<I> FuseImpl<I> for Fuse<I>
where
    I: Iterator,
{
    type Item = <I as Iterator>::Item;

    #[inline]
    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
        and_then_or_clear(&mut self.iter, Iterator::next)
    }
    
    // 省略其它方法...
}

// 关键方法
// next 最终会调用此方法
#[inline]
fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> {
    let x = f(opt.as_mut()?);
    if x.is_none() {
        *opt = None;
    }
    x
}

一些主要的方法我都列了出来。我们调用迭代器的 fuse 方法时，会创建一个 Fuse 实例。Fuse 只有一个私有字段 iter ，表示我们传入的迭代器。当我们调用 next 方法时，实际上是调用了 Fuse 的 next 方法，最终间接的调用了关键方法 and_then_or_clear。这里解释下这个方法，就明白原理了。

它接收两个参数：一个可变的Option<T> 类型（其实传入的就是我们之前创建的迭代器）和一个闭包 f（迭代器的回调）。首先调用 opt.as_mut() 方法获取可变引用，如果 opt 为 None 则直接返回 None，然后将结果回调出去。下面再判断如果 x 是 None。直接修改前面传入的迭代器为 None。这也就意味着，一旦出现 None，后续的返回结果都是 None。因为 Fuse 实例中保存的字段已经被重置为 None 了。PS：大家可以自己下断点验证下。

0x04 小结

本篇文章主要介绍了 for 循环的底层原理，其实算是一个迭代器的语法糖吧。关于迭代器的熔断，大家可以只做了解，应用场景应该不是很多。本来想一篇文章说完，不知不觉还是写了这么多字了，只能分两篇来写了，下一篇继续介绍吧。