Rust Lifetime Problems when sorting an array by key

Question

I encounter some problems, when implementing an argmax function. Here is an MVCE (link to v1 playground):

fn main() {
    let c = [4,5,6,1];
    let min = argmin(&c);
    println!("{}", min);
}

fn argmin(arr: &[i32]) -> usize {
        arr.iter()
            .enumerate()
            .min_by_key(|(_, v)| v)
            .map(|(idx, _)| idx)
            .unwrap()
}

Which results in some lifetime errors:

error: lifetime may not live long enough
  --> src/main.rs:10:50
   |
10 |             .min_by_key(|(_, v): &(usize, &i32)| v)
   |                                  -             - ^ returning this value requires that `'1` must outlive `'2`
   |                                  |             |
   |                                  |             return type of closure is &'2 &i32
   |                                  let's call the lifetime of this reference `'1`

error: aborting due to previous error

Granted. There is no guarantee that the a reference to the minimum value of the vector outlives the (reference to the) vector from which it's coming. This led me to the following adaptations (link to v2 playground):

fn main() {
    let c = [4,5,6,1];
    let min = argmin(&c);
    println!("{}", min);
}

fn argmin<'a>(arr: &'a [i32]) -> usize {
        arr.iter()
            .enumerate()
            .min_by_key(|(_, v): &'a (usize, &i32)| v)
            .map(|(idx, _)| idx)
            .unwrap()
}

I would think now, that Rust can figure out that both c and its minimum have the same lifetime with the information from the argmin's signature. But what I receive is another compiler error:

error[E0308]: mismatched types
  --> src/main.rs:10:34
   |
10 |             .min_by_key(|(_, v): &'a (usize, &i32)| v)
   |                                  ^^^^^^^^^^^^^^^^^ lifetime mismatch
   |
   = note: expected reference `&(usize, &i32)`
              found reference `&'a (usize, &i32)`
note: the anonymous lifetime #1 defined on the body at 10:25...
  --> src/main.rs:10:25
   |
10 |             .min_by_key(|(_, v): &'a (usize, &i32)| v)
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...does not necessarily outlive the lifetime `'a` as defined on the function body at 7:11
  --> src/main.rs:7:11
   |
7  | fn argmin<'a>(arr: &'a [i32]) -> usize {
   |           ^^

error[E0308]: mismatched types
  --> src/main.rs:10:34
   |
10 |             .min_by_key(|(_, v): &'a (usize, &i32)| v)
   |                                  ^^^^^^^^^^^^^^^^^ lifetime mismatch
   |
   = note: expected reference `&(usize, &i32)`
              found reference `&'a (usize, &i32)`
note: the lifetime `'a` as defined on the function body at 7:11...
  --> src/main.rs:7:11
   |
7  | fn argmin<'a>(arr: &'a [i32]) -> usize {
   |           ^^
note: ...does not necessarily outlive the anonymous lifetime #1 defined on the body at 10:25
  --> src/main.rs:10:25
   |
10 |             .min_by_key(|(_, v): &'a (usize, &i32)| v)
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

What is happening here? To me it seems like the lifetime in the function signature can't be matched to the one in min_by_key. How can we fix this in a proper way, using lifetimes? Can we even do it?

P.S.: I know that this can easily be fixed by just using a clone (.min_by_key(|(_, v)| v.clone())) in line 10.

you can just easily remove the lifetimes and let it handle them. — Netwave
@Netwave thanks for the comment. That is what I first tried, have a look at the second code block. — pythonic833
Interestingly, the even simpler fn argmin(arr: &[i32]) { let _min = arr.iter().min_by_key(|v| v).unwrap(); } also fails to build (playground) with the same lifetime error as the first snippet. I'm curious about the actual problem with that code - it's not like the closure returns the reference to a local value, it returns the reference received in argument, and that reference "obviously" lives long enough. Replacing min_by_key(|v| v) with just min() compiles. — user4815162342

Netwave Netwave · Accepted Answer · 2021-01-30T10:59:19

So, it is a bit tricky, but it is due because of a double reference. If I'm correct. Notice the double reference &(usize, &i32). So, in reality you are getting a &usize and a &&i32. For solving that, just match the outer reference in the closure:

fn argmin(arr: &[i32]) -> usize {
        arr.iter()
            .enumerate()
            .min_by_key(|&(_, v): &(usize, &i32)| v)
            .map(|(idx, _)| idx)
            .unwrap()
}

Playground

Rust Lifetime Problems when sorting an array by key

1 Answers