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.)

5

Is it possible to make my_sort_by_key work as I excepted? Could you kindly provide an example please? Thanks in advance.

6

This can probably be simplified.

pub trait SortKey<'a> : Ord {}

impl<'a, T: Ord + 'a> SortKey<'a> for T {}

pub trait GetSortKey<'a, T> {
    type Key: SortKey<'a>;
    fn get_sort_key(&mut self, val: &'a T) -> Self::Key;
}

impl<'a, T: 'a, K: 'a + Ord, F: 'a> GetSortKey<'a, T> for F where F: FnMut(&'a T) -> K {
    type Key = K;
    fn get_sort_key(&mut self, val: &'a T) -> Self::Key {
        self(val)
    }

}

pub fn sort_by_key<T, F>(s: &mut [T], mut f: F) where for<'a> F: GetSortKey<'a, T> {
    s.sort_by(|x, y| {
        let a = f.get_sort_key(x);
        let b = f.get_sort_key(y);
        a.cmp(&b)
    })
}

fn make_key<'a>(elem: &'a (i32, i32)) -> (&'a i32, &'a i32) {
    (&elem.0, &elem.1)
}

pub fn main() {
    let mut x = [(3, 4), (1, 2)];
    
    sort_by_key(&mut x, make_key);
    
    println!("{:?}", x);
}
1 Like
7

See also slice::sort_by_key has more restrictions than slice::sort_by · Issue #34162 · rust-lang/rust · GitHub

2 Likes
8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.