为什么先借后用在这里？

Question

我正在学习 Rust，并试图实现一个单链表。一切都很顺利，直到我尝试实现一个从列表中删除尾部的函数。

LinkedList的定义：

pub struct LinkedList<T> {
    head: Link<T>,
}

#[derive(Debug)]
struct Node<T> {
    ele: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

我首先尝试使用

while let

但失败了：

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail_not_working_1(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        while let Some(node) = cur {
            if node.next.is_none() {
                return cur.take().map(|tail| tail.ele);
            }
            cur = &mut node.next;
        }
        None
    }
}

有错误消息

error[E0499]: cannot borrow `*cur` as mutable more than once at a time
  --> src/linked_list.rs:66:24
   |
64 |         while let Some(node) = cur {
   |                        ---- first mutable borrow occurs here
65 |             if node.next.is_none() {
66 |                 return cur.take().map(|tail| tail.ele);
   |                        ^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first borrow later used here

然后我尝试了

loop + match

，仍然失败：

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail_not_working_2(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        loop {
            match cur {
                None => return None,
                Some(node) => {
                    if node.next.is_none() {
                        return cur.take().map(|tail| tail.ele);
                    }
                    cur = &mut node.next;
                }
            }
        }
    }
}

有类似的错误消息：

error[E0499]: cannot borrow `*cur` as mutable more than once at a time
  --> src/linked_list.rs:54:32
   |
52 |                 Some(node) => {
   |                      ---- first mutable borrow occurs here
53 |                     if node.next.is_none() {
54 |                         return cur.take().map(|tail| tail.ele);
   |                                ^^^
   |                                |
   |                                second mutable borrow occurs here
   |                                first borrow later used here

最后，我尝试了

match

守卫，它起作用了

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        loop {
            match cur {
                None => return None,
                Some(node) if node.next.is_none() => {
                    return cur.take().map(|tail| tail.ele);
                }
                Some(node) => cur = &mut node.next,
            }
        }
    }
}

我不确定为什么第三个实现有效，但前两个实现无效，我认为它们都有相同的逻辑。具体来说，我真的对短语

first borrow later used here

感到困惑，我不知道为什么当第二个可变借用发生时使用第一个借用？

Answer 1

您可以跟踪链接列表的大小，以便知道如何根据大小修改它：

pub struct LinkedList<T> {
    head: Link<T>,
    size: usize,
}

#[derive(Debug)]
struct Node<T> {
    ele: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            size: 0,
        }
    }

    pub fn pop_tail(&mut self) -> Option<T> {
        if self.size == 0 {
            return None;
        }
        if self.size == 1 {
            let res = self.head.take().map(|n| n.ele);
            self.size -= 1;
            return res;
        }
        let mut last_node = self.head.as_mut();
        for _ in 0..self.size-2 {
            last_node = last_node.and_then(|e| e.next.as_mut());
        }
        self.size -= 1;
        last_node.unwrap().next.take().map(|n| n.ele)
    }
}

fn main() {
    let mut list = LinkedList {
        head: Some(Box::new(Node {ele: 10, next: Some(Box::new(Node {ele: 20, next: None}))})),
        size: 2,
    };
    
    
    let value = list.pop_tail();
    println!("{}", list.size);
    println!("{}", value.unwrap());
    
}

游乐场

Answer 2

使用“拥有”的值比使用引用要容易得多。

实施：

impl<T> LinkedList<T> {
    pub fn pop_tail(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }

        let mut node = self.head.take().unwrap();
        let mut tail = &mut self.head;

        while let Some(next) = node.next.take() {
            *tail = Some(node);
            tail = &mut tail.as_mut().unwrap().next;
            node = next;
        }

        Some(node.ele)
    }
}

一个相当蹩脚的测试用例（playground链接）：

fn main() {
    let mut head: LinkedList<i32> = LinkedList { head: None };
    println!("Before: {:?}", head);
    assert_eq!(None, head.pop_tail());
    println!("After: {:?}", head);

    let mut head = LinkedList {
        head: Some(Box::new(Node { next: None, ele: 1 })),
    };
    println!("Before: {:?}", head);
    assert_eq!(Some(1), head.pop_tail());
    println!("After: {:?}", head);

    let mut head = LinkedList {
        head: Some(Box::new(Node {
            ele: 1,
            next: Some(Box::new(Node { next: None, ele: 2 })),
        })),
    };
    println!("Before: {:?}", head);
    assert_eq!(Some(2), head.pop_tail());
    println!("After: {:?}", head);
}