为什么在使用 sort_by_key 对向量进行排序时不能使用返回引用的键函数？

Question

我正在尝试使用返回对向量中字符串的引用的键函数对 Vec 进行排序。一个人为的示例是使用恒等函数作为关键函数（这当然是无用的，但它是重现我的问题的最小示例）：

fn key(x: &String) -> &String {
    x
}

fn example(items: Vec<String>) {
    items.sort_by_key(key);
}

这给出了以下错误：

error[E0308]: mismatched types
   --> src/lib.rs:6:11
    |
6   |     items.sort_by_key(key);
    |           ^^^^^^^^^^^ lifetime mismatch
    |
    = note: expected associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
               found associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
    = note: the required lifetime does not necessarily outlive the empty lifetime
note: the lifetime requirement is introduced here

我不明白为什么会出现此错误，所以我尝试了来追踪这一点。我首先实现了我自己的 sort_by_key() 版本：

fn sort_by_key<T, K: Ord>(a: &mut [T], key: fn(&T) -> K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

当尝试调用此函数时，我得到了看起来像“相反”的错误：

error[E0308]: mismatched types
 --> src/lib.rs:6:29
  |
6 |     sort_by_key(&mut items, key);
  |                             ^^^ one type is more general than the other
  |
  = note: expected fn pointer `for<'r> fn(&'r String) -> &String`
             found fn pointer `for<'r> fn(&'r String) -> &'r String`

我可以通过将键类型固定为 &T 而不是使用泛型参数 K，或者使用 &K 而不是 K 作为返回类型关键功能：

fn sort_by_key_v2<T: Ord>(a: &mut [T], key: fn(&T) -> &T) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

fn sort_by_key_v3<T, K: Ord>(a: &mut [T], key: fn(&T) -> &K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

我也尝试添加生命周期注释，但是只是转移了错误而没有解决它。

这是 sort_by_key() 函数的三个版本游乐场。

为什么我会收到这些错误？有什么方法可以修复它们，同时保持密钥类型 K 完全通用吗？

Answer 1

现在，您必须使用“长”形式：

v.sort_by(|x, y| key(x).cmp(&key(y)));

为什么我会收到这些错误？有什么办法可以解决吗？

原因和修复是一回事：Rust 目前的表现力不足以代表您想要的东西。所需的功能称为通用关联类型（GAT）；以前称为关联类型构造函数 (ATC) 或更高种类的类型 (HKT)。

来自相关问题：

为了使 sort_by_key 调用正常，输入引用的生命周期 [...] 需要合并到 B 中以使返回类型 &'a str，但 B 是类型参数。

我不知道 sort_by_key 的签名在实施后是否能够无缝转移到 GAT。在这一点上似乎值得怀疑，因为 Fn* 特征本身可能需要更改。

---

在控制所有类型签名的类似情况下，您可以要求返回引用：

use std::cmp::Ordering;

struct User {
    name: String,
}

fn compare_keys<T, R>(a: T, b: T, key: impl Fn(&T) -> &R) -> Ordering
where
    for<'a> &'a R: Ord,
{
    let ak = key(&a);
    let bk = key(&b);
    ak.cmp(&bk)
}

fn main() {
    let alice = User {
        name: String::from("alice"),
    };
    let bob = User {
        name: String::from("bob"),
    };

    compare_keys(alice, bob, |u| &u.name);
}

这是不理想的，因为现在您无法返回非引用，但在实现 GAT 之前根本没有完整的解决方案。您也许可以添加并行方法，例如 sort_by 和 sort_by_key，具体取决于您的情况。

Answer 2

正如 @Shepmaster 解释的，您不能使用 sort_by_key 函数来处理返回类型的通用关联生命周期key 函数，但这里是始终返回引用的键函数的变体：

fn sort_by_key_ref<T, F, K>(a: &mut [T], key: F) 
where
    F: Fn(&T) -> &K,
    K: ?Sized + Ord,
{
    a.sort_by(|x, y| key(x).cmp(key(y)));
}

您还可以写下键函数的生命周期要求：

    for<'a> F: Fn(&'a T) -> &'a K,

请参阅操场上的示例。

Answer 3

基于 Shepmaster 答案的最简洁的解决方法（IMO）是：

fn ref_key<T, K: Ord + ?Sized>(mut f: impl FnMut(&T) -> &K) -> impl FnMut(&T, &T) -> Ordering {
    move |a, b| f(a).cmp(f(b))
}

只需将 slice.sort_by_key(key) 转换为 slice.sort_by(ref_key(key)) 即可使用它。代码>.