递归特征函数的生命周期问题

Question

我很难将我的独立 merge_sort 函数转换为 Vec<T> 的特征。看来我运行陷入合并排序算法工作方式的生命周期错误。

我已经尝试在函数和特征声明中指定生命周期，但它仍然给我一个类似的错误。

我对寿命的研究包括...

有效 Rust
Rust 书
关于一生的几个 YouTube 视频
关于生命周期的 Stack Overflow 上的大多数问题

这是代码

trait MergeSortable<T> {
    fn merge_sort(&mut self);
    fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>;
}

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> {
    fn merge_sort(&mut self) {
        if self.len() <= 1 {
            return;
        }
        let mid = self.len() / 2;
        let mut left = self[..mid].to_vec();
        left.merge_sort();
        let mut right = self[mid..].to_vec();
        right.merge_sort();
        self = self._merge(&mut left, &mut right);
    }

    fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
        if left.len() == 0 {
            return right;
        }
        if right.len() == 0 {
            return left;
        }
        if left[0] < right[0] {
            let mut v: Vec<T> = Vec::new();
            v.push(left[0].clone());
            v.extend_from_slice(&self._merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]);
            return &mut v;
        }
        let mut v: Vec<T> = Vec::new();
        v.push(right[0].clone());
        v.extend_from_slice(&self._merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]);
        return &mut v;
    }
}

(Playground)

错误：

error: lifetime of reference outlives lifetime of borrowed content... [E0312]
  --> <anon>:27:20
   |>
27 |>             return left;
   |>                    ^^^^
note: ...the reference is valid for the anonymous lifetime #1 defined on the block at 22:75...
  --> <anon>:22:76
   |>
22 |>     fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>                                                                            ^
note: ...but the borrowed content is only valid for the anonymous lifetime #2 defined on the block at 22:75
  --> <anon>:22:76
   |>
22 |>     fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>                                                                            ^

error: lifetime of reference outlives lifetime of borrowed content... [E0312]
  --> <anon>:24:20
   |>
24 |>             return right;
   |>                    ^^^^^
note: ...the reference is valid for the anonymous lifetime #1 defined on the block at 22:75...
  --> <anon>:22:76
   |>
22 |>     fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>                                                                            ^
note: ...but the borrowed content is only valid for the anonymous lifetime #3 defined on the block at 22:75
  --> <anon>:22:76
   |>
22 |>     fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>                                                                            ^
help: consider using an explicit lifetime parameter as shown: fn _merge<'a, 'b>(&'a self, left: &'a mut Vec<T>, right: &'b mut Vec<T>)
 -> &mut Vec<T>
  --> <anon>:22:5
   |>
22 |>     fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>     ^

Answer 1

在您将其转换为特征版本之前，我不明白它是如何工作的。问题出在 _merge:

的签名上

fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>;

该签名实际上是 shorthand 用于：

fn _merge<'a>(&'a self, left: &mut Vec<T>, right: &mut Vec<T>) -> &'a mut Vec<T>;

这意味着，returned 值必须是从 self 借来的。在你的情况下，这完全不是真的，因为你要么 return left 或 right，要么是一个全新的向量（而你 ). The easiest way to fix it would be to return just Vec<T>. Or if you want to save a .clone() when returning left or right, you can return a Cow<[T]> （我认为它不值得不过。

此外，我认为 _merge 并不真正属于特征，您甚至没有在那里使用 self。我会把它变成一个函数。

Answer 2

_merge 实际上并不需要它的 self 参数。让我们删除它：

use std::cmp::Ord;
use std::clone::Clone;

trait MergeSortable<T> {
    fn merge_sort(&mut self);
    fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>;
}

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> {
    fn merge_sort(&mut self) {
        if self.len() <= 1 {
            return;
        }
        let mid = self.len() / 2;
        let mut left = self[..mid].to_vec();
        left.merge_sort();
        let mut right = self[mid..].to_vec();
        right.merge_sort();
        self = Self::_merge(&mut left, &mut right);
    }

    fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
        if left.len() == 0 {
            return {right};
        }
        if right.len() == 0 {
            return {left};
        }
        if left[0] < right[0] {
            let mut v: Vec<T> = Vec::new();
            v.push(left[0].clone());
            v.extend_from_slice(&Self::_merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]);
            return &mut v;
        }
        let mut v: Vec<T> = Vec::new();
        v.push(right[0].clone());
        v.extend_from_slice(&Self::_merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]);
        return &mut v;
    }
}

