# Iter

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

好吧，让我们试试这个：

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

```rust
> 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 查看：

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

```rust
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}
```

```rust
> 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
```

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

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

```rust
> 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会自动为您选择生命周期。 这就是生命周期省略。

特别是：

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

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

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

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

```rust
// 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
        })
    }
}
```

好了，我想这次我们成功了。

```rust
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 的引用：

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


```

```rust
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 中，这意味着它将被丢弃，引用将悬空：

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


```

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

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

```rust
cargo build
```

🎉 🎉 🎉

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

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

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

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

看，map 是一个泛型：

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

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

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

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

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

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

```rust
> 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


```

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

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

相当于：

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

耶，更少的生命周期！

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

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


---

# 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-hai-hang-de-dan-lian-zhan/iter.md?ask=<question>
```

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.