如何创建自己的数据结构，并使用迭代器返回可变引用？

Question

我在 Rust 中创建了一个数据结构，并希望为其创建迭代器。创建不可变迭代器很容易。目前我有以下代码，它可以正常工作：

// This is a mock of the "real" EdgeIndexes class as
// the one in my real program is somewhat complex, but
// of identical type

struct EdgeIndexes;

impl Iterator for EdgeIndexes {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        Some(0)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, None)
    }
}

pub struct CGraph<E> {
    nodes: usize,
    edges: Vec<E>,
}

pub struct Edges<'a, E: 'a> {
    index: EdgeIndexes,
    graph: &'a CGraph<E>,
}

impl<'a, E> Iterator for Edges<'a, E> {
    type Item = &'a E;

    fn next(&mut self) -> Option<Self::Item> {
        match self.index.next() {
            None => None,
            Some(x) => Some(&self.graph.edges[x]),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.index.size_hint()
    }
}

我想创建一个迭代器，它能够返回可变引用。我已经尝试过了，但无法找到让它编译通过的方法：

pub struct MutEdges<'a, E: 'a> {
    index: EdgeIndexes,
    graph: &'a mut CGraph<E>,
}

impl<'a, E> Iterator for MutEdges<'a, E> {
    type Item = &'a mut E;

    fn next(&mut self) -> Option<&'a mut E> {
        match self.index.next() {
            None => None,
            Some(x) => self.graph.edges.get_mut(x),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.index.size_hint()
    }
}

编译此代码会导致以下错误：

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/lib.rs:54:24
   |
54 |             Some(x) => self.graph.edges.get_mut(x),
   |                        ^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 51:5...
  --> src/lib.rs:51:5
   |
51 | /     fn next(&mut self) -> Option<&'a mut E> {
52 | |         match self.index.next() {
53 | |             None => None,
54 | |             Some(x) => self.graph.edges.get_mut(x),
55 | |         }
56 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:54:24
   |
54 |             Some(x) => self.graph.edges.get_mut(x),
   |                        ^^^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 48:6...
  --> src/lib.rs:48:6
   |
48 | impl<'a, E> Iterator for MutEdges<'a, E> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut E>
              found std::option::Option<&mut E>

我不确定如何解释这些错误以及如何更改我的代码，以便允许MutEdges返回可变引用。

链接到代码示例。

- Mike Pedersen

---

我不确定，但可能是与https://dev59.com/eF8e5IYBdhLWcg3wfaUy相同的问题。 - Levans

不完全是，我认为。我的迭代器没有拥有它返回可变引用的对象，而那个代码片段却有。我认为这是可能的，因为 Rust 标准库已经有了可变引用的迭代器。 (http://doc.rust-lang.org/std/slice/struct.MutItems.html) - Mike Pedersen

他们的实现使用了已弃用的函数mut_shift_ref()，也许你可以在这里找到你需要的内容：http://doc.rust-lang.org/std/slice/trait.MutableSlice.html#tymethod.mut_shift_ref - Levans

@Levans：他们的实现没有使用mut_shift_ref。只需单击文档中的[src]按钮即可查看MutItems的源代码。 - sellibitze

@sellibitze 对不起，我的错，我没有读好的源文件。 - Levans

Answer 1

你无法编译这段代码，因为可变引用比不可变引用更加限制。下面是说明该问题的缩短版本：

struct MutIntRef<'a> {
    r: &'a mut i32
}

impl<'a> MutIntRef<'a> {
    fn mut_get(&mut self) -> &'a mut i32 {
        &mut *self.r
    }
}

fn main() {
    let mut i = 42;
    let mut mir = MutIntRef { r: &mut i };
    let p = mir.mut_get();
    let q = mir.mut_get();
    println!("{}, {}", p, q);
}

会产生相同错误：

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^
  |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 6:5...
 --> src/main.rs:6:5
  |
6 | /     fn mut_get(&mut self) -> &'a mut i32 {
7 | |         &mut *self.r
8 | |     }
  | |_____^
note: ...so that reference does not outlive borrowed content
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 5:6...
 --> src/main.rs:5:6
  |
5 | impl<'a> MutIntRef<'a> {
  |      ^^
note: ...so that reference does not outlive borrowed content
 --> src/main.rs:7:9
  |
7 |         &mut *self.r
  |         ^^^^^^^^^^^^

如果我们看一下主函数，我们会得到两个可变引用p和q，它们都别名指向i的内存位置。这是不被允许的。在Rust中，我们不能有两个可变引用别名并且都可用。这种限制的动机是观察到变异和别名与内存安全方面不相容。因此，编译器拒绝了这段代码是好事。如果编译出了这样的代码，就很容易出现各种内存损坏错误。

Rust避免这种危险的方法是保持最多一个可变引用的可用性。因此，如果您想基于对Y的可变引用创建对X的可变引用，其中X由Y拥有，我们最好确保只要对X的引用存在，我们就不能再触摸对Y的其他引用。在Rust中，这通过生命周期和借用实现。编译器在这种情况下认为原始引用被借用，并且这对生成的引用的生命周期参数也有影响。如果我们更改

fn mut_get(&mut self) -> &'a mut i32 {
    &mut *self.r
}

fn mut_get(&mut self) -> &mut i32 { // <-- no 'a anymore
    &mut *self.r // Ok!
}

编译器不再抱怨这个get_mut函数。现在它返回一个引用，其生命周期参数与&self匹配，而不是'a。这使得mut_get成为一个您可以“借用”self的函数。这就是编译器抱怨不同位置的原因：

error[E0499]: cannot borrow `mir` as mutable more than once at a time
  --> src/main.rs:15:13
   |
14 |     let p = mir.mut_get();
   |             --- first mutable borrow occurs here
15 |     let q = mir.mut_get();
   |             ^^^ second mutable borrow occurs here
16 |     println!("{}, {}", p, q);
   |                        - first borrow later used here

显然，编译器确实认为mir是被借用的。这很好。这意味着现在只有一种方法可以访问i的内存位置：p。

现在你可能会想：标准库作者是如何编写可变向量迭代器的？答案很简单：他们使用了不安全的代码。没有其他办法。Rust编译器根本不知道每当您请求一个可变向量迭代器的下一个元素时，您获得的是每次都不同的引用，而不是两次相同的引用。当然，我们知道这样的迭代器不会给您相同的引用两次，这使得我们可以安全地提供您所使用的这种接口。我们不需要“冻结”这样的迭代器。如果迭代器返回的引用没有重叠，访问元素时不需要借用迭代器是安全的。在内部，这是使用不安全的代码完成的（将原始指针转换为引用）。

解决问题的简单方法可能是依赖于MutItems。这已经是库提供的可变迭代器，可以用于遍历向量。因此，您可以仅使用它而不是自己的自定义类型，或者您可以在自定义迭代器类型内部包装它。如果由于某种原因无法这样做，则必须编写自己的不安全代码。如果您这样做，请确保

• 您不会创建多个别名的可变引用。如果这样做，将违反Rust规则并调用未定义行为。
• 您不要忘记使用PhantomData类型来告诉编译器您的迭代器是类似引用的类型，其中不能用更长的生命周期替换该类型，否则可能会创建一个悬空的迭代器。

- sellibitze