Why can't I use a key function that returns a reference when sorting a vector with sort_by_key?
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.
As @Shepmaster explained you cannot have a sort_by_key
function handling generic associated lifetimes for the return type of the key
function, but here is a variant for a key function always returning a reference:
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)));
}
You could also write down the lifetime requirements for the key function:
for<'a> F: Fn(&'a T) -> &'a K,
See example on playground.