4.6 迭代
原文链接: https://rust-unofficial.github.io/too-many-lists/fourth-iteration.html
我们来试试迭代这货。
IntoIter
和往常一样，IntoIter 会是最容易的那个。只需包装栈并调用 pop：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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> {
self.0.pop_front()
}
}
|
但我们遇到了一个有趣的新情况。以前我们的链表只有一种"自然"的迭代顺序，而双端队列天生是双向的。从前到后有什么特别的？如果有人想反方向迭代呢？
Rust 对此有答案：DoubleEndedIterator。DoubleEndedIterator继承自 Iterator（意味着所有 DoubleEndedIterator 都是 Iterator），并要求一个新方法：next_back。它的签名与 next 完全相同，但应该从另一端产出元素。DoubleEndedIterator 的语义对我们非常方便：迭代器变成双端队列。你可以从前后两端消费元素，直到两端汇合，此时迭代器为空。
和 Iterator 与 next 类似，next_back 也不是 DoubleEndedIterator 的消费者真正关心的。这个接口最好的部分是它暴露了 rev 方法，它包装迭代器以产生一个反向产出元素的新迭代器。语义相当直接：对反向迭代器的 next 调用就是对 next_back 的调用。
总之，既然我们已经是双端队列，提供这个 API 相当容易：
1
2
3
4
5
| impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.0.pop_back()
}
}
|
来测试一下：
1
2
3
4
5
6
7
8
9
10
11
12
| #[test]
fn into_iter() {
let mut list = List::new();
list.push_front(1); list.push_front(2); list.push_front(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next_back(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(), None);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| cargo test
Running target/debug/lists-5c71138492ad4b4a
running 11 tests
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::iter ... ok
test third::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test result: ok. 11 passed; 0 failed; 0 ignored; 0 measured
|
不错。
Iter
Iter 会没那么宽容。我们得再次对付那些糟糕的 Ref！因为 Ref，我们不能像之前那样存储 &Node。相反，我们试试存储 Ref<Node>：
1
2
3
4
5
6
7
| pub struct Iter<'a, T>(Option<Ref<'a, Node<T>>>);
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter(self.head.as_ref().map(|head| head.borrow()))
}
}
|
目前还好。实现 next 会有点棘手，但我觉得基本逻辑和旧的栈 IterMut 一样，只是多了 RefCell 的疯狂：
1
2
3
4
5
6
7
8
9
| impl<'a, T> Iterator for Iter<'a, T> {
type Item = Ref<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| {
self.0 = node_ref.next.as_ref().map(|head| head.borrow());
Ref::map(node_ref, |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
error[E0521]: borrowed data escapes outside of closure
--> src/fourth.rs:155:13
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` is declared here, outside of the closure body
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ^^^^^^ -------- borrow is only valid in the closure body
| |
| reference to `node_ref` escapes the closure body here
error[E0505]: cannot move out of `node_ref` because it is borrowed
--> src/fourth.rs:156:22
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- lifetime `'1` appears in the type of `self`
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ------ -------- borrow of `node_ref` occurs here
| |
| assignment requires that `node_ref` is borrowed for `'1`
156 | Ref::map(node_ref, |node| &node.elem)
| ^^^^^^^^ move out of `node_ref` occurs here
|
糟了。
node_ref 存活得不够久。与普通引用不同，Rust 不允许我们那样拆分 Ref。我们从 head.borrow() 得到的 Ref 只能活到 node_ref 那么久，但我们在 Ref::map 调用中把它毁掉了。
我们想要的函数存在，叫做 [map_split][]：
1
2
3
4
| pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
F: FnOnce(&T) -> (&U, &V),
U: ?Sized,
V: ?Sized,
|
哇。我们来试试……
1
2
3
4
5
6
7
8
9
10
11
| fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| {
let (next, elem) = Ref::map_split(node_ref, |node| {
(&node.next, &node.elem)
});
self.0 = next.as_ref().map(|head| head.borrow());
elem
})
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| cargo build
Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
--> src/fourth.rs:159:13
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` is declared here, outside of the closure body
...
159 | self.0 = next.as_ref().map(|head| head.borrow());
| ^^^^^^ ---- borrow is only valid in the closure body
| |
| reference to `next` escapes the closure body here
|
呃。我们得再用 Ref::Map 来让生命周期正确。但 Ref::Map 返回 Ref，而我们需要 Option<Ref>，但我们得通过 Ref 来对 Option 做 map……
凝视远方很久
??????
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| {
let (next, elem) = Ref::map_split(node_ref, |node| {
(&node.next, &node.elem)
});
self.0 = if next.is_some() {
Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
} else {
None
};
elem
})
}
|
1
2
3
4
5
6
7
8
| error[E0308]: mismatched types
--> src/fourth.rs:162:22
|
162 | Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
|
= note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`
|
哦。对了。有多个 RefCell。我们越深入链表，在每个 RefCell 下嵌套得越深。我们需要维护，比如，一个 Ref 栈来表示所有未偿还的借用，因为如果我们停止查看某个元素，就需要减少它之前每个 RefCell 的借用计数…………
我觉得这里无能为力。这是死胡同。我们试试摆脱 RefCell。
那我们的 Rc 呢。谁说我们一定需要存储引用？为什么不能直接 Clone 整个 Rc 来获得一个指向链表中间的拥有型句柄？
1
2
3
4
5
6
7
8
9
10
| pub struct Iter<T>(Option<Rc<Node<T>>>);
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter(self.head.as_ref().map(|head| head.clone()))
}
}
impl<T> Iterator for Iter<T> {
type Item =
|
呃……等等我们现在返回什么？&T？Ref<T>？
不，这些都不行……我们的 Iter 没有生命周期了！&T 和 Ref<T> 都要求我们在进入 next 之前先声明某个生命周期。但我们从 Rc 里能拿到的任何东西都是在借用 Iterator……脑子……疼……啊啊啊啊啊
也许我们可以……map……Rc……来得到 Rc<T>？有这种事吗？Rc 的文档里好像没有类似的东西。实际上有人做了一个 crate 让你能做到。
但等等，即使我们那样做了，我们还有一个更大的问题：迭代器失效的幽灵。以前我们完全免疫迭代器失效，因为 Iter 借用了链表，让它完全不可变。然而如果我们的 Iter 产出 Rc，它们根本不会借用链表！这意味着人们可以在持有指向链表的指针时开始调用 push 和 pop！
天哪，那会怎样？！
嗯，push 其实没问题。我们持有链表某个子范围的视图，链表会在我们视野之外增长。没什么大不了的。
然而 pop 是另一回事。如果他们在我们的范围之外弹出元素，仍然应该没问题。我们看不到那些节点，所以什么也不会发生。然而如果他们试图弹出我们指向的节点……一切都会爆炸！特别是当他们去 try_unwrap 的结果时，实际上会失败，整个程序会 panic。
这其实挺酷的。我们可以获得大量指向链表内部的拥有型指针，同时修改链表，而且只要能用，直到他们试图移除我们指向的节点。即使那样我们也不会得到悬垂指针，程序会确定性地 panic！
但在映射 Rc 之上还要处理迭代器失效……似乎……很糟。Rc<RefCell> 真的终于让我们失望了。有趣的是，我们经历了与持久化栈相反的情况。持久化栈难以收回数据的所有权，但可以整天获取引用；我们的链表获取所有权没问题，但借出引用真的很挣扎。
不过公平地说，我们的大部分挣扎都围绕着想隐藏实现细节并有一个像样的 API。如果我们愿意到处传递 Node，我们可以做好一切。
见鬼，我们甚至可以做出多个并发的 IterMut，在运行时检查它们没有可变访问同一元素！
真的，这种设计更适合作为不会暴露给 API 消费者的内部数据结构。内部可变性很适合写安全的应用。不太适合安全的库。
总之，这就是我放弃 Iter 和 IterMut 了。我们可以做，但ugh。