如果迭代器有生命周期，如何在可变迭代器上实现下一个方法？

Question

我想在 Rust 中实现一个 table 类型，所以我有以下代码：

use std::ops::{Index, IndexMut};

#[derive(Clone)]
pub struct Table<T>
where
    T: Clone,
{
    row: usize,
    col: usize,
    data: Vec<Vec<T>>,
}

impl<T> Table<T>
where
    T: Clone,
{
    pub fn new(row: usize, col: usize) -> Self {
        let mut t = Table {
            row,
            col,
            data: Vec::<Vec<T>>::with_capacity(row),
        };
        t.data.resize(row, Vec::<T>::with_capacity(col));
        t
    }

    pub fn size(&self) -> (usize, usize) {
        (self.row(), self.col())
    }

    pub fn col(&self) -> usize {
        self.col
    }

    pub fn row(&self) -> usize {
        self.row
    }

    pub fn cell_iter(&self) -> TableCellIter<T> {
        TableCellIter {
            table: self,
            row: 0,
            col: 0,
        }
    }

    pub fn cell_iter_mut(&mut self) -> TableCellIterMut<'_, T> {
        TableCellIterMut {
            table: self,
            row:0,
            col:0,
        }
    }
}

impl<T> Index<(usize, usize)> for Table<T>
where
    T: Clone,
{
    type Output = T;
    fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
        if row >= self.row() {
            panic!("out of range")
        }
        &self.data[row][col]
    }
}

impl<T> IndexMut<(usize, usize)> for Table<T>
where
    T: Clone,
{
    fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut Self::Output {
        while self.data.len() <= row {
            self.data.push(Vec::<T>::with_capacity(self.col()));
        }
        &mut self.data[row][col]
    }
}

pub struct TableCellIter<'a, T>
where
    T: Clone,
{
    table: &'a Table<T>,
    row: usize,
    col: usize,
}

impl<'a, T> Iterator for TableCellIter<'a, T>
where
    T: Clone,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.col == self.table.col() {
            self.row += 1;
            self.col = 0;
        }
        if self.row >= self.table.row() {
            return None;
        }
        let ref cell = self.table[(self.row, self.col)];
        self.col += 1;
        Some(cell)
    }
}

pub struct TableCellIterMut<'a, T>
where
    T: Clone,
{
    table: &'a mut Table<T>,
    row: usize,
    col: usize,
}

impl<'a, T> Iterator for TableCellIterMut<'a, T>
where
    T: Clone,
{
    type Item = &'a mut T;

    fn next<'b: 'a>(&'b mut self) -> Option<Self::Item>
    {
        if self.col == self.table.col() {
            self.row += 1;
 self.col = 0;
        }
        if self.row >= self.table.row() {
            return None;
        }
        let ref mut cell = self.table[(self.row, self.col)];
        self.col += 1;
        Some(cell)
    }
}

在 TableCellIter 类型工作正常的地方，TableCellIterMut 不能。编译器警告我：

error[E0195]: lifetime parameters or bounds on method `next` do not match the trait declaration
   --> src/lib.rs:125:12
    |
125 |     fn next<'b: 'a>(&'b mut self) -> Option<Self::Item>
    |            ^^^^^^^^ lifetimes do not match method in trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0195`.
error: could not compile `sample`

但是如果我删除 TableCellIterMut 的下一个生命周期范围：

    fn next(&mut self) -> Option<Self::Item>

似乎无法推断下一个生命周期参数：

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
   --> src/lib.rs:135:28
    |
135 |         let ref mut cell = self.table[(self.row, self.col)];
    |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 126:13...
   --> src/lib.rs:126:13
    |
126 |     fn next(&mut self) -> Option<Self::Item>
    |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
   --> src/lib.rs:135:28
    |
135 |         let ref mut cell = self.table[(self.row, self.col)];
    |                            ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 119:6...
   --> src/lib.rs:119:6
    |
119 | impl<'a, T> Iterator for TableCellIterMut<'a, T>
    |      ^^
note: ...so that the types are compatible
   --> src/lib.rs:127:5
    |
127 | /     {
128 | |         if self.col == self.table.col() {
129 | |             self.row += 1;
130 | |  self.col = 0;
...   |
137 | |         Some(cell)
138 | |     }
    | |_____^
    = note: expected `Iterator`
               found `Iterator`

error: aborting due to previous error

我的问题是，为什么 TableCellIter 中的 next 是正确的，而 TableCellIterMut 中的是错误的？

下一步如何正确执行？

Answer 1

由迭代器编辑的项目引用 return 可以具有重叠的生命周期，因为正如您所注意到的，它们的生命周期不能与 self 参数的生命周期绑定到 next().如果 next() 方法对同一个可变引用 return 两次，你最终会得到对同一个对象的多个可变引用，这是不允许的。这意味着您的代码只有在所有 return 引用都是不相交的情况下才是安全的，如果正确实现了迭代器就是这种情况。然而，这种保证只能通过对代码的语义进行推理来得出，而不能仅仅通过查看所涉及的函数调用的原型来得出。这是borrow checker做不到的（事实上，在一般情况下可以证明这是不可能的），所以编译器拒绝了代码。

对于不可变引用，这不是问题，因为允许对同一对象有多个不可变引用。

有几种方法可以解决这个问题。我的建议是将数据表示从 Vec<Vec<T>> 更改为平面 Vec<T>，并相应地实施索引操作。这将使您的代码整体上更简单，同时效率更高。然后可以通过推迟到 Vec<>.

上的现有迭代器来实现迭代器

如果您想保留 Vec<Vec<T>> 结构，您仍然可以使用 Vec 上的现有迭代器：

pub fn cell_iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
    self.data.iter_mut().flat_map(|row| row.iter_mut())
}

请注意，您甚至不需要显式定义自定义迭代器类型。 iter() 方法可以实现类似的实现。

如果你想从头开始创建一个完全自定义的容器类型，你通常需要对可变迭代器使用不安全的代码，但在这种情况下，依赖 Vec 的迭代器实现要好得多（内部使用不安全代码）。

如果迭代器有生命周期，如何在可变迭代器上实现下一个方法？

How to implement the next method on mutable Iterator if the Iterator has a lifetime?

lifetime

rust