我很难让借用检查器为简单的迭代链表构建器工作。
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 这一定是开始，所以我们让 root 变量获得第一个节点的所有权。如果不是，我们更新前一个节点的下一个值以指向该节点。
我是 Rust 的新手，所以我不确定我哪里出错了。我的解释是借用检查器处理得不好。它不能推断匹配中的 None 分支，包含 'root' 赋值，只会被调用一次，从而导致关于 root 被借用两次的两个错误。我说得对吗？
这种方法在 Rust 中可行吗？有没有更惯用的方法来做这类事情？
(递归方法可能更容易，但我想完成一个迭代方法作为学习练习。)
最佳答案
首先，您可能应该确保您已经阅读并理解了 Rust Book 关于 Ownership 的章节。和 References and Borrowing .您眼前的问题是，您借用的东西不属于任何东西， 将因此消失。您还有其他问题，例如尝试通过不可变指针进行变异。
让我们得到一些至少可以工作的东西:
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 及其相关的运行时成本来解决此问题，尽管这会使在循环中迭代此类列表变得复杂。另一种选择是使用 usize 而不是指针，并将所有节点分配到某处的 Vec 中，尽管这会引入边界检查开销。
如果所有这些都失败，就会出现不安全代码，它可以让您或多或少地编写出与使用其他语言(如 C 或 C++)编写的内容完全相同的代码，但没有 Rust 通常的安全保证。
归根结底，编写不是的数据结构只是在安全的 Rust 中围绕现有数据结构进行包装而没有开销是不可能的。这就是为什么 Rust 中的基本数据结构都是使用一些不安全的代码编写的。
关于rust - 创建一个简单的链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31423174/