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

Question

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

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 中的 next 是错误的？

我怎样才能正确实施下一步？

Answer 1

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

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

有多种方法可以解决这个问题。我的建议是将数据表示形式从 flat 更改Vec<Vec<T>>为 flat 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（内部使用不安全代码）。