可变迭代器用于 Vec<Vec<(K, V)>>

Question

可变迭代器用于 Vec<Vec<(K, V)>>

3

我将尝试创建一个可变的迭代器，用于类型为：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)> {
   |     ^

显然我有终身难题，但我不知道如何告诉编译器这应该可以工作。

这样实现可变迭代器是否正确，还是有更好的方法？

- Jesper Axelsson

2个回答

3

您没有提供重新实现标准Iterator::flat_map的理由，因此我建议直接使用这个方法并结合另一个map来消除您不需要的可变性：

fn main() {
    let mut a: Vec<Vec<(u8, u8)>> = Default::default();
    let c = a.iter_mut()
        .flat_map(|x| x.iter_mut())
        .map(|&mut (ref a, ref mut b)| (a, b))
        .count();
    println!("{}", c);
}

一旦你拥有了这个，你可以通过多种方法之一返回迭代器。

#[derive(Debug, Default)]
struct Thing<K, V>(Vec<Vec<(K, V)>>);

impl<K, V> Thing<K, V> {
    fn iter_mut<'a>(&'a mut self) -> Box<Iterator<Item = (&'a K, &'a mut V)> + 'a> {
        Box::new(self.0
            .iter_mut()
            .flat_map(|x| x.iter_mut())
            .map(|&mut (ref a, ref mut b)| (a, b)))
    }
}

fn main() {
    let mut a = Thing::<u8, u8>::default();
    let c = a.iter_mut().count();
    println!("{}", c);
}

- Shepmaster

谢谢！我一直在想如何传递一个迭代器，这将在未来非常有用。 - Jesper Axelsson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthieu M. · Accepted Answer

当调试晦涩的错误信息时，我发现尽可能地隔离问题会更容易。第一步是将表达式分解为其基本组成部分，让我们从拆分索引步骤开始：

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

即使您没有，也不能保证您没有一个“倒带”方法可以让您“后退”。 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)。