Iteration

让我们仔细研究一下这个坏小子。

IntoIter

一如既往，IntoIter 将是最简单的，只需包装堆栈并调用 pop：

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<T> {
        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非常简单：

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

让我们来测试一下：

#[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);
}

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 ：

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()))
    }
}

> cargo build

到目前为止一切顺利。实现 next 可能有点麻烦，但是我认为它和旧栈 IterMut 的基本逻辑是一样的，只是添加了额外的 RefCell。

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)
        })
    }
}

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 不允许我们像这样拆分引用。 我们从 head.borrow() 中获得的 Ref 只允许与 node_ref 一样长，但是最终在 Ref::map 调用中将其破坏了。

巧合的是，就在我写这篇文章的那一刻，我们想要的功能实际上已经在两天前稳定了。 这意味着它将在几个月后才能稳定发布。 因此，让我们继续进行最新的每晚构建版本：

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,

我们来试试..。

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
    })
}

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::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。。。

凝视了很久

??????

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
    })
}

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 下的嵌套就越多。我们需要维持，比如，一堆 Refs 来代表我们持有的所有借用，因为如果我们停止寻找一个元素，我们需要减少前面每个 RefCell 的借用计数..。

我不认为我们能做什么。这是个死胡同。让我们试着离开 RefCell。

那我们的 Rcs 呢。谁说我们需要存储引用？为什么我们不能克隆整个 Rc，在列表中间添加一个好的拥有句柄呢？

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 都要求我们在进入下一个生命周期之前声明一些生命周期。 但是我们设法摆脱 Rc 的任何事情都是借用Iterator ...大脑...受伤了... aaaaaahhhhhh

也许我们可以... map... 的 Rc... 得到一个 Rc<T> ？有这种东西吗？文档似乎没有这样的东西。实际上有人做了一个 crate，可以让你这样做。

但是，等等，即使我们这样做，也遇到了一个更大的问题：迭代器失效的可怕幽灵。 以前，我们完全不受迭代器失效的影响，因为Iter借用了列表，使其完全不可变。 但是，如果我们的Iter产生了Rcs，那么他们根本不会借用该列表！ 这意味着人们可以在按住指针的同时开始调用push并弹出列表！

天啊，那有什么用? ！

好吧，push 实际上很好。 我们已经了解了列表的某些子范围，并且列表将超出我们的视线。 没关系。

然而，pop 则是另一回事。如果他们在我们的范围之外弹出元素，它仍然应该是好的。我们看不到那些节点，所以什么都不会发生。然而，如果他们试图弹出我们正在指向的节点... 一切都会爆炸！特别是当它们打开 try_unwrap 的结果时，它实际上会失败，整个程序将陷入恐慌。

这其实挺酷的。我们可以获得大量内部拥有的指针到列表中，并同时对它进行变异，它将一直工作，直到他们尝试删除我们正在指向的节点。即使这样，我们也不会得到悬空指针或其他任何东西，程序会确定地陷入恐慌！

但是必须在映射Rcs的基础上处理迭代器失效问题，似乎不好。Rc真的让我们失望了。有趣的是，我们经历了不可变堆栈情况的反转。当不可变堆栈很难收回数据的所有权，但每个地方都能得到引用时，我们的列表在获得所有权方面没有问题，但实际上很难借用我们的引用。

虽然公平地说，我们的大部分挣扎都围绕着想要隐藏实现细节和拥有一个体面的 API。如果我们只是到处传播节点，我们可以做好每件事。

见鬼，我们可以使多个并发 IterMuts 在运行时被检查为不可变访问同一个元素！

实际上，这种设计更适合于内部数据结构，因为这种结构从来不会向 API 的使用者公开。内部可变性对于编写安全的应用程序非常重要。没有那么多安全的库。

不管怎样，那就是我放弃了Iter和IterMut。我们可以使用他们，但是很丑。