再帰的形質機能の寿命に関する問題

Question

私のスタンドアロンのmerge_sort関数をVec<T>の特性に変換するのは苦労しています。私は、マージソートアルゴリズムが動作する方法で生涯エラーに遭遇しているようです。

私は関数と特性宣言で寿命を指定しようとしましたが、それでも私には同様のエラーが出ています。 が寿命に私の研究が含まれ

...

• 効果的な錆
• 錆帳
寿命に
• いくつかのYouTubeの動画スタックオーバーフローに関する寿命の
• ほとんどの質問

コードはこちら

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は、実際には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パラメータと戻り値があるときは、参照され、コンパイラは、返された参照の存続期間がselfにリンクされていると推論します。それはすべてここでは当てはまりません！ selfパラメータを削除すると、コンパイラは参照である2つの引数に直面し、現在のエリミッションルールによって、にはが明示的な有効期間を指定する必要があります。

だから、やりましょう！

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 local String as a slice (&str)を参照してください。

あなたが知らなかったことの1つは、参照の後ろの値を参照解除（*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; 
    } 
} 

私はまた、あなたがそれを呼び出すためにSelf::_mergeを記述する必要はありませんように、形質のうち、およびフリー機能に_mergeを移動することを検討します。

Answer 2

あなたは形質バージョンにそれを変換する前に、私はこれが働いてどのように表示されません。問題は_mergeの署名である：

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

署名は、実際の短縮形であること：戻り値はselfから借りなければならないことを、意味

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

。あなたの場合は、leftまたはright、まったく新しいベクトル（そしてあなたはcan't return a reference to a local variable）のいずれかを返すので、それはまったく真実ではありません。それを修正する最も簡単な方法は、ちょうどVec<T>を返すことです。またはleftまたはrightを返すときに.clone()を保存する場合は、​​を返すことができます（ただし、それは価値があるとは思いません）。

また、私は_mergeは実際には形質に属していないと思いますが、そこにはselfも使用されていません。私は単なる機能にしたいと思う。