# Iteration 让我们仔细研究一下这个坏小子。 ### IntoIter 一如既往，IntoIter 将是最简单的，只需包装堆栈并调用 pop： ```rust pub struct IntoIter(List); impl List { pub fn into_iter(self) -> IntoIter { IntoIter(self) } } impl Iterator for IntoIter { type Item = T; fn next(&mut self) -> Option { self.0.pop_front() } } ``` 但是我们有一个有趣的新发现。 以前，我们的列表只有一个“自然”的迭代顺序，而Deque本质上是双向的。 从头到尾有什么特别之处？ 如果有人想朝另一个方向迭代怎么办？ Rust实际上对此有一个答案：DoubleEndedIterator。 DoubleEndedIterator继承自Iterator（意味着所有DoubleEndedIterator均为Iterators），并且需要一个新方法：next\_back。 它具有与 next 完全相同的签名，但是应该从另一端产生元素。 DoubleEndedIterator的语义对我们来说非常方便：迭代器成为双端队列。 您可以从正面和背面消耗元素，直到两端收敛为止，此时迭代器为空。 就像 Iterator 和 next 一样，事实证明 next\_back 并不是DoubleEndedIterator 的消费者真正关心的东西。 而是，此接口的最好之处在于它公开了rev方法，该方法包装了迭代器以创建一个新的迭代器，该迭代器以相反的顺序生成元素。 这样做的语义很简单：在反向迭代器上对 next 的调用只是对 next\_back 的调用。 无论如何，因为我们已经很老套了，所以提供此API非常简单： ```rust impl DoubleEndedIterator for IntoIter { fn next_back(&mut self) -> Option { self.0.pop_back() } } ``` 让我们来测试一下： ```rust #[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); } ``` ```rust 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事情！ 由于引用，我们无法像以前那样存储＆Nodes。 相反，让我们尝试存储Ref ： ```rust pub struct Iter<'a, T>(Option>>); impl List { pub fn iter(&self) -> Iter { Iter(self.head.as_ref().map(|head| head.borrow())) } } ``` ```rust > cargo build ``` 到目前为止一切顺利。实现 next 可能有点麻烦，但是我认为它和旧栈 IterMut 的基本逻辑是一样的，只是添加了额外的 RefCell。 ```rust impl<'a, T> Iterator for Iter<'a, T> { type Item = Ref<'a, T>; fn next(&mut self) -> Option { self.0.take().map(|node_ref| { self.0 = node_ref.next.as_ref().map(|head| head.borrow()); Ref::map(node_ref, |node| &node.elem) }) } } ``` ```rust cargo build error[E0521]: borrowed data escapes outside of closure --> src/fourth.rs:155:13 | 153 | fn next(&mut self) -> Option { | --------- `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 { | --------- 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 不允许我们像这样拆分引用。 我们从 head.borrow() 中获得的 Ref 只允许与 node\_ref 一样长，但是最终在 Ref::map 调用中将其破坏了。 巧合的是，就在我写这篇文章的那一刻，我们想要的功能实际上已经在两天前稳定了。 这意味着它将在几个月后才能稳定发布。 因此，让我们继续进行最新的每晚构建版本： ```rust pub fn map_split(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where F: FnOnce(&T) -> (&U, &V), U: ?Sized, V: ?Sized, ``` 我们来试试..。 ```rust fn next(&mut self) -> Option { 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 }) } ``` ```rust cargo build Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists) error[E0521]: borrowed data escapes outside of closure --> src/fourth.rs:159:13 | 153 | fn next(&mut self) -> Option { | --------- `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 来映射我们的 Option。。。 凝视了很久 ?????? ```rust fn next(&mut self) -> Option { 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 }) } ``` ```rust 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>>` ``` 哦。对。有多个 refcell。我们在列表中走得越深，我们在每个 RefCell 下的嵌套就越多。我们需要维持，比如，一堆 Refs 来代表我们持有的所有借用，因为如果我们停止寻找一个元素，我们需要减少前面每个 RefCell 的借用计数..。 我不认为我们能做什么。这是个死胡同。让我们试着离开 RefCell。 那我们的 Rcs 呢。谁说我们需要存储引用？为什么我们不能克隆整个 Rc，在列表中间添加一个好的拥有句柄呢？ ```rust pub struct Iter(Option>>); impl List { pub fn iter(&self) -> Iter { Iter(self.head.as_ref().map(|head| head.clone())) } } impl Iterator for Iter { type Item = ``` 呃... 等等，我们现在要返回什么？`&T`? `Ref`? 不，这些都不起作用……我们的Iter不再拥有一生！ \&T 和 Ref 都要求我们在进入下一个生命周期之前声明一些生命周期。 但是我们设法摆脱 Rc 的任何事情都是借用Iterator ...大脑...受伤了... aaaaaahhhhhh 也许我们可以... map... 的 Rc... 得到一个 Rc\ ？有这种东西吗？文档似乎没有这样的东西。实际上有人做了一个 crate，可以让你这样做。 但是，等等，即使我们这样做，也遇到了一个更大的问题：迭代器失效的可怕幽灵。 以前，我们完全不受迭代器失效的影响，因为Iter借用了列表，使其完全不可变。 但是，如果我们的Iter产生了Rcs，那么他们根本不会借用该列表！ 这意味着人们可以在按住指针的同时开始调用push并弹出列表！ 天啊，那有什么用? ！ 好吧，push 实际上很好。 我们已经了解了列表的某些子范围，并且列表将超出我们的视线。 没关系。 然而，pop 则是另一回事。如果他们在我们的范围之外弹出元素，它仍然应该是好的。我们看不到那些节点，所以什么都不会发生。然而，如果他们试图弹出我们正在指向的节点... 一切都会爆炸！特别是当它们打开 try\_unwrap 的结果时，它实际上会失败，整个程序将陷入恐慌。 这其实挺酷的。我们可以获得大量内部拥有的指针到列表中，并同时对它进行变异，它将一直工作，直到他们尝试删除我们正在指向的节点。即使这样，我们也不会得到悬空指针或其他任何东西，程序会确定地陷入恐慌！ 但是必须在映射Rcs的基础上处理迭代器失效问题，似乎不好。Rc真的让我们失望了。有趣的是，我们经历了不可变堆栈情况的反转。当不可变堆栈很难收回数据的所有权，但每个地方都能得到引用时，我们的列表在获得所有权方面没有问题，但实际上很难借用我们的引用。 虽然公平地说，我们的大部分挣扎都围绕着想要隐藏实现细节和拥有一个体面的 API。如果我们只是到处传播节点，我们可以做好每件事。 见鬼，我们可以使多个并发 IterMuts 在运行时被检查为不可变访问同一个元素！ 实际上，这种设计更适合于内部数据结构，因为这种结构从来不会向 API 的使用者公开。内部可变性对于编写安全的应用程序非常重要。没有那么多安全的库。 不管怎样，那就是我放弃了Iter和IterMut。我们可以使用他们，但是很丑。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://chapin666.gitbook.io/too-many-list-zh/yi-ge-zao-gao-dan-an-quan-de-shuang-xiang-dui-lie/iteration.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.