在 Rust 中使用递归函数生成树结构时的多个可变借用 [英] Multiple mutable borrows when generating a tree structure with a recursive function in Rust
问题描述
我在实现一个递归函数时遇到了麻烦，该函数通过操作索引到不可变列表的可变索引列表来生成二叉树.
I'm having trouble implementing a recursive function that generates a binary tree by manipulating a mutable list of indices that index into an immutable list.
代码如下:
enum Tree<'r, T:'r> {
Node(Box<Tree<'r, T>>,
&'r T,
Box<Tree<'r, T>>),
Empty
}
fn process_elements<T>(xs: &mut [T]) {
// interesting things happen here
}
// This function creates a tree of references to elements in a list 'xs' by
// generating a permutation 'indices' of a list of indices into 'xs',
// creating a tree node out of the center element, then recursively building
// the new node's left and right subtrees out of the elements to the left and
// right of the center element.
fn build_tree<'r, T>(xs: &'r [T],
indices: &'r mut [uint]) -> Box<Tree<'r, T>> {
let n = xs.len();
if n == 0 { return box Empty; }
process_elements(indices);
let pivot_index = n / 2;
let left_subtree =
// BORROW 1 ~~~v
build_tree(xs, indices.slice_to_or_fail_mut(&pivot_index));
let right_subtree =
// BORROW 2 ~~~v
build_tree(xs, indices.slice_from_or_fail_mut(&(pivot_index + 1)));
box Node(left_subtree, &xs[pivot_index], right_subtree)
}
当我尝试编译它时，我收到一个错误，说我不能一次多次借用 *indices 作为可变变量，其中第一次借用发生在标记为 BORROW 1 第二次借位发生在 BORROW 2.
When I try to compile this, I get an error saying that I can't borrow *indices as mutable more than once at a time, where the first borrow occurs at the comment marked BORROW 1 and the second borrow occurs at BORROW 2.
我清楚地看到 *points 确实在这两个位置被借用，但在我看来 *points 的第一次借用应该只持续到最后在 let left_subtree 语句中对 build_tree 的单个递归调用.然而，Rust 声称这个借用实际上会持续到整个 build_tree 函数结束.
I clearly see that *points does get borrowed at both of those locations, but it appears to me that the first borrow of *points should only last until the end of that single recursive call to build_tree in the let left_subtree statement. However, Rust claims that this borrow actually lasts until the end of the entire build_tree function.
谁能解释一下:
- 为什么第一次借用会持续到
build_tree函数结束，以及 - 如何在 Rust 中正确实现这样的函数?
顺便说一句:如果我删除了let left_subtree ="和"let right_subtree ="(即，使用对build_tree的递归调用仅用于它们对索引的副作用 并将 Nones 传递给 Node 构造函数)，代码编译得很好并且不会抱怨多次借用.这是为什么?
By the way: if I remove the "let left_subtree =" and "let right_subtree =" (i.e., use the recursive calls to build_tree only for their side-effects on indices and pass Nones to the Node constructor), the code compiles just fine and does not complain about multiple borrows. Why is this?
推荐答案
build_tree 的结果是 Box.借用一直到函数结束，因为结果仍然从切片借用，正如 Tree 的生命周期参数所证明的那样.
The result of build_tree is Box<Tree<'r, T>>. The borrows extend until the end of the function because the result still borrows from the slice, as evidenced by the lifetime parameter to Tree.
编辑:对于您的情况，以下更改完全没有必要.只需从 indices 参数中删除 'r:indices: &mut [uint].否则，编译器会假设您仍然从切片中借用，因为返回的 Tree 将该生命周期作为参数.通过删除 indices 上的生命周期，编译器将推断出一个不同的生命周期.
EDIT: The changes below are completely unnecessary in your case. Simply remove 'r from the indices parameter: indices: &mut [uint]. Otherwise, the compiler assumes that you still borrow from the slice because the returned Tree has that lifetime as a parameter. By removing the lifetime on indices, the compiler will infer a distinct lifetime.
要将可变切片分成两部分，请使用 <代码>split_at_mut.split_at_mut 使用 unsafe 代码来解决编译器的限制，但该方法本身不是 unsafe.
To split a mutable slice into two, use split_at_mut. split_at_mut uses unsafe code to work around compiler limitations, but the method itself is not unsafe.
fn build_tree<'r, T>(xs: &'r [T],
indices: &'r mut [uint]) -> Box<Tree<'r, T>> {
let n = xs.len();
if n == 0 { return box Empty; }
process_elements(indices);
let pivot_index = n / 2;
let (indices_left, indices_right) = indices.split_at_mut(pivot_index);
let (_, indices_right) = indices_right.split_at_mut(1);
let left_subtree = build_tree(xs, indices_left);
let right_subtree = build_tree(xs, indices_right);
box Node(left_subtree, &xs[pivot_index], right_subtree)
}
这篇关于在 Rust 中使用递归函数生成树结构时的多个可变借用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
