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

Question

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

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>作为 Item由 Iterator 返回，但编译器提示 next无法返回临时变量。有没有一种优雅的方式来实现 Iterator对于 Rc<RefCell> ?

Answer 1

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

不是特别。你的路上有两件大事。

构建 Iterator 时的一个限制是输出类型不能引用迭代器本身。它可以返回一个拥有的值(不涉及生命周期)或返回绑定(bind)到某个其他对象的生命周期的引用。
我看到你试图传达你想要返回 Ref s 绑定(bind)到原始 SkipList 的生命周期通过使用 PhantomData<&'a K>并且还使用 'a在您的 Iterator::Item .但是，由于您的迭代器只能从 ptr 获取值。 , 一个与 'a 没有生命周期联系的拥有值，编译器会在某一时刻提示不匹配的生命周期。
为了做到这一点，你的迭代器必须使用绑定(bind)到 'a 的东西。 ，可能是 Option<Ref<'a, _>> 的某种形式.

但是，另一个限制是当您嵌套了 RefCell s，对于您迭代的每个级别，您需要保持一个额外的 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与另一个链接，它将以一种或另一种形式遇到“返回引用当前函数拥有的数据的值”错误。如果您尝试保留所有这些 Ref s 在迭代器中，然后它创建一个自引用结构。不太好。
您只能通过克隆 Rc 来解决此问题。 s 在每个级别(您已经完成)以获得拥有的值并逃脱前一个 Ref 的生命周期.

所以你不能为你的迭代器返回一个引用类型。您唯一的选择是返回一个拥有的值，在这种情况下这并不理想，因为它要么必须是一个克隆的 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 }
        })
    }
}

也可以看看:

How do I write an iterator that returns references to itself?

Why can't I store a value and a reference to that value in the same struct?

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