我有一个链表:

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. 详细说明第一个功能中发生了什么,以及为什么此功能可以将所有权恢复到当前状态并移动到下一个 node ?
  2. 解释为什么在函数返回后,self.head仍然指向列表的原始头,但却指向列表的末尾(无),如果A3行中的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() (A0)这一行在循环的每一次迭代中获取current的所有权,将其赋予变量"node".第current章没有结果
  2. let next = node.next.take(); node.next(A1) This line takes ownership of 第node.next章没有结果
  3. *current = Some(node);个 (A2)再次将电流指向该 node .Current不再是None.它现在指向 node {val:(无论当前值是什么),Next:None}
  4. current = &mut current.as_mut().unwrap().next;个 (A3)如果没有此行,循环仍将前进,但当函数返回到调用方时,链表最终将指向列表的末尾(无).这里current.as_mut().unwrap().next;的值应该始终为None,因为我们从 node 上夺走了所有权.下一步是A1.
  5. *current = next; (A4)将current指向A1中next中存储的下一个 node .

请注意,注释掉倒数第二行(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;
            }
        }
    }

在调用后打印链接列表(使用我的格式化程序),结果是Head==None:

LL(0): |None|

推荐答案

这里的棘手之处在于,在第current = &mut current.as_mut().unwrap().next行之后,*current将确实是None,但是current没有值None,它是 node 的pointernext的一个数.

既然它是一个指针,我们不仅可以用它来观察next,我们还可以改变它.基本上,我们将current作为指向 node 中当前列表的指针.

如果省略这一行,current将始终指向head,对其应用的所有更改都将应用于head.因此,我们将在列表中前进,但只更改head并删除所有 node ,导致head指向最后一个 node None.


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

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;
            }
        }
    }
}

应该可以工作,但当前不能,因为当前borrow 判断器中存在一个已知缺陷.

Rust相关问答推荐

为什么我们不能通过指针算法将Rust原始指针指向任意地址?'

在Rust中赋值变量有运行时开销吗?

如何获取Serde struct 的默认实例

用 rust 蚀中的future 展望 struct 的future

在使用AWS SDK for Rust时,如何使用硬编码访问密钥ID和密钥凭据?

S在Cargo.toml中添加工作空间开发依赖关系的正确方法是什么?

如何创建一个可变的嵌套迭代器?

对于rustc编译的RISC-V32IM二进制文件,llvm objdump没有输出

Rust移动/复制涉及实际复制时进行检测

处理带有panic 的 Err 时,匹配臂具有不兼容的类型

确保参数是编译时定义的字符串文字

.在 Rust 模块标识符中

try 实现线程安全的缓存

从 rust 函数返回 &HashMap

一旦令牌作为文字使用,声明宏不匹配硬编码值?

borrow 匹配手臂内部的可变

为什么我不能克隆可克隆构造函数的Vec?

如何异步记忆选项中的 struct 字段

使用 rust-sqlx/tokio 时如何取消长时间运行的查询

如何创建动态创建值并向它们返回borrow 的工厂?