迭代器

集合类型可以通过 Iterator 特征进行迭代,该特征看起来比 Drop 要复杂点:

#![allow(unused)] fn main() { pub trait Iterator { type Item; fn next(&mut self) -> Option<Self::Item>; } }

这里的 Item关联类型,用来指代迭代器中具体的元素类型,next 方法返回的也是该类型。

其实上面的说法有点不够准确,原因是 next 方法返回的是 Option<Self::Item>,使用 Option<T> 枚举的原因是为了方便用户,不然用户需要 has_nextget_next 才能满足使用需求。有值时返回 Some(T),无值时返回 None,这种 API 设计工程性更好,也更加安全,完美!

有点悲剧的是, Rust 截至目前还没有 yield 语句,因此我们需要自己来实现相关的逻辑。还有点需要注意,每个集合类型应该实现 3 种迭代器类型:

  • IntoIter - T
  • IterMut - &mut T
  • Iter - &T

也许大家不认识它们,但是其实很好理解,IntoIter 类型迭代器的 next 方法会拿走被迭代值的所有权,IterMut 是可变借用, Iter 是不可变借用。事实上,类似的命名规则在 Rust 中随处可见,当熟悉后,以后见到类似的命名大家就可以迅速的理解其对值的运用方式。

IntoIter

先来看看 IntoIter 该怎么实现:

#![allow(unused)] fn main() { pub struct IntoIter<T>(List<T>); impl<T> List<T> { pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { // access fields of a tuple struct numerically self.0.pop() } } }

这里我们通过元组结构体的方式定义了 IntoIter,下面来测试下:

#![allow(unused)] fn main() { #[test] fn into_iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.into_iter(); assert_eq!(iter.next(), Some(3)); assert_eq!(iter.next(), Some(2)); assert_eq!(iter.next(), Some(1)); assert_eq!(iter.next(), None); } }
$ cargo test Running target/debug/lists-5c71138492ad4b4a running 4 tests test first::test::basics ... ok test second::test::basics ... ok test second::test::into_iter ... ok test second::test::peek ... ok test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured

Iter

相对来说,IntoIter 是最好实现的,因为它只是简单的拿走值,不涉及到引用,也不涉及到生命周期,而 Iter 就有所不同了。

这里的基本逻辑是我们持有一个当前节点的指针,当生成一个值后,该指针将指向下一个节点。

#![allow(unused)] fn main() { pub struct Iter<T> { next: Option<&Node<T>>, } impl<T> List<T> { pub fn iter(&self) -> Iter<T> { Iter { next: self.head.map(|node| &node) } } } impl<T> Iterator for Iter<T> { type Item = &T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.map(|node| &node); &node.elem }) } } }
$ cargo build error[E0106]: missing lifetime specifier --> src/second.rs:72:18 | 72 | next: Option<&Node<T>>, | ^ expected lifetime parameter error[E0106]: missing lifetime specifier --> src/second.rs:82:17 | 82 | type Item = &T; | ^ expected lifetime parameter

许久不见的错误又冒了出来,而且这次直指 Rust 中最难的点之一:生命周期。关于生命周期的讲解,这里就不再展开,如果大家还不熟悉,强烈建议看看此章节,然后再继续。

首先,先加一个生命周期试试:

#![allow(unused)] fn main() { pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } }
$ cargo build error[E0106]: missing lifetime specifier --> src/second.rs:83:22 | 83 | impl<T> Iterator for Iter<T> { | ^^^^^^^ expected lifetime parameter error[E0106]: missing lifetime specifier --> src/second.rs:84:17 | 84 | type Item = &T; | ^ expected lifetime parameter error: aborting due to 2 previous errors

好的,现在有了更多的提示,来按照提示修改下代码:

#![allow(unused)] fn main() { pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } impl<'a, T> List<T> { pub fn iter(&'a self) -> Iter<'a, T> { Iter { next: self.head.map(|node| &'a node) } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&'a mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.map(|node| &'a node); &'a node.elem }) } } }
$ cargo build error: expected `:`, found `node` --> src/second.rs:77:47 | 77 | Iter { next: self.head.map(|node| &'a node) } | ---- while parsing this struct ^^^^ expected `:` error: expected `:`, found `node` --> src/second.rs:85:50 | 85 | self.next = node.next.map(|node| &'a node); | ^^^^ expected `:` error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>` --> src/second.rs:77:9 | 77 | Iter { next: self.head.map(|node| &'a node) } | ^^^^ missing `next`

怎么回事。。感觉错误犹如雨后春笋般冒了出来,Rust 是不是被我们搞坏了 :(

现在看来,我们的生命周期是用错了,聪明的同学可能已经看出了端倪,那么再修改下试试;

#![allow(unused)] fn main() { pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } // 这里无需生命周期,因为 List 没有使用生命周期的关联项 impl<T> List<T> { // 这里我们为 `iter` 声明一个生命周期 'a , 此时 `&self` 需要至少和 `Iter` 活得一样久 pub fn iter<'a>(&'a self) -> Iter<'a, T> { Iter { next: self.head.map(|node| &node) } } } // 这里声明生命周期是因为下面的关联类型 Item 需要 impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; // 这里无需更改,因为上面已经处理了. // Self 依然是这么棒 fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.map(|node| &node); &node.elem }) } } }

现在,我们也许可以自信的编译下试试了:

$ cargo build error[E0308]: mismatched types --> src/second.rs:77:22 | 77 | Iter { next: self.head.map(|node| &node) } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>` error[E0308]: mismatched types --> src/second.rs:85:25 | 85 | self.next = node.next.map(|node| &node); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&'a second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

(╯°□°)╯︵ ┻━┻

这么看,生命周期的问题解决了,但是又引入了新的错误。原因在于,我们希望存储 &Node 但是获取的却是 &Box<Node>。嗯,小问题,解引用搞定:

#![allow(unused)] fn main() { impl<T> List<T> { pub fn iter<'a>(&'a self) -> Iter<'a, T> { Iter { next: self.head.map(|node| &*node) } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.map(|node| &*node); &node.elem }) } } }
$ cargo build Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists) error[E0515]: cannot return reference to local data `*node` --> src/second.rs:77:43 | 77 | Iter { next: self.head.map(|node| &*node) } | ^^^^^^ returns a reference to data owned by the current function error[E0507]: cannot move out of borrowed content --> src/second.rs:77:22 | 77 | Iter { next: self.head.map(|node| &*node) } | ^^^^^^^^^ cannot move out of borrowed content error[E0515]: cannot return reference to local data `*node` --> src/second.rs:85:46 | 85 | self.next = node.next.map(|node| &*node); | ^^^^^^ returns a reference to data owned by the current function error[E0507]: cannot move out of borrowed content --> src/second.rs:85:25 | 85 | self.next = node.next.map(|node| &*node); | ^^^^^^^^^ cannot move out of borrowed content

又怎么了! (ノಥ益ಥ)ノ ┻━┻

大家还记得之前章节的内容吗?原因是这里我们忘记了 as_ref ,然后值的所有权被转移到了 map 中,结果我们在内部引用了一个局部值,造成一个悬垂引用:

#![allow(unused)] fn main() { pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } impl<T> List<T> { pub fn iter<'a>(&'a self) -> Iter<'a, T> { Iter { next: self.head.as_ref().map(|node| &*node) } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_ref().map(|node| &*node); &node.elem }) } } }
$ cargo build Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists) error[E0308]: mismatched types --> src/second.rs:77:22 | 77 | Iter { next: self.head.as_ref().map(|node| &*node) } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>` error[E0308]: mismatched types --> src/second.rs:85:25 | 85 | self.next = node.next.as_ref().map(|node| &*node); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box` | = note: expected type `std::option::Option<&'a second::Node<T>>` found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

😭

错误的原因是,as_ref 增加了一层间接引用,需要被移除,这里使用另外一种方式来实现:

#![allow(unused)] fn main() { pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } impl<T> List<T> { pub fn iter<'a>(&'a self) -> Iter<'a, T> { Iter { next: self.head.as_deref() } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_deref(); &node.elem }) } } }
$ cargo build

🎉 🎉 🎉

as_derefas_deref_mut 函数在 Rust 1.40 版本中正式稳定下来。在那之前,你只能在 stable 版本中使用 map(|node| &**node)map(|node| &mut**node) 的方式来替代。

大家可能会觉得 &** 的形式看上去有些烂,没错,确实如此。但是就像一瓶好酒一样,Rust 也随着时间的推进变得越来越好,因此现在我们已经无需再这么做了。事实上,Rust 很擅长隐式地做类似的转换,或者可以称之为 Deref

但是 Deref 在这里并不能很好的完成自己的任务,原因是在闭包中使用 Option<&T> 而不是 &T 对于它来说有些过于复杂了,因此我们需要显式地去帮助它完成任务。好在根据我的经验来看,这种情况还是相当少见的。

事实上,还可以使用另一种方式来实现:

#![allow(unused)] fn main() { self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node); }

这种类型暗示的方式可以使用的原因在于 map 是一个泛型函数:

#![allow(unused)] fn main() { pub fn map<U, F>(self, f: F) -> Option<U> }

turbofish 形式的符号 ::<> 可以告诉编译器我们希望用哪个具体的类型来替代泛型类型,在这种情况里,::<&Node<T>, _> 意味着: 它应该返回一个 &Node<T>。这种方式可以让编译器知道它需要对 &node 应用 deref,这样我们就不用手动的添加 ** 来进行解引用。

好了,既然编译通过,那就写个测试来看看运行结果:

#![allow(unused)] fn main() { #[test] fn iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.iter(); assert_eq!(iter.next(), Some(&3)); assert_eq!(iter.next(), Some(&2)); assert_eq!(iter.next(), Some(&1)); } }
$ cargo test Running target/debug/lists-5c71138492ad4b4a running 5 tests test first::test::basics ... ok test second::test::basics ... ok test second::test::into_iter ... ok test second::test::iter ... ok test second::test::peek ... ok test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured

最后,还有一点值得注意,之前的代码事实上可以应用生命周期消除原则:

#![allow(unused)] fn main() { impl<T> List<T> { pub fn iter<'a>(&'a self) -> Iter<'a, T> { Iter { next: self.head.as_deref() } } } }

这段代码跟以下代码是等价的:

#![allow(unused)] fn main() { impl<T> List<T> { pub fn iter(&self) -> Iter<T> { Iter { next: self.head.as_deref() } } } }

当然,如果你就喜欢生命周期那种自由、飘逸的 feeling,还可以使用 Rust 2018 引入的“显式生命周期消除"语法 '_

#![allow(unused)] fn main() { impl<T> List<T> { pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_deref() } } } }