如何使用返回可变引用的迭代器创建自己的数据结构? [英] How can I create my own data structure with an iterator that returns mutable references?

问题描述

我已经在Rust中创建了一个数据结构，我想为其创建迭代器.不变的迭代器很容易.我目前有这个，并且工作正常:

I have created a data structure in Rust and I want to create iterators for it. Immutable iterators are easy enough. I currently have this, and it works fine:

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

我想创建一个迭代器，该迭代器也返回可变引用.我已经尝试过这样做，但是找不到一种方法来编译它:

I want to create a iterator that returns mutable references as well. I've tried doing this, but can't find a way to get it to compile:

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

编译此错误会导致以下错误:

Compiling this results in the following error:

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返回可变引用.

I'm unsure how to interpret these errors and how to change my code in order to allow MutEdges to return mutable references.

链接到带有代码的游乐场.

推荐答案

您无法编译此代码，因为可变引用比不可变引用更具限制性.简短的版本说明了这个问题，这是这样的:

You can't compile this because mutable references are more restrictive than immutable references. A shortened version that illustrates the issue is this:

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

哪个会产生相同的错误:

Which produces the same error:

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
  |         ^^^^^^^^^^^^

如果看一下main函数，我们会得到两个分别称为p和q的可变引用，它们都是i的存储位置的别名.这是不允许的.在Rust中，我们不能有两个互为别名且都可用的可变引用.这种限制的动机是观察到突变和混叠在内存安全方面不能很好地发挥作用.因此，编译器拒绝代码是一件好事.如果编译了这样的内容，则很容易出现各种内存损坏错误.

If we take a look at the main function, we get two mutable references called p and q that both alias the memory location of i. This is not allowed. In Rust, we can't have two mutable references that alias and are both usable. The motivation for this restriction is the observation that mutation and aliasing don't play well together with respect to memory safety. So, it's good that the compiler rejected the code. If something like this compiled, it would be easy to get all kinds of memory corruption errors.

Rust避免这种危险的方法是通过保持最多一个可变引用可用.因此，如果要基于对Y的可变引用(其中X归Y拥有)创建对X的可变引用，则最好确保只要存在对X的引用，就不能再碰到另一个对Y的引用.在Rust中，这是通过生命周期和借用来实现的.在这种情况下，编译器认为原始参考是借用的，这也会影响所得参考的生命周期参数.如果我们改变

The way Rust avoids this kind of danger is by keeping at most one mutable reference usable. So, if you want to create mutable reference to X based on a mutable reference to Y where X is owned by Y, we better make sure that as long as the reference to X exists, we can't touch the other reference to Y anymore. In Rust this is achieved through lifetimes and borrowing. The compiler considers the original reference to be borrowed in such a case and this has an effect on the lifetime parameter of the resulting reference as well. If we change

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的功能.这就是为什么编译器抱怨位置不同的原因:

the compiler stops complaining about this get_mut function. It now returns a reference with a lifetime parameter that matches &self and not 'a anymore. This makes mut_get a function with which you "borrow" self. And that's why the compiler complains about a different location:

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

显然，编译器确实 did 认为mir是借来的.很好这意味着现在只有一种方法可以到达i的存储位置:p.

Apparently, the compiler really did consider mir to be borrowed. This is good. This means that now there is only one way of reaching the memory location of i: p.

现在您可能想知道:标准库作者如何设法编写可变向量迭代器?答案很简单:他们使用了不安全的代码.没有别的办法了. Rust编译器根本不知道，每当您问一个可变向量迭代器作为下一个元素时，您每次都会获得一个不同的引用，而永远不会两次获得相同的引用.当然，我们知道，这样的迭代器不会两次为您提供相同的引用，因此可以安全地提供您惯用的这种接口.我们不需要冻结"这样的迭代器.如果迭代器返回的引用不重叠，则不必不必借用迭代器来访问元素是安全的.在内部，这是使用不安全的代码(将原始指针转换为引用)完成的.

Now you may wonder: How did the standard library authors manage to write the mutable vector iterator? The answer is simple: They used unsafe code. There is no other way. The Rust compiler simply does not know that whenever you ask a mutable vector iterator for the next element, that you get a different reference every time and never the same reference twice. Of course, we know that such an iterator won't give you the same reference twice and that makes it safe to offer this kind of interface you are used to. We don't need to "freeze" such an iterator. If the references an iterator returns don't overlap, it's safe to not have to borrow the iterator for accessing an element. Internally, this is done using unsafe code (turning raw pointers into references).

针对您的问题的简单解决方案可能是依靠MutItems.这已经是库在向量上提供的可变迭代器.因此，您可能只使用它而不是自己的自定义类型就可以摆脱困境，或者可以将其包装在自定义迭代器类型中.如果由于某种原因而不能这样做，则必须编写自己的不安全代码.如果这样做，请确保

The easy solution for your problem might be to rely on MutItems. This is already a library-provided mutable iterator over a vector. So, you might get away with just using that instead of your own custom type, or you could wrap it inside your custom iterator type. In case you can't do that for some reason, you would have to write your own unsafe code. And if you do so, make sure that

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

• You don't create multiple mutable references that alias. If you did, this would violate the Rust rules and invoke undefined behavior.
• You don't forget to use the PhantomData type to tell the compiler that your iterator is a reference-like type where replacing the lifetime with a longer one is not allowed and could otherwise create a dangling iterator.

这篇关于如何使用返回可变引用的迭代器创建自己的数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！