如何为 Rc<RefCell<T>> 链实现迭代器？

Question

在 Rust 中实现跳过列表时，我在尝试为 Rc<RefCell<T>> 链实现 Iterator 时卡住了。

pub struct SkipList<K, V> {
    head: Rc<RefCell<SkipNode<K, V>>>,
    rng: rand::rngs::ThreadRng,
    len: usize,
}

impl<K: Ord, V> SkipList<K, V> {
    pub fn iter(&self) -> Iter<K, V> {
        let next = &RefCell::borrow(&self.head).next_by_height[0];
        Iter {
            ptr: next.as_ref().map(|ref cell|Rc::clone(cell)),
            _marker: Default::default(),
        }
    }
}

struct SkipNode<K, V> {
    entry: Entry<K, V>,
    next_by_height: [Option<Rc<RefCell<SkipNode>>>; MAX_HEIGHT],
}

pub struct Entry<K, V> {
    key: K,
    value: V,
}

struct SkipNode<K, V> {
    entry: Option<Entry<K, V>>,
    next_by_height: SkipTrack<K, V>,
}

pub struct Iter<'a, K: Ord, V> {
    ptr: Option<Rc<RefCell<SkipNode<K, V>>>>,
    _marker: marker::PhantomData<&'a K>,
}

impl<'a, K, V: 'a> Iterator for Iter<'a, K, V>
where K: Ord
{
    type Item = Ref<'a, Entry<K, V>>;

    fn next(&mut self) -> Option<Self::Item> {
        self.ptr.take().map(|node| {
            let current = RefCell::borrow(&node);
            self.ptr = current.next_by_height[0].as_ref().map(|ref node| Rc::clone(node));
            Ref::map(current, |ref wrapped| {
                &wrapped.entry.unwrap()
            })
        })
    }
}

错误是：

   Compiling RclessRefCelllessTgreatergreater-Rust v0.1.0 (/home/runner/RclessRefCelllessTgreatergreater-Rust)
error[E0515]: cannot return reference to temporary value
   --> main.rs:138:15
    |
138 |               &wrapped.entry.unwrap()
    |               ^----------------------
    |               ||
    |               |temporary value created here
    |               returns a reference to data owned by the current function

error[E0507]: cannot move out of `wrapped.entry` which is behind a shared reference
   --> main.rs:138:16
    |
138 |               &wrapped.entry.unwrap()
    |                ^^^^^^^^^^^^^
    |                |
    |                move occurs because `wrapped.entry` has type `std::option::Option<Entry<K, V>>`, which does not implement the `Copy` trait
    |                help: consider borrowing the `Option`'s content: `wrapped.entry.as_ref()`

error[E0515]: cannot return value referencing function parameter `node`
   --> main.rs:137:13
    |
135 |               let current = RefCell::borrow(&node);
    |                                             ----- `node` is borrowed here
136 |               self.ptr = current.next_by_height[0].as_ref().map(|ref node| Rc::clone(node));
137 | /             Ref::map(current, |ref wrapped| {
138 | |                 &wrapped.entry.unwrap()
139 | |             })
    | |______________^ returns a value referencing data owned by the current function

error: aborting due to 3 previous errors

Some errors have detailed explanations: E0507, E0515.
For more information about an error, try `rustc --explain E0507`.
error: could not compile `RclessRefCelllessTgreatergreater-Rust`.

完整代码可在 Repl.it 获得。

我试图将 Ref<T> 当作由 Iterator 编辑的 Item return，但编译器抱怨说 next 不能 return 一个临时变量。有没有一种优雅的方法可以为 Rc<RefCell> 实现 Iterator？

Answer 1

Is there an elegant way to implement Iterator for Rc<RefCell>?

不是特别喜欢。你有两件大事。

构建 Iterator 时的一个限制是输出类型不能引用迭代器本身。它可以是 return 拥有的值（不涉及生命周期）或 return 绑定到其他对象生命周期的引用。

我看到您曾尝试通过使用 PhantomData<&'a K> 和使用'a 在你的 Iterator::Item 中。但是，由于您的迭代器只能从 ptr 获取值，这是一个与 'a 没有生命周期链接的拥有值，编译器会在某一时刻抱怨生命周期不匹配。

为了做到这一点，您的迭代器必须使用绑定到 'a 的东西，可能是某种形式的 Option<Ref<'a, _>>.

但是，另一个限制是当您嵌套 RefCell 时，对于迭代的每个级别，您需要保留一个额外的 Ref。原因是从 Ref 借用的不是 RefCell 的生命周期，而是 Ref 本身。

let refc = RefCell::new(RefCell::new(RefCell::new(42)));
let ref1 = refc.borrow(); // these all need
let ref2 = ref1.borrow(); // to be preserved
let ref3 = ref2.borrow(); // to access `v`
let v = &*ref3;

因此，如果您尝试仅将一个 Ref 与另一个链接起来，它将遇到一个 "return 引用当前函数拥有的数据的值"= 72=] 一种或另一种形式的错误。如果您改为尝试将所有这些 Ref 保留在迭代器中，那么它会创建一个自引用结构。不好看

您只能通过在每个级别（您已经完成）克隆 Rc 来获得一个拥有的值并逃脱前一个 [=15= 的生命周期来解决这个问题].

因此您不能 return 迭代器的引用类型。您唯一的选择是 return 一个拥有的值，在这种情况下这不是理想的，因为它要么必须是 cloned Entry，要么一个 Rc<RefCell<SkipNode<K, V>>>，或者一个 Rc 的包装器，可以正确地暴露 Entry。

这是一个工作版本。我添加的 EntryRef 包装器可能会更好，但它有效并证明了这一点。

pub struct EntryRef<K, V> { ptr: Rc<RefCell<SkipNode<K, V>>>, } impl<K, V> EntryRef<K, V> { pub fn get_entry(&self) -> Ref<'_, Entry<K, V>> { Ref::map(self.ptr.borrow(), |node| node.entry.as_ref().unwrap()) } } pub struct Iter<K: Ord, V> { ptr: Option<Rc<RefCell<SkipNode<K, V>>>>, } impl<K, V> Iterator for Iter<K, V> where K: Ord, { type Item = EntryRef<K, V>; fn next(&mut self) -> Option<Self::Item> { self.ptr.take().map(|node| { self.ptr = node.borrow().next_by_height[0] .as_ref() .map(|ref node| Rc::clone(node)); EntryRef { ptr: node } }) } }

另请参阅：

Borrowed RefCell does not last long enough when iterating over a list

如何为 Rc<RefCell<T>> 链实现迭代器？

How to implement Iterator for a Rc<RefCell<T>> chain?

iterator

smart-pointers

lifetime

rust