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

Question

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

#[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 被更改为最后一个 val 为 5 的 NodeList:

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 block 都应该包含大量注释，解释代码如何安全并且不会破坏您需要维护的保证。

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

另见:

• Why is it discouraged to accept a reference to a String (&String), Vec (&Vec) or Box (&Box) as a function argument?
• Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time