在 Rust 中实现链表时如何复制原始指针?

Question

我正在用 Rust 编写一个递归类型ListNode。我必须在结构中使用Box，并且我正在尝试编写一个循环来添加nextListNode。但是，我想尝试使用指针，但递归方法除外。

#[derive(Debug)]
struct ListNode {
val: i32,
next: Option<Box<ListNode>>,
}
impl ListNode {
fn new(i: i32) -> Self {
ListNode { val: i, next: None }
}
fn add_l(&mut self, l: &Vec<i32>) {
let mut p: *mut ListNode = self as *mut ListNode;
for i in l {
unsafe {
(*p).next = Some(Box::new(ListNode::new(*i)));
let temp_b = Box::from_raw(p);
p = Box::into_raw(temp_b.next.wrap());
};
}
}
}
fn main() {
let mut a = ListNode::new(1);
a.add_l(&vec![2, 3, 4, 5]);
println!("{:?}", a);
}

我发现a更改为最后一个NodeList，val为 5：

ListNode { val: 5, next: None }

1. 有什么方法可以复制指针以保持a稳定吗？
2. 如果无法复制指针，我该如何实现？

Answer 1

首先要做的是：在这里使用unsafe是完全不必要的，如果我在任何真实代码中看到它，我会说是恶意的。不要用unsafe来"好玩"。

下面是一个完全安全的函数实现，它向后移动以构造要添加的列表的新尾部：

fn add_l(&mut self, l: &[i32]) {
let mut tail = None;
for &val in l.iter().rev() {
let next = tail.take();
tail = Some(Box::new(ListNode { val, next }));
}
self.next = tail;
}

一个向前发展，但需要unwrap：

fn add_l(&mut self, l: &[i32]) {
let mut head = self;
for &val in l {
head.next = Some(Box::new(ListNode::new(val)));
head = { head }.next.as_mut().unwrap();
}
}

如果你必须在前进的方向上这样做并且必须避开unwrap，那么也许你可以使用unsafe.每个unsafe块都应该包含大量的注释，解释代码是如何安全的，并且不会破坏你需要坚持的保证。

fn add_l(&mut self, l: &[i32]) {
let mut head = self;
for &val in l {
unsafe {
// Boxing a value gives it a stable address.
let mut node = Box::new(ListNode::new(val));
// So long as this raw pointer doesn't escape this block, 
// we don't need to worry about its lifetime as it should 
// outlive what we need.
let node_raw = &mut node as &mut ListNode as *mut ListNode;
head.next = Some(node);
// Now that we've moved the `Box` into its final place,
// we throw away the reference to head to avoid mutable 
// aliasing
head = &mut *node_raw;
}
}
}

另请参阅：

• 为什么不鼓励接受对字符串(&String(，Vec(&Vec(或Box(&Box(的引用作为函数参数？
• 迭代递归结构时无法获得可变引用：一次不能多次借用可变
引用

Answer 2

您在这里遇到了许多问题，这些问题都与复制指针无关。

我明白你想做什么，但你看到的是"未定义的行为"在行动，而不是复制指针值失败。

首先，这个：

temp_b.next.unwrap()

解包不会留下对象;它会消耗它。每次迭代，您都将next的值设置为无，因为您称之为unwrap。

其次，在循环的第一次迭代中，将原始指针转换为一个框：

let mut p: *mut ListNode = self as *mut ListNode;
// ... p is not reassigned before calling the next statement
Box::from_raw(p);

因此，当您使用temp_b时，您将删除(释放(根对象 a。

这不会立即触发崩溃，但这意味着您现在已经有效地损坏了堆栈。超过这一点的所有内容都是未定义的行为。

跟踪实际指针值时，请查看输出：

#[derive(Debug)]
struct ListNode {
val: String,
next: Option<Box<ListNode>>,
}
impl ListNode {
fn new(i: &str) -> Self {
ListNode { val: format!("{:?}", i), next: None }
}
fn add_l(&mut self, l: &Vec<&str>) {
let mut p: *mut ListNode = self as *mut ListNode;
println!("self -> {:?}", self as *mut ListNode);
for i in l {
unsafe {
(*p).next = Some(Box::new(ListNode::new(*i)));
let temp_b = Box::from_raw(p);
println!("{:?} -> {:?}", p, temp_b);
p = Box::into_raw(temp_b.next.unwrap());
println!("next p -> {:?}", p);
};
}
println!("self -> {:?}", self as *mut ListNode);
}
}
fn main() {
let mut a = ListNode::new("1");
a.add_l(&vec!["2", "3", "4", "5"]);
println!("self -> {:?}", &mut a as *mut ListNode);
println!("{:?}", a);
}

。

self -> 0x7ffdc10a90f0
0x7ffdc10a90f0 -> ListNode { val: ""1"", next: Some(ListNode { val: ""2"", next: None }) }
next p -> 0x7fdde801f060
0x7fdde801f060 -> ListNode { val: ""2"", next: Some(ListNode { val: ""3"", next: None }) }
next p -> 0x7ffdc10a90f0
0x7ffdc10a90f0 -> ListNode { val: ""3"", next: Some(ListNode { val: ""4"", next: None }) }
next p -> 0x7fdde801f060
0x7fdde801f060 -> ListNode { val: ""4"", next: Some(ListNode { val: ""5"", next: None }) }
next p -> 0x7ffdc10a90f0 <---- Whhhaaaat! You've been reallocated!
self -> 0x7ffdc10a90f0
self -> 0x7ffdc10a90f0
ListNode { val: ""5"", next: None }

所以......这就是为什么使用unsafe是不安全的。

如果不一直使用原始指针，就无法做您想做的事情;我建议你看看Rc你想做什么。