提问人:Elfen Dew 提问时间:11/15/2023 最后编辑:Elfen Dew 更新时间:11/15/2023 访问量:65
这个 rust 代码用于从未排序的链表中删除重复项,在 else 分支的低级上做什么?
What is this rust code to remove duplicates from an unsorted linked list doing on a low-level in the else branch?
问:
我有一个链表:
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;
- 给出第一个函数中发生的事情的细分,以及为什么这会将所有权恢复到当前状态并移动到下一个节点?
- 解释为什么 self.head 在函数返回后仍然指向列表的原始头部,但如果在第 A3 行中被注释掉,则指向列表的末尾 (None)。
current = &mut current.as_mut().unwrap().next
我有一个带有此处代码的游乐场(打印调试语句有点嘈杂):https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0015a922b6cc0f7284c9b37d0dfb95e6
我的理解如下,可能有缺陷:
while let Some(mut node) = current.take()
(答0)这条线在循环的每次迭代中都拥有电流的所有权,并将其交给变量“node”。 因此,它是 None。current
let next = node.next.take();
(答1)此行获取 node.next 的所有权,并将其存储在变量中以供以后使用。 因此,它是 None。next
node.next
*current = Some(node);
(答2)再次将电流指向节点。current 不再是 None。它现在指向节点 { val:(无论当前值是多少),next:None}current = &mut current.as_mut().unwrap().next;
(答3)如果没有此行,循环仍将前进,但当函数返回给调用方时,链表最终将指向列表的末尾 (None)。此处的值应始终为 None,因为我们在 A1 中从 node.next 中夺走了所有权。current.as_mut().unwrap().next;
*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|
答:
2赞
Chayim Friedman
11/15/2023
#1
这里棘手的部分是,在行之后,确实是 ,但没有值 ,它是指向节点的指针。current = &mut current.as_mut().unwrap().next
*current
None
current
None
next
鉴于它是一个指针,我们不仅可以用它来观察,还可以改变它。基本上,我们前进作为指向节点中当前列表的指针。next
current
如果我们省略这一行,将始终指向 ,并且应用于它的所有更改都将应用于 。因此,我们将浏览列表,但只需更改并删除所有节点,从而导致指向最后一个节点。current
head
head
head
head
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;
}
}
}
}
应该可以工作,但目前不能,因为当前借用检查器存在已知的缺点。
评论
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。
评论