现在我们得到一个不同的错误：

error: missing lifetime specifier [--explain E0106]
 --> <anon>:6:57
  |>
6 |>     fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>;
  |>                                                         ^^^^^^^^^^^
help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `left` or `right`

error: missing lifetime specifier [--explain E0106]
  --> <anon>:22:57
   |>
22 |>     fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> {
   |>                                                         ^^^^^^^^^^^
help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `left` or `right`

这有助于我们理解第一个问题：当有一个 self 参数并且 return 值是一个引用时，编译器将推断 returned 的生命周期参考链接到 self。这里根本不是这样！通过删除 self 参数，编译器将面临两个引用参数，当前的省略规则使得您必须指定显式生命周期。

所以，让我们开始吧！

use std::cmp::Ord;
use std::clone::Clone;

trait MergeSortable<T> {
    fn merge_sort(&mut self);
    fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T>;
}

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> {
    fn merge_sort(&mut self) {
        if self.len() <= 1 {
            return;
        }
        let mid = self.len() / 2;
        let mut left = self[..mid].to_vec();
        left.merge_sort();
        let mut right = self[mid..].to_vec();
        right.merge_sort();
        self = Self::_merge(&mut left, &mut right);
    }

    fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T> {
        if left.len() == 0 {
            return right;
        }
        if right.len() == 0 {
            return left;
        }
        if left[0] < right[0] {
            let mut v: Vec<T> = Vec::new();
            v.push(left[0].clone());
            v.extend_from_slice(&Self::_merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]);
            return &mut v;
        }
        let mut v: Vec<T> = Vec::new();
        v.push(right[0].clone());
        v.extend_from_slice(&Self::_merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]);
        return &mut v;
    }
}

但是现在，我们收到了更多错误。让我们关注这个：

error: `v` does not live long enough
  --> <anon>:33:25
   |>
33 |>             return &mut v;
   |>                         ^
note: reference must be valid for the lifetime 'a as defined on the block at 22:81...
  --> <anon>:22:82
   |>
22 |>     fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T> {

您正在尝试 return 对局部变量的引用。您不能那样做：您必须 return 值本身，就像您在原始函数中所做的那样。有关详细信息，请参阅。

也许您不知道的一个技巧是您可以通过分配给它的取消引用来替换引用后面的值 (*self = new_value)。

use std::cmp::Ord;
use std::clone::Clone;

trait MergeSortable<T> {
    fn merge_sort(&mut self);
    fn _merge(left: Vec<T>, right: Vec<T>) -> Vec<T>;
}

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> {
    fn merge_sort(&mut self) {
        if self.len() <= 1 {
            return;
        }
        let mid = self.len() / 2;
        let mut left = self[..mid].to_vec();
        left.merge_sort();
        let mut right = self[mid..].to_vec();
        right.merge_sort();
        *self = Self::_merge(left, right);
    }

    fn _merge(left: Vec<T>, right: Vec<T>) -> Vec<T> {
        if left.len() == 0 {
            return right;
        }
        if right.len() == 0 {
            return left;
        }
        if left[0] < right[0] {
            let mut v: Vec<T> = Vec::new();
            v.push(left[0].clone());
            v.extend_from_slice(&Self::_merge(left[1..].to_vec(), right)[..]);
            return v;
        }
        let mut v: Vec<T> = Vec::new();
        v.push(right[0].clone());
        v.extend_from_slice(&Self::_merge(left, right[1..].to_vec())[..]);
        return v;
    }
}

我还会考虑将 _merge 移出 trait 并放入一个自由函数中，这样您就不必编写 Self::_merge 来调用它了。

递归特征函数的生命周期问题

Problems with lifetimes on recursive trait functions

mergesort

lifetime

rust