Lifetime problem with "sort_unstable_by_key"

Hello!
I want to sort structs inside a vector by struct's field:

struct Struct {
    f: String
}

fn main() {
    let mut vec = vec![Struct { f: "a".to_string() }, Struct { f: "b".to_string() }];
    vec.sort_unstable_by_key(|s| &s.f);
}

This code results in compiler error:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
 --> src/main.rs:9:34
  |
9 |     vec.sort_unstable_by_key(|s| &s.f);
  |                                  ^^^^
  |
note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the body at 9:30...
 --> src/main.rs:9:30
  |
9 |     vec.sort_unstable_by_key(|s| &s.f);
  |                              ^^^^^^^^
note: ...so that reference does not outlive borrowed content
 --> src/main.rs:9:34
  |
9 |     vec.sort_unstable_by_key(|s| &s.f);
  |                                  ^^^^
note: but, the lifetime must be valid for the method call at 9:5...
 --> src/main.rs:9:5
  |
9 |     vec.sort_unstable_by_key(|s| &s.f);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that a type/lifetime parameter is in scope here
 --> src/main.rs:9:5
  |
9 |     vec.sort_unstable_by_key(|s| &s.f);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Could you please help?

So I guess the problem here is that the sorting function will move the elements of the vector (otherwise it wouldn't be much of a sorting function :D). But that means that you cannot take references to members of the struct because they will be invalidated by the move. It works if you clone the string instead of referencing it:

struct Struct {
    f: String
}

fn main() {
    let mut vec = vec![Struct { f: "a".to_string() }, Struct { f: "b".to_string() }];
    vec.sort_unstable_by_key(|s| s.f.clone());
}

That's not optimal of course. A better solution would probably be to use sort_unstable_by so you don't need to clone any strings:

struct Struct {
    f: String
}

fn main() {
    let mut vec = vec![Struct { f: "a".to_string() }, Struct { f: "b".to_string() }];
    vec.sort_unstable_by(|e1, e2| e1.f.cmp(&e2.f));
}
1 Like

@dthul is on the money in terms of the way to avoid the issue, but conceptually, there's no issue in allowing references to be compared by the sorting routine - those references are dropped after it determines the order between any 2 elements it's looking at.

This is explored a bit in this github issue and this forum thread.

4 Likes

Ah interesting. I initially thought (without checking the code) that sort_unstable_by_key might hold on to the computed key when moving elements, in order not to recompute the keys for every comparison (makes sense if key computation is expensive for example). Seems the issue is more arcane in nature :smiley: