Rust中链表的迭代器

fumotvh3  于 2022-12-26  发布在  其他
关注(0)|答案(1)|浏览(209)

我是Rust的新手,正在努力学习它。我已经阅读了大量不同的材料,相信我已经掌握了一些重要概念的要点,如借位检查器、引用、生存期、智能指针等。但我很难理解更深奥的概念,如RefCellMutexesPin等。才能用这些数据结构来编码。对我来说,这些都是非常抽象的。
1.我在哪里可以了解更多关于这些项目的信息,以便实际使用它们进行编码?
1.我有一个特别的问题,关于实现Iterator trait来迭代RefCell内部对LinkedList数据结构的引用,我已经编写了代码,但似乎无法工作,因为它会导致临时借用等问题,而且我完全不知道如何解决这些问题来解决上述问题。
下面是我的代码:

use std::{
    cell::{Ref, RefCell},
    rc::Rc,
};

type LinkNodePtr<T> = Rc<RefCell<LinkNode<T>>>;

pub struct LinkNode<T> {
    data: T,
    next: Option<LinkNodePtr<T>>,
    prev: Option<LinkNodePtr<T>>,
}

#[derive(Debug)]
pub struct LinkedList<T> {
    head: Option<LinkNodePtr<T>>,
    tail: Option<LinkNodePtr<T>>,
    len: usize,
}

impl<'a, T> LinkedList<T> {
    pub fn new(data: T) -> Self {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: None,
            prev: None,
        }));

        LinkedList {
            head: Some(Rc::clone(&link_node_ptr)),
            tail: Some(Rc::clone(&link_node_ptr)),
            len: 1,
        }
    }

    pub fn add_to_head(&mut self, data: T) {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: self.head.take(),
            prev: None,
        }));

        self.head = Some(Rc::clone(&link_node_ptr));

        let link_node = link_node_ptr.borrow_mut();
        if let Some(ref link_node_ptr_next) = link_node.next {
            let mut link_node_next = (*link_node_ptr_next).borrow_mut();
            link_node_next.prev = Some(Rc::clone(&link_node_ptr));
        }

        self.len += 1;
    }

    pub fn add_to_tail(&mut self, data: T) {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: None,
            prev: self.tail.take(),
        }));

        self.tail = Some(Rc::clone(&link_node_ptr));

        let link_node = link_node_ptr.borrow();
        if let Some(ref link_node_ptr_prev) = link_node.prev {
            let mut link_node_prev = (*link_node_ptr_prev).borrow_mut();
            link_node_prev.next = Some(Rc::clone(&link_node_ptr));
        }

        self.len += 1;
    }

    pub fn iter(&'a self) -> LinkedListIter<'a, T> {
        let current = if let Some(ref head) = self.head {
            Some(head.borrow())
        } else {
            None
        };
        LinkedListIter { current }
    }
}

pub struct LinkedListIter<'a, T> {
    current: Option<Ref<'a, LinkNode<T>>>,
}

impl<'a, T> Iterator for LinkedListIter<'a, T> {
    type Item = Ref<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(link_node) = self.current.take() {
            self.current = if let Some(ref link_node_ptr_next) = link_node.next {
                let link_node_next = (*link_node_ptr_next).borrow();
                Some(link_node_next)
            } else {
                None
            };
            Some(Ref::map(link_node, |x| &x.data))
        } else {
            None
        }
    }
}

impl<'a, T> std::fmt::Debug for LinkNode<T>
where
    T: std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("LinkNode")
            .field("data", &self.data)
            .field("next", &self.next)
            .finish()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let mut ll = LinkedList::new(1);
        ll.add_to_tail(2);
        ll.add_to_tail(3);
        ll.add_to_tail(4);
        ll.add_to_head(5);
        ll.add_to_head(6);

        for x in ll.iter() {
            println!("{}", x);
        }

        println!("{:?}", ll);
    }
}
error[E0505]: cannot move out of `link_node` because it is borrowed
  --> src\linked_list.rs:97:27
   |
86 | impl<'a, T> Iterator for LinkedListIter<'a, T> {
   |      -- lifetime `'a` defined here
...
91 |             self.current = if let Some(ref link_node_ptr_next) = link_node.next {
   |                                                                  --------- borrow of `link_node` occurs here
92 |                 let link_node_next = (*link_node_ptr_next).borrow();
   |                                      ------------------------------ argument requires that `link_node` is borrowed for `'a`
...
97 |             Some(Ref::map(link_node, |x| &x.data))
   |                           ^^^^^^^^^ move out of `link_node` occurs here
w7t8yxp5

w7t8yxp51#

我担心它不适用于生存期注解,因为每个节点的生存期都是不同的,这就是为什么Rust中的链表是如此困难,而且大部分都是在"Learn Rust With Entirely Too Many Linked Lists"中布局的,如果你想处理像链表这样的递归数据结构,这是一本很好的读物,几乎是强制性的。
要解决这个问题,不要将Ref值保存到下一项,而是保存Rc本身,这就是Rc的用途。
也就是说,目前不可能从一个借用迭代器本身的迭代器返回一个值,这使得不可能从一个迭代器返回一个Ref,因为Ref必须总是通过一个生存期连接到RefCell,并且RefCell必须存储在迭代器中。
所以现在,恐怕我必须告诉您,没有unsafe(据我所知),您的方法是不可能的。
“完全太多的链表”这篇文章似乎也同意这一点,它有整整一章是关于基于Rc<RefCell<T>>的双链表以及它们是如何与迭代器不兼容的。

**TLDR:**不要尝试在Rust中编写链表。这是一个与Rust所有权规则完全不兼容的概念。如果你想这样做,请先阅读"Learn Rust With Entirely Too Many Linked Lists"

相关问题