Пожизненная проблема с общей чертой и срезом

Question

В качестве учебного упражнения я писал библиотеку сортировки и сталкиваюсь с препятствиями. Я определил черту ExtractFrom для извлечения сортируемого ключа из элементов в срезе (чтобы сделать эквивалент того, что сделал бы sort_by_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 .

Это не с:

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

Ваш код, скорее всего, будет записан как

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

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

impl<'a> From<&'a LargeData> for LargeDataKey<'a> {
    fn from(input: &'a LargeData) -> LargeDataKey<'a> {
        LargeDataKey(&input.2, &input.0)
    }
}

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()),
    ];
    v.sort_by_key(|x| LargeDataKey::from(x));
    println!("hello");
}

Как подсказывает rodrigo , ваш код не может быть реализован в стабильном Rust 1.30. Это , почему sort_by_key имеет такое ограничение: в настоящее время невозможно разработать черту, охватывающую ваш вариант использования.

Проблема в том, что в Rust в настоящее время нет понятия родственных ассоциированных типов . Это необходимо для того, чтобы иметь возможность определить связанный тип, имеющий конструктор, который может принимать время жизни с поздней привязкой.

Вместо этого вы можете использовать sort_by напрямую, если возвращаемые типы не выходят из замыкания:

v.sort_by(|a, b| {
    let a = LargeDataKey::from(a);
    let b = LargeDataKey::from(b);
    a.cmp(&b)
});

Смотри также:

• slice :: sort_by_key имеет больше ограничений, чем slice :: sort_by

Answer 2

Ошибка компилятора ясно указывает на то, что здесь есть два времени жизни:

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))

Я не нашел способа избавиться от этого несоответствия по времени жизни при сохранении вашего дизайна.

Если ваша цель - извлечь сортируемый ключ из элементов в срезе, вот подход, который работает на основе реализации Ord для LargeData:

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);
}