创建一个简单的链表

Question

我很难让借用检查器为一个简单的迭代链表构建器工作.

fn main() {                                                        
    let v = vec![1,5,3,8,12,56,1230,2,1];                          
    let nodes = Vec::<Node>::with_capacity(v.len());               
    let mut root: Option<&mut Box<Node>> = None;                   
    let mut prev: &Option<&mut Box<Node>> = &None;                 

    for i in v {                                                   
        let curr = Some(&mut Box::new(Node { value: i, next: None }));
        match *prev {                                              
            Some(ref mut p) => {                                   
                p.next = curr;                                        
                prev = &mut p.next;                                
            },                                                     
            None => {                                              
                root = curr;                                          
                prev = &mut root;                                  
            }                                                      
        }                                                          
    }                                                              
}                                                                  

struct Node<'a> {                                                  
    value: i32,                                                    
    next: Option<&'a mut Box<Node<'a>>>,                           
}                         

我尝试编译时收到的错误:

linked_list.rs:8:30: 8:69 error: borrowed value does not live long enough
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:4:49: 20:2 note: reference must be valid for the block suffix following statement 2 at 4:48...
linked_list.rs:4     let mut root: Option<&mut Box<Node>> = None;
linked_list.rs:5     let mut prev: &Option<&mut Box<Node>> = &None;
linked_list.rs:6 
linked_list.rs:7     for i in v {
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
linked_list.rs:9         match *prev {
                 ...
linked_list.rs:8:9: 8:71 note: ...but borrowed value is only valid for the statement at 8:8
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:8:9: 8:71 help: consider using a `let` binding to increase its lifetime
linked_list.rs:8         let curr = Some(&mut Box::new(Node { value: i, next: None }));
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:10:18: 10:27 error: cannot borrow immutable anonymous field `(prev:core::option::Some).0` as mutable
linked_list.rs:10             Some(ref mut p) => {
                                   ^~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:15:17: 15:28 error: cannot assign to `root` because it is borrowed
linked_list.rs:15                 root = curr;
                                  ^~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: borrow of `root` occurs here
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 error: cannot borrow `root` as mutable more than once at a time
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: previous borrow of `root` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `root` until the borrow ends
linked_list.rs:16                 prev = &mut root;
                                              ^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:20:2: 20:2 note: previous borrow ends here
linked_list.rs:1 fn main() {
...
linked_list.rs:20 }
                  ^
error: aborting due to 4 previous errors

我想要的是相当简单的.我们遍历Vec,在每次迭代时创建一个新节点.如果prev为None,则必须是start,因此我们使root变量取得第一个节点的所有权.如果不是,我们更新上一个节点的下一个值以指向该节点.

我是Rust的新手,所以我不确定我哪里出错了.我的解释是借用检查员没有很好地处理这个问题.它无法推断匹配中包含"根"赋值的None分支只会被调用一次,导致有关root的两个错误被借用两次.我对么？

这种方法在Rust中可行吗？是否有更惯用的方式来做这种事情？

(递归方法可能更容易,但我想完成一个迭代的方法作为学习练习.)

Answer 1

首先,您应该确保阅读并理解有关所有权和参考资料以及借阅的Rust Book章节.你当前的问题是,你借的东西并非由任何东西拥有,因此就会消失.您还有其他问题,例如尝试通过不可变指针进行变异.

让我们得到的东西至少可以起作用:

fn main() {
    let v = vec![1,5,3,8,12,56,1230,2,1];
    let mut root: Option<Box<Node>> = None;

    for i in v.into_iter().rev() {
        root = Some(Box::new(Node { value: i, next: root }));
    }

    println!("root: {}",
        root.map(|n| n.to_string()).unwrap_or(String::from("None")));
}

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

impl std::fmt::Display for Node {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        let mut cur = Some(self);
        let mut first = true;
        try!(write!(fmt, "["));
        while let Some(node) = cur {
            if !first { try!(write!(fmt, ", ")); }
            first = false;
            try!(write!(fmt, "{}", node.value));
            cur = node.next.as_ref().map(|n| &**n);
        }
        try!(write!(fmt, "]"));
        Ok(())
    }
}

这构造了一个列表,并显示了如何迭代显示它.请注意施工代码中完全没有借用.

我已经有点被骗了,因为我已经重述,矢量向后构建列表.

原始代码的问题在于,即使您删除了所有不必要的内容,也可以执行以下操作:

let v = vec![1,5,3,8,12,56,1230,2,1];
let mut v = v.into_iter();

let mut root: Option<Box<Node>> = None;
if let Some(i) = v.next() {
    root = Some(Box::new(Node { value: i, next: None }));
    let mut prev: &mut Box<Node> = root.as_mut().unwrap();

    for i in v {
        let curr = Some(Box::new(Node { value: i, next: None }));
        prev.next = curr;
        prev = prev.next.as_mut().unwrap();
    }
}

你仍然会遇到这样一种情况,即编译器看到你改变了你用第二条路径借来的东西.这不是很聪明地认识到,重新分配prev并没有真正产生任何别名.另一方面,如果您将循环分解为等效的递归:

if let Some(i) = v.next() {
    root = Some(Box::new(Node { value: i, next: None }));

    fn step<It>(prev: &mut Box<Node>, mut v: It) where It: Iterator<Item=i32> {
        if let Some(i) = v.next() {
            let curr = Some(Box::new(Node { value: i, next: None }));
            prev.next = curr;
            step(prev.next.as_mut().unwrap(), v)
        }
    }

    step(root.as_mut().unwrap(), v);
}

然后它完全没问题.遗憾的是,即使启用了优化,在这种情况下Rust也不会执行尾调用.因此,在借用检查器限制和缺乏保证尾部调用消除之间,这种设计在安全代码中可能是不可能的.

我自己遇到了这个问题; 循环和&mut指针并不总是很好地相互配合.您可以通过切换到RefCell与其相关的运行时成本来解决此问题,尽管这会使循环中的此类列表的迭代变得复杂.另一种方法是使用usizes而不是指针,并将所有节点分配到Vec某个地方,尽管这会引入边界检查开销.

如果没有这一切,就会有unsafe代码,它可以让你或多或少地准确写出你用其他语言写的东西,比如C或C++,但是没有Rust通常的安全保证.

在一天结束的时候,写一个数据结构不只是围绕在安全锈现有的数据结构包装无开销交界不可能的.这就是为什么Rust中的基本数据结构都是使用一些不安全的代码编写的.