How to set lifetime of slice::sort_by_key to make it support reference value?

help
1

Hi , I try to sort a slice by a string field, Is it possible to use sort by key without memery allocating of String?

fn main() {
    let mut values: Vec<V1> = vec![
        // some test values
    ];

    // this work
    values.sort_by(|left, right| left.s.cmp(&right.s));

    // compile error: lifetime may not live long enough
    values.sort_by_key(|v| &v.s);

    // compile error: lifetime may not live long enough
    my_sort_by_key(&mut values, |v| &v.s);

    println!("{values:?}")
}

fn my_sort_by_key<K, T, F>(vec: &mut Vec<T>, mut f: F)
where
    K: Ord,
    for<'a> F: FnMut(&'a T) -> K + 'a,
{
    vec.sort_by(|left, right| f(left).cmp(&f(right)))
}

#[derive(Debug)]
struct V1 {
    n: i32,
    s: String,
}

It works if I use &K instead of K, but still can not support tuple with &str in it.

fn main() {
    let mut values: Vec<V1> = vec![
        // some test values
    ];

    // this work
    my_sort_by_key(&mut values, |v| &v.s);

    // this doesn't work
    my_sort_by_key(&mut values, |v| (&v.s, v.n));

    println!("{values:?}")
}

fn my_sort_by_key<K, T, F>(vec: &mut Vec<T>, mut f: F)
where
    K: Ord,
    // change return value from K + 'a to &'a K 
    for<'a> F: FnMut(&'a T) -> &'a K,
{
    vec.sort_by(|left, right| f(left).cmp(&f(right)))
}

#[derive(Debug)]
struct V1 {
    n: i32,
    s: String,
}
2

You can’t use sort_by_key() in this way and must use sort_by() instead.

The fundamental problem is that sort_by_key or my_sort_by_key is mutating the vector, which is incompatible with borrowing keys of a single type K from it. You might be able to do this with a GAT trait instead of FnMut but it won't be easy to use.

3

There is no way to make it work. It doesn't allow this by design.

This function moves the items, so it invalidates the references you give it.

4

You can, at least, use sort_by_cached_key instead so that the allocation is once per element instead of once per comparison.

(To make a by_key version work with lifetimes like that it'd need GATs and a for<'a> bound, which is why the older-than-GATs sort_by_key doesn't do that.)