为什么在使用 sort_by_key 对向量进行排序时不能使用返回引用的键函数? [英] Why can't I use a key function that returns a reference when sorting a vector with sort_by_key?
问题描述
我正在尝试使用返回对向量中字符串的引用的键函数对 Vec
进行排序.一个人为的例子是使用恒等函数作为关键函数(这当然没用,但它是重现我的问题的最小例子):
fn key(x: &String) ->&字符串{X}
现在给定items: Vec
,我希望能够做到
items.sort_by_key(key);
出现以下错误:
error[E0271]:类型不匹配解析`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);|^^^^^^^^^^^ 预期绑定生命周期参数,找到具体生命周期|= 注意:找到的具体生命周期是生命周期 '_#16r
我不明白为什么我会收到这个错误,所以我试图追踪这个错误.我首先实现了我自己的 sort_by_key()
版本:
fn sort_by_key(a: &mut [T], key: fn(&T) -> K) {a.sort_by(|x, y| key(x).cmp(&key(y)));}
当尝试调用这个函数时,我得到看起来像相反"的错误:
错误[E0308]:类型不匹配-->src/main.rs:22:29|22 |sort_by_key(&mut items, key);|^^^ 预期的具体生命周期,找到绑定的生命周期参数|= 注意:预期类型 `fn(&std::string::String) ->_`找到类型 `fn(&std::string::String) ->&std::string::String {main::key}`
我可以通过将键类型固定为 &T
而不是使用通用参数 K
或使用 &K
而不是 K
作为键函数的返回类型:
fn sort_by_key_v2(a: &mut [T], key: fn(&T) -> &T) {a.sort_by(|x, y| key(x).cmp(&key(y)));}fn sort_by_key_v3(a: &mut [T], key: fn(&T) -> &K) {a.sort_by(|x, y| key(x).cmp(&key(y)));}
我也尝试添加生命周期注释,但这只会改变错误而没有解决它.
为什么我会收到这些错误?有没有办法在保持密钥类型 K
完全通用的同时修复它们?
现在,你必须使用长"形式:
v.sort_by(|x, y| key(x).cmp(&key(y)));
<块引用>
为什么我会收到这些错误?有什么办法可以解决吗?
原因和修复是一回事:Rust 目前的表现力不足以代表您想要的东西.所需的功能称为通用关联类型 (GATs);以前称为关联类型构造函数 (ATC) 或更高级的类型 (HKT).
来自相关问题:
<块引用>为了使 sort_by_key
调用正常,需要将输入引用 [...] 的生命周期合并到 B
中以使其返回类型 &'a str
,但 B
是一个类型参数.
我不知道 sort_by_key
的签名在实施时是否能够无缝移动到 GAT.
在您控制所有类型签名的类似情况下,您可以要求返回引用:
使用 std::cmp::Ordering;结构用户{名称:字符串,}fn compare_keys<T,R>(a:T,b:T,key:impl Fn(&T)->&R)->订购在哪里对于<'a>&'a R:奥德,{让 ak = key(&a);让 bk = key(&b);ak.cmp(&bk)}fn 主(){让爱丽丝 = 用户 {名称:String::from("alice"),};让鲍勃 = 用户 {名称:String::from("bob"),};compare_keys(alice, bob, |u| &u.name);}
这是不理想的,因为现在您不能返回非引用,但在实施 GAT 之前根本没有完整的解决方案.根据您的情况,您可以添加诸如 sort_by
和 sort_by_key
之类的并行方法.
I'm trying to sort a Vec<String>
using a key function that returns references to the strings in the vector. A contrived example is to use the identity function as key function (which of course is useless, but it's the minimal example to reproduce my problem):
fn key(x: &String) -> &String {
x
}
Now given items: Vec<String>
, I'd like to be able to do
items.sort_by_key(key);
This gives the following error:
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
I don't understand why I get this error, so I tried to track this down. I first implemented my own version of 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)));
}
When trying to call this function, I get what looks like the "opposite" error:
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}`
I can make this code compile by fixing the key type to &T
instead of using the generic parameter K
, or by using &K
instead of K
as return type for the key function:
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)));
}
I also tried adding lifetime annotations, but that only shifted the error around without resolving it.
Here's the three versions of the sort_by_key()
function on the Playground.
Why am I getting these errors? Is there any way to fix them while keeping the key type K
completely generic?
For now, you have to use the "long" form:
v.sort_by(|x, y| key(x).cmp(&key(y)));
Why am I getting these errors? Is there any way to fix them?
The cause and fix are one-and-the same: Rust is simply not currently expressive enough to represent what you want. The feature needed is called generic associated types (GATs); previously known as associated type constructors (ATCs) or higher-kinded types (HKTs).
From the associated issue:
For the
sort_by_key
call to be okay, the lifetime of the input reference [...] needs to be incorporated intoB
to make the return type&'a str
, butB
is a type parameter.
I don't know if the signature for sort_by_key
will be able to be seamlessly moved to a GAT when they are implemented.
In similar cases where you control the signature of all the types, you can require that a reference be returned:
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);
}
This is non-ideal because now you cannot return a non-reference, but there's simply no complete solution until GATs are implemented. You may be able to add a parallel methods like sort_by
and sort_by_key
, depending on your case.
这篇关于为什么在使用 sort_by_key 对向量进行排序时不能使用返回引用的键函数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!