Iter

好的，让我们试着实现 Iter。这一次，我们不能依靠 List 来提供所有我们想要的功能。我们得自己动手了。我们需要的基本逻辑是保持一个指针，指向下一个要生成的当前节点。因为该节点可能不存在(列表为空或者我们已经进行了迭代) ，所以我们希望该引用是 Option。当我们生成一个元素时，我们要前进到当前节点的下一个节点。

好吧，让我们试试这个：

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

天啊。 生命周期。 我听说过这些东西。 我听说他们是一场噩梦。

让我们尝试一些新的东西: 看到那个错误[ E0106]的东西吗？这是一个编译器错误代码。我们可以要求 rustc 解释这些。使用 --explain 查看：

> 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 加到我们的结构中？我们来试试。

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

我开始看到一种模式。。。让我们把这些小家伙加入到我们能做的事情中：

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 打败了。

也许我们应该真正弄清楚 'a 生命周期到底意味着什么。

生命周期可能会吓跑很多人，因为它们改变了我们从编程开始就知道和喜爱的东西。到目前为止，我们实际上已经成功地避开了生命周期，尽管它们一直在我们的程序中纠缠不清。

在有垃圾收集器的语言中，生命周期是不必要的，因为垃圾收集器可确保一切按需魔术般地存在。 Rust中的大多数数据都是手动管理的，因此数据需要另一种解决方案。C 和 C++为我们提供了一个清晰的示例，如果让人们随意使用指向堆栈上的指针会发生什么：无处不在的无法管理的不安全性。这可以大致分为两类错误：

• 拿着指向超出范围的东西的指针

• 拿着一个指针指向某个修改了的东西

生命周期可以99%解决这两个问题，它们都是以完全透明的方式来解决的。

那么什么是生命周期呢？

简而言之，生命周期是程序中某处代码的区域（〜块/作用域）的名称而已。 当引用标记有生命周期时，我们说它在整个区域都有效。 不同的地方必须引用且需要有效时间。整个生命周期系统反过来就是一个约束求解系统，它试图最小化每个引用的区域。 如果成功找到了满足所有约束条件的一组寿命，则程序将编译！ 否则，您将返回一条错误消息，提示某些对象寿命不足。

在一个函数体中，你通常不能谈论生命周期，也不想谈论生命周期。编译器拥有完整的信息，可以推断出所有的约束以找到最小的生命周期。然而，在类型和 api 级别上，编译器并不拥有所有的信息，它要求你告诉它不同生命之间的关系，这样它就能知道你在做什么。

原则上，这些生命周期也可以省略，但检查所有的借用将是一个庞大的整个程序分析，将产生令人难以置信的非本地错误。所有借用检查都可以在每个函数体中独立完成，并且所有错误都应该是局部的（或者您的类型具有不正确的签名）。

但我们之前已经在函数签名中编写了引用，这很好！ 这是因为在某些情况下很常见，Rust会自动为您选择生命周期。 这就是生命周期省略。

特别是：

//输入中只有一个引用，因此必须从该输入导出输出
fn foo(&A) -> &B; // sugar for:
fn foo<'a>(&'a A) -> &'a B;

// 许多输入，假设它们都是独立的
fn foo(&A, &B, &C); // sugar for:
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);

// Methods, 假设所有的输出寿命都来自`self`
fn foo(&self, &B, &C) -> &D; // sugar for:
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;

那么 fn foo<'a>(&'a A) -> &'a B 是什么意思？实际上，这意味着输入必须至少与输出生命周期一样长。因此，如果您将输出保留很长时间，这将扩大输入必须对其有效的区域。一旦停止使用输出，编译器就会知道输入也会变得无效。

通过这个系统的建立，Rust 可以确保在释放之后没有任何东西被使用，并且存在未完成的引用时没有任何东西被修改。它只是确保所有的约束都能解决！

好吧，那么，Iter。

让我们回到无生命周期状态：

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

我们只需要在函数和类型签名中添加生存期：

// Iter is generic over *some* lifetime, it doesn't care
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

// No lifetime here, List doesn't have any associated lifetimes
impl<T> List<T> {
    // We declare a fresh lifetime here for the *exact* borrow that
    // creates the iter. Now &self needs to be valid as long as the
    // Iter is around.
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

// We *do* have a lifetime here, because Iter has one that we need to define
impl<'a, T> Iterator for Iter<'a, T> {
    // Need it here too, this is a type declaration
    type Item = &'a T;

    // None of this needs to change, handled by the above.
    // Self continues to be incredibly hype and amazing
    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。好的，这很简单，我们只需要在引用之前取消对 Box 的引用：

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，所以我们将 box 移到了 map 中，这意味着它将被丢弃，引用将悬空：

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 我们需要移除间接层：

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

🎉 🎉 🎉

你可能会想: “哇，&** 这东西真难看” ，没错。通常 Rust 非常擅长隐式地进行这种转换，通过一个叫做 deref 强制的进程，它基本上可以在整个代码中插入 *'s 来进行类型检查。之所以可以这样做，是因为我们有借用检查器来确保我们永远不会弄乱指针！

但是在这个例子中，我们有一个 Option<&T> 而不是 &T，这个闭包有点太复杂了，所以我们需要为它做这个。值得庆幸的是，在我的经验中，这是相当罕见的。

为了完整起见，我们可以使用涡轮鱼语法给出一个不同的提示：

    self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);

看，map 是一个泛型：

pub fn map<U, F>(self, f: F) -> Option<U>

涡轮鱼：::<>，让我们告诉编译器我们认为这些泛型的类型。::<&Node, _> 表示“它应该返回一个 &Node 类型，我不知道/也不在乎其他类型。

反过来让编译器知道 &node 应该应用了deref，所以我们不需要手动应用所有这些*！。

在这种情况下，我不认为这是一个真正的改进，这只是一个几乎不加掩饰来炫耀 deref 和 涡轮鱼 语法的借口。

让我们编写一个测试，以确保我们没有使用它或其他任何东西：

#[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

最后，应该注意的是，我们实际上可以在这里省略生命周期：

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

相当于：

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

耶，更少的生命周期！

或者，如果您不喜欢“隐藏”某个结构包含生命周期，可以使用 Rust 2018 显式省略生命周期语法： ’ _ ：

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}