Rust:从 std::Rc 智能指针向量实现迭代器

Question

我刚开始使用 Rust，但我已经面临数据所有权方面的问题。

我想实现一个名为 Port<T> 的通用结构具有值向量 Vec<T> .此外，这个结构有一个指向相同类型的其他结构的引用计数指针向量，Vec<Rc<Port<T>>> :

use std::slice::Iter;
use std::rc::Rc;

pub struct Port<T> {
    values: Vec<T>,
    ports: Vec<Rc<Port<T>>>,
}

思路如下:有多个类型为Port<T>的结构.您可以添加 T 类型的值到给定的端口。每个端口将这些值存储在其 values 中属性。但是，可以使用引用计数指针将一个端口“链接”到其他端口:

impl <T> Port<T> {
    pub fn new() -> Self {
        Self { values: vec![], ports: vec![] }
    }

    pub fn add_value(&mut self, value: T) {
        self.values.push(value);
    }

    pub fn chain_port(&mut self, port: Rc<Port<T>>) {
        if !port.is_empty() {
            self.ports.push(port)
        }
    }

    pub fn is_empty(&self) -> bool {
        self.values.is_empty() || self.ports.is_empty()
    }

    pub fn clear(&mut self) {
        self.values.clear();
        self.ports.clear();
    }
}

到目前为止，代码编译通过。现在，我想为一个端口实现一个迭代器，它返回对该端口拥有的值的引用，但也返回对每个链接端口的迭代器生成的值的引用:

pub struct PortIterator<'a, T> {
    values: Iter<'a, T>,                     // Iterates over values owned by Port<T>
    port: Option<Box<PortIterator<'a, T>>>,  // Pointer to current port iterator
    ports: Vec<Rc<Port<T>>>,                 // Pointers to remaining chained ports
}

// Note that the iterator is created from an immutable reference to Port<T>
impl<'a, T: 'a> IntoIterator for &'a Port<T> {
    type Item = &'a T;  // the iterator returns references to values
    type IntoIter = PortIterator<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        // We clone all the reference-counting pointers so the iterator owns them
        let mut ports = vec![];
        for port in self.ports.iter() {
            ports.push(port.clone())
        }
        PortIterator {values: self.values.iter(), port: None, ports}
    }
}

现在，让我们定义 Iterator PortIterator 的特征:

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

    fn next(&mut self) -> Option<Self::Item> {
        // We first iterate over values of the original port
        if let Some(v) = self.values.next() {
            return Some(v)
        }
        // If the first iterable is done, we try to iterate over a chained port
        if let Some(port) = &mut self.port {
            if let Some(v) = port.next() {
                return Some(v)
            }
        }
        // if the chained port is over, we try to consume the next chained port
        if let Some(port) = self.ports.get(self.next_port) {
            self.next_port += 1;
            self.port = Some(Box::new(port.as_ref().into_iter()));
            return self.next()
        }
        None
    }
}

现在，程序无法编译。问题似乎在第三个 if let block ，它与生命周期有关。这是编译器所说的:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/modeling/port.rs:69:40
   |
69 |         if let Some(port) = self.ports.get(self.next_port) {
   |                                        ^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 57:5...
  --> src/modeling/port.rs:57:5
   |
57 |     fn next(&mut self) -> Option<Self::Item> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/modeling/port.rs:69:29
   |
69 |         if let Some(port) = self.ports.get(self.next_port) {
   |                             ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 54:7...
  --> src/modeling/port.rs:54:7
   |
54 | impl <'a, T: 'a> Iterator for PortIterator<'a, T> {
   |       ^^
note: ...so that the expression is assignable
  --> src/modeling/port.rs:71:25
   |
71 |             self.port = Some(Box::new(port.as_ref().into_iter()));
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `Option<Box<PortIterator<'a, _>>>`
              found `Option<Box<PortIterator<'_, _>>>`

我不知道该如何处理。我一直在尝试其他选项和实现，但我一直在兜圈子。

Answer 1

我认为有更简单的方法可以实现您想要实现的目标。让我们从小事做起:你的 Port<T>需要一个iter(&self)返回迭代器的方法，该迭代器发出 &T项目:

pub fn iter(&self) -> impl Iterator<Item = &T> {
    // ...
}

此函数需要将迭代器链接到 self.values 上，即 self.values.iter()在链式端口上使用迭代器。你想写的是这样的:

pub fn iter(&self) -> impl Iterator<Item = &T> {
    self.values
        .iter()
        .chain(self.ports.iter().flat_map(|p| p.iter()))
}

但是，这不会编译，因为编译器提示“递归不透明类型”。那是因为 p.iter() 的类型和我们一样impl Iterator<...> ，然后必须包含自己。这在概念上与您在构建 PortIterator 时遇到的问题相同，您通过装箱链接 PortIterator 解决了这个问题.我们可以通过装箱内部迭代器并动态调度它来以相同的方式解决它:

pub fn iter(&self) -> impl Iterator<Item = &T> {
    self.values.iter().chain(
        self.ports
            .iter()
            .flat_map(|p| Box::new(p.iter()) as Box<dyn Iterator<Item = &T>>),
    )
}