2.5 Iter
原文链接: https://rust-unofficial.github.io/too-many-lists/second-iter.html
好，来实现 Iter。这次不能指望 List 提供我们想要的一切，得自己动手。基本思路是保存指向「下一个要 yield 的节点」的指针。因为该节点可能不存在（链表为空或迭代已结束），这个引用应该是 Option。yield 一个元素后，要前进到当前节点的 next 节点。
试试看：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| > 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
|
天哪。生命周期。听说过这东西，据说是噩梦。
试试新办法：看到那个 error[E0106] 了吗？那是编译器错误代码。可以用 rustc --explain 来查：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| > rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).
Here are some simple examples of where you'll run into this error:
struct Foo { x: &bool } // error
struct Foo<'a> { x: &'a bool } // correct
enum Bar { A(u8), B(&bool), } // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct
type MyStr = &str; // error
type MyStr<'a> = &'a str; //correct
...
|
呃……这并没解释多少（这些文档假设我们对 Rust 的理解比现在更深）。但看起来应该给结构体加上那些 'a？试试：
1
2
3
| pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| > 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
|
开始看出规律了……凡能加的地方都加上这些小东西：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| > 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 搞坏了。
也许该弄明白 'a 生命周期到底是什么意思。
生命周期会吓跑很多人，因为它改变了我们从编程诞生之初就熟悉的东西。到目前为止我们其实一直在躲避生命周期，尽管它们其实贯穿了我们写的所有程序。
在带垃圾回收的语言里不需要生命周期，因为 GC 会神奇地保证一切活得足够久。Rust 里大多数数据是手动管理的，所以需要别的方案。C 和 C++ 清楚地展示了如果随便让人拿栈上数据的指针会发生什么：无处不在、难以管控的不安全。大致可分两类错误：
生命周期解决这两类问题，而且 99% 的情况下完全透明。
那生命周期是什么？
简单说，生命周期就是程序中某段代码区域（约等于块/作用域）的名字。就这样。引用带上生命周期，就是说它必须在整个区域内有效。不同事物对引用必须/能够存活多久有不同要求。整个生命周期系统本质上是一个约束求解系统，试图最小化每个引用的区域。若成功找到满足所有约束的生命周期集合，程序就能编译！否则会报错说某物活得不够久。
在函数体内通常不能谈论生命周期，也不想谈论。编译器信息齐全，能推断所有约束以找到最短生命周期。但在类型和 API 层面，编译器没有全部信息，需要你告诉它不同生命周期之间的关系，它才能弄清你在做什么。
原则上这些生命周期也可以省略，但那样检查所有借用会变成巨大的全程序分析，产生令人费解的非局部错误。Rust 的系统意味着每个函数体可以独立做借用检查，错误应该相当局部（否则就是类型签名写错了）。
但我们以前在函数签名里写过引用，也没问题啊！那是因为有些情况太常见，Rust 会自动替你选生命周期。这就是生命周期省略。
具体来说：
1
2
3
4
5
6
7
8
9
10
11
| // 输入只有一个引用，输出必须来自该输入
fn foo(&A) -> &B; // 糖化为：
fn foo<'a>(&'a A) -> &'a B;
// 多个输入，假定彼此独立
fn foo(&A, &B, &C); // 糖化为：
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);
// 方法：假定所有输出生命周期都来自 `self`
fn foo(&self, &B, &C) -> &D; // 糖化为：
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;
|
那 fn foo<'a>(&'a A) -> &'a B 意味着什么？实际上就是说输入至少得和输出活得一样久。如果你把输出留很久，就会扩大输入必须有效的区域。一旦不再使用输出，编译器就知道输入也可以失效了。
有了这个系统，Rust 能确保没有 use-after-free，也没有在仍有未归还引用时发生变异。只要保证所有约束能成立就行！
好。那么。Iter。
先回滚到没有生命周期的状态：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
})
}
}
|
我们只需要在函数和类型签名里加生命周期：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| // Iter 对*某个*生命周期泛型，它并不关心具体是哪个
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
// 这里没有生命周期，List 没有关联的生命周期
impl<T> List<T> {
// 为创建 iter 的*确切*借用声明一个新的生命周期。
// 现在 &self 必须在 Iter 存在期间一直有效。
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &node) }
}
}
// 这里*确实*有生命周期，因为 Iter 有，我们需要定义它
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
})
}
}
|
好，这次应该对了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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>。好办，在取引用前先解引用 Box：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| cargo build
Compiling lists v0.1.0 (/Users/ADesires/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，于是把 Box 移进 map，会被 drop，引用就悬空了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| cargo build
Compiling lists v0.1.0 (/Users/ADesires/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 又加了一层间接，还得剥掉：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
})
}
}
|
🎉 🎉 🎉
as_deref 和 as_deref_mut 自 Rust 1.40 起稳定。在此之前得写 map(|node| &**node) 和 map(|node| &mut**node)。你可能在想「哇这 &** 真别扭」，没错，但就像好酒，Rust 越陈越好，我们不必再这么写了。通常 Rust 很擅长通过解引用强制隐式做这种转换，也就是在代码里插入 * 让类型对上。能这么做是因为有借用检查器保证我们不会搞砸指针！
但这里闭包加上 Option<&T> 而不是 &T 有点复杂，编译器推不出来，得显式帮忙。好在以我经验这挺少见。
为完整起见，我们可以用turbofish给另一种提示：
1
| self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);
|
看，map 是泛型函数：
1
| pub fn map<U, F>(self, f: F) -> Option<U>
|
turbofish ::<> 让我们告诉编译器那些泛型参数应该是什么类型。这里 ::<&Node<T>, _> 表示「应返回 &Node<T>，另一个类型我不知道/不在乎」。
这样编译器就知道应对 &node 做解引用强制，不必手动加一堆 *！
但我觉得这里不算改进，只是借机展示解引用强制和有时有用的 turbofish。😅
写个测试确认没写成空操作：
1
2
3
4
5
6
7
8
9
10
| #[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));
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| > 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
|
太棒了。
最后说明一下，这里其实可以应用生命周期省略：
1
2
3
4
5
| impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.as_deref() }
}
}
|
等价于：
1
2
3
4
5
| impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.as_deref() }
}
}
|
耶，更少的生命周期！
若不习惯「隐藏」结构体含有生命周期，可以用 Rust 2018 的「显式省略生命周期」语法 '_：
1
2
3
4
5
| impl<T> List<T> {
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
}
|