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

Question

我正在尝试Vec<String>使用键函数对其进行排序,该函数返回对向量中字符串的引用.一个人为的例子是使用身份函数作为关键函数(当然这是无用的,但它是重现我的问题的最小例子):

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

现在items: Vec<String>,我希望能够做到

items.sort_by_key(key);

这会出现以下错误:

error[E0271]: type mismatch resolving `for<'r> <fn(&std::string::String) -> &std::string::String {main::key} as std::ops::FnOnce<(&'r std::string::String,)>>::Output == _`
  --> src/main.rs:19:11
   |
19 |     items.sort_by_key(key);
   |           ^^^^^^^^^^^ expected bound lifetime parameter, found concrete lifetime
   |
   = note: concrete lifetime that was found is lifetime '_#16r

我不明白为什么我会收到这个错误,所以我试着追踪这个错误.我首先实现了我自己的版本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/main.rs:22:29
   |
22 |     sort_by_key(&mut items, key);
   |                             ^^^ expected concrete lifetime, found bound lifetime parameter
   |
   = note: expected type `fn(&std::string::String) -> _`
              found type `fn(&std::string::String) -> &std::string::String {main::key}`

我可以通过修改密钥类型&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()Playground上函数的三个版本.

为什么我会收到这些错误？有没有办法解决这些问题,同时保持密钥类型K完全通用？

Answer 1

为什么我会收到这些错误？有没有办法解决它们？

原因和修复是一回事:Rust目前的表达力不足以代表你想要的东西.所需的功能称为通用关联类型(GAT) ; 以前称为相关类型构造函数(ATC)或更高级类型(HKT).

从相关问题:

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

我不知道签名是否sort_by_key能够在实施时无缝移动到GAT.

现在,你必须使用"长"形式:

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