iterator - Vec >的可变迭代器

Question

我正在尝试为类型为Vec<Vec<(K, V)>>的向量创建可变的迭代器

迭代器代码:

pub struct IterMut<'a, K: 'a, V: 'a> {
    iter: &'a mut Vec<Vec<(K, V)>>,
    ix: usize,
    inner_ix: usize,
}

impl<'a, K, V> Iterator for IterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);

    #[inline]
    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {

        while self.iter.len() < self.ix {
            while self.iter[self.ix].len() < self.inner_ix {
                self.inner_ix += 1;
                let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix];
                return Some((&k, &mut v));
            }

            self.ix += 1;
        }

        return None;
    }
}

我得到的错误是:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:16:42
   |
16 |                 let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix];
   |                                          ^^^^^^^^^^^^^^^^^^
   |
help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<(&'a K, &'a mut V)>
  --> src/main.rs:11:5
   |
11 |     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
   |     ^

显然我遇到了生存期问题，但是我不知道如何告诉编译器这应该工作。

这是应该如何实现可变迭代器，还是有更好的方法？

Answer 1

当调试隐秘错误消息时，我发现尝试并尽可能地隔离问题更加容易。

第一步是将表达式分解为其基本组成部分，让我们从拆分索引步骤开始:

fn next(&mut self) -> Option<(&'a K, &'a mut V)> {

    while self.iter.len() < self.ix {
        while self.iter[self.ix].len() < self.inner_ix {
            self.inner_ix += 1;
            let outer: &'a mut Vec<_> = self.iter;
            let inner: &'a mut Vec<_> = &mut outer[self.ix];
            let (ref k, ref mut v) = inner[self.inner_ix];
            return Some((&k, &mut v));
        }

        self.ix += 1;
    }

    return None;
}

Index特性假定其输出的生存期与接收者的生存期相关联，因此要获得 'a生存期，我们需要接收器具有 &'a生存期，并且它向上传播，从而产生上述代码。

但是，这里存在一个问题:因为可变引用不是 let outer: &'a mut Vec<_> = self.iter;，所以 Copy无法编译。

那么，如何从可变引用中获取可变引用(这是必须的，因为 IndexMut获得了可变引用)？

一种使用重新借阅: let outer: &'a mut Vec<_> = &mut *self.iter;。

而且，哦:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> <anon>:16:45
   |
16 |                 let outer: &'a mut Vec<_> = &mut *self.iter;
   |                                             ^^^^^^^^^^^^^^^
   |

重新借用的引用对 'a无效，仅对 self的(未命名)生命周期有效!

为什么会使用rust ？为什么？

因为否则将是不安全的。

保证 &mut T不会混叠，但是您的方法可以创建混叠引用(如果您忘记了推进索引的话):

#[inline]
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
    let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix];
    return Some((&k, &mut v));
}

即使您不这样做，也无法保证您没有允许“后退”的 rewind方法。

TL; DR:您将要踩到一枚地雷，而是被转向了Stack Overflow；)

好的，但是如何实现迭代器!

好吧，当然，使用迭代器。正如Shepmaster(简短地)回答的那样，已经以 FlatMap 为幌子在标准库中有一个等效项。诀窍是使用现有的迭代器来获取详细信息!

就像是:

use std::slice::IterMut;

pub struct MyIterMut<'a, K: 'a, V: 'a> {
    outer: IterMut<'a, Vec<(K, V)>>,
    inner: IterMut<'a, (K, V)>,
}

然后，您可以从 inner中消费(只要它提供了商品)，而当空时，您可以从 outer中重新填充它。

impl<'a, K, V> MyIterMut<'a, K, V> {
    fn new(v: &'a mut Vec<Vec<(K, V)>>) -> MyIterMut<'a, K, V> {
        let mut outer = v.iter_mut();
        let inner = outer.next()
                         .map(|v| v.iter_mut())
                         .unwrap_or_else(|| (&mut []).iter_mut());
        MyIterMut { outer: outer, inner: inner }
    }
}

impl<'a, K, V> Iterator for MyIterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);

    #[inline]
    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
        loop {
            match self.inner.next() {
                Some(r) => return Some((&r.0, &mut r.1)),
                None => (),
            }

            match self.outer.next() {
                Some(v) => self.inner = v.iter_mut(),
                None => return None,
            }
        }
    }
}

快速测试案例:

fn main() {
    let mut v = vec![
        vec![(1, "1"), (2, "2")],
        vec![],
        vec![(3, "3")]
    ];
    let iter = MyIterMut::new(&mut v);
    let c: Vec<_> = iter.collect();
    println!("{:?}", c);
}

打印:

[(1, "1"), (2, "2"), (3, "3")]

不出所料，所以它并没有完全损坏，但是我希望我不必依靠 &[]是 'static技巧(即 std::slice::IterMut实现 Default)。