这个 rust 代码用于从未排序的链表中删除重复项,在 else 分支的低级上做什么?

What is this rust code to remove duplicates from an unsorted linked list doing on a low-level in the else branch?

提问人:Elfen Dew 提问时间:11/15/2023 最后编辑:Elfen Dew 更新时间:11/15/2023 访问量:65

问:

我有一个链表:

pub struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>
}

我的问题涉及此功能以删除重复项:

impl<T: Clone + Eq + Hash> LinkedList<T> {
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() { // AO
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take(); // A1 take rest of list. Node.next is now None
                *current = Some(node); // A2 restore ownership of node to current but its now pointing to None.
                 current = &mut current.as_mut().unwrap().next; // *A3* None because (A1) took ownership. *Why is this line necessary?*
                *current = next; // A4 move to next node to continue with rest of list
            }
        }
    }

它的工作原理和删除重复项,就像以下操作一样,以一种更易于理解的方式:

impl<T: Clone + Eq + Hash> LinkedList<T> {
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() //B0 {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                *current = Some(node); // B1
                 current = &mut current.as_mut().unwrap().next; // B2
            }
        }
    }

我是 rust 的新手,正在努力了解内存中发生的事情。我不明白 A3 行-- --需要什么以及它到底在做什么,但如果没有它,该功能就无法工作。有人可以current = &mut current.as_mut().unwrap().next;

  1. 给出第一个函数中发生的事情的细分,以及为什么这会将所有权恢复到当前状态并移动到下一个节点?
  2. 解释为什么 self.head 在函数返回后仍然指向列表的原始头部,但如果在第 A3 行中被注释掉,则指向列表的末尾 (None)。current = &mut current.as_mut().unwrap().next

我有一个带有此处代码的游乐场(打印调试语句有点嘈杂):https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0015a922b6cc0f7284c9b37d0dfb95e6

我的理解如下,可能有缺陷:

  1. while let Some(mut node) = current.take()(答0)这条线在循环的每次迭代中都拥有电流的所有权,并将其交给变量“node”。 因此,它是 None。current
  2. let next = node.next.take();(答1)此行获取 node.next 的所有权,并将其存储在变量中以供以后使用。 因此,它是 None。nextnode.next
  3. *current = Some(node);(答2)再次将电流指向节点。current 不再是 None。它现在指向节点 { val:(无论当前值是多少),next:None}
  4. current = &mut current.as_mut().unwrap().next;(答3)如果没有此行,循环仍将前进,但当函数返回给调用方时,链表最终将指向列表的末尾 (None)。此处的值应始终为 None,因为我们在 A1 中从 node.next 中夺走了所有权。current.as_mut().unwrap().next;
  5. *current = next;(答4)将电流指向我们存储在 A1 中的下一个节点。next

请注意,注释掉倒数第二行 (A3) 等效于

    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        let mut restore:&mut Option<Box<Node<T>>> = &mut None;
        while let Some(mut node) = current.take() {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take();
                *restore = Some(node);
                 current = &mut restore.as_mut().unwrap().next;
                *current = next;
            }
        }
    }
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take();
                *current = Some(node);
                *current = next;
            }
        }
    }

调用后打印链表(使用我的格式化程序)会导致头部 == 无:

LL(0): |None|
Rust 借用检查器 所有权

评论


答:

2赞 Chayim Friedman 11/15/2023 #1

这里棘手的部分是,在行之后,确实是 ,但没有值 ,它是指向节点的指针current = &mut current.as_mut().unwrap().next*currentNonecurrentNonenext

鉴于它是一个指针,我们不仅可以用它来观察,还可以改变它。基本上,我们前进作为指向节点中当前列表的指针。nextcurrent

如果我们省略这一行,将始终指向 ,并且应用于它的所有更改都将应用于 。因此,我们将浏览列表,但只需更改并删除所有节点,从而导致指向最后一个节点。currentheadheadheadheadNone


请注意,以下更简单的代码:

impl<T: Eq + Hash> LinkedList<T> {
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(node) = current {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(&node.val);
                current = &mut node.next;
            }
        }
    }
}

应该可以工作,但目前不能,因为当前借用检查器存在已知的缺点。

评论

0赞 Elfen Dew 11/15/2023
感谢您的解释,有助于澄清正在发生的事情。你提到的这个已知缺点是什么?是否有包含更多信息的链接?
1赞 Chayim Friedman 11/15/2023
@ElfenDew 就在最近,一篇关于此事的官方博客文章发表了:blog.rust-lang.org/inside-rust/2023/10/06/polonius-update.html