rust - 通用特征和 slice::sort_by 的生命周期问题

Question

作为学习练习，我一直在编写排序库，但遇到了障碍。我已经定义了一个特性 ExtractFrom 来从切片中的项目中提取一个可排序的键(相当于 sort_by_key 会做的事情)。我希望能够提取借用数据的 key ，但我尝试实现该方法失败了。

这是一个简化的示例，它演示了我的尝试。 LargeData 是切片中包含的内容，我定义了 LargeDataKey，它包含对我要排序的数据子集的引用。这在 extract_from 实现和 sort_by 期望之间遇到了生命周期问题，但我不知道如何解决它。任何关于如何最好地实现这一点的解释或建议将不胜感激。

trait ExtractFrom<'a, T> {
    type Extracted;
    fn extract_from(&'a T) -> Self::Extracted;
}

fn sort_by_extractor<'a, T, E>(vec: Vec<T>)
where
    E: ExtractFrom<'a, T>,
    E::Extracted: Ord,
{
    vec.sort_by(|a, b| {
        let ak = &E::extract_from(a);
        let bk = &E::extract_from(b);
        ak.cmp(bk)
    })
}

#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
struct LargeData(String, String, String);

#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
struct LargeDataKey<'a>(&'a str, &'a str);

impl<'a> ExtractFrom<'a, LargeData> for LargeDataKey<'a> {
    type Extracted = LargeDataKey<'a>;
    fn extract_from(input: &'a LargeData) -> LargeDataKey<'a> {
        LargeDataKey(&input.2, &input.0)
    }
}

fn main() {
    let v = vec![
        LargeData("foo".to_string(), "bar".to_string(), "baz".to_string()),
        LargeData("one".to_string(), "two".to_string(), "three".to_string()),
        LargeData("four".to_string(), "five".to_string(), "six".to_string()),
    ];
    sort_by_extractor::<LargeData, LargeDataKey>(v);
    println!("hello");
}

此代码也可在 Rust playground 上找到.

这失败了:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> src/main.rs:12:19
   |
12 |         let ak = &E::extract_from(a);
   |                   ^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the body at 11:17...
  --> src/main.rs:11:17
   |
11 |       vec.sort_by(|a, b| {
   |  _________________^
12 | |         let ak = &E::extract_from(a);
13 | |         let bk = &E::extract_from(b);
14 | |         ak.cmp(bk)
15 | |     })
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:12:35
   |
12 |         let ak = &E::extract_from(a);
   |                                   ^
note: but, the lifetime must be valid for the lifetime 'a as defined on the function body at 6:22...
  --> src/main.rs:6:22
   |
6  | fn sort_by_extractor<'a, T, E>(vec: Vec<T>)
   |                      ^^
   = note: ...so that the types are compatible:
           expected ExtractFrom<'_, T>
              found ExtractFrom<'a, T>

Answer 1

编译器错误清楚地表明这里有两个生命周期:

vec.sort_by(|a: &T, b: &T| {
    let ak = &E::extract_from(a);
    let bk = &E::extract_from(b);
    ak.cmp(bk)
})

• 与a: &T 和b: &T 闭包参数关联的匿名生命周期
• 与'a 生命周期参数关联的生命周期 (fn extract_from(&'a T))

我没有找到在保持设计的同时消除这种生命周期不匹配的方法。

如果您的目标是从切片中的项目中提取可排序的键，这里有一种基于为 LargeData 实现 Ord 的方法:

use std::cmp::Ordering;

#[derive(Debug, PartialOrd, PartialEq, Eq)]
struct LargeData(String, String, String);

// really needed?
// see impl in LargeData::cmp() below
#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
struct LargeDataKey<'a>(&'a str, &'a str);

impl Ord for LargeData {
    fn cmp(&self, other: &LargeData) -> Ordering {
        //let op1 = LargeDataKey(&self.2, &self.0);
        //let op2 = LargeDataKey(&other.2, &other.0);
        //op1.cmp(&op2)
        (&self.2, &self.0).cmp(&(&other.2, &other.0))
    }
}

fn sort_by_extractor<E, T>(vec: &mut Vec<T>, extractor: E)
where
    E: FnMut(&T, &T) -> Ordering,
{
    vec.sort_by(extractor);
}

fn main() {
    let mut v = vec![
        LargeData("foo".to_string(), "bar".to_string(), "baz".to_string()),
        LargeData("one".to_string(), "two".to_string(), "three".to_string()),
        LargeData("four".to_string(), "five".to_string(), "six".to_string()),
    ];

    sort_by_extractor(&mut v, |a, b| a.cmp(b));
    println!("{:?}", v);
}