How do I find the minimum element in a vector


#1

Okay, the question is a little more complicated because it has some constraints. So here they are:

  1. The vector is immutable
  2. The elements don’t implement copy (so you need to take ownership of them to return the minimum)
  3. The elements are comparable with a f32

Here’s what I’ve tried:

  1. std::vec::Vec implements sort_by which is good enough because my vecs are usually small. I can just use partial_cmp to compare f32s. But unfortunately due to (1), the vector is immutable and sort_by is in-place. So this won’t work
  2. There’s vec.iter().min_by_key(|x| x.my_f32) but f32 doesn’t implement Ord (it implements PartialOrd) so Rust complains about a type mismatch.

So I’ve come up with this monstrosity, which works but seems like a huge amount of code to do something simple:

struct MyStruct {my_f32: f32}

// Takes ownership of my_vec and returns its smallest element (or None if the list is empty).
fn find_min(my_vec: Vec<MyStruct>) -> Option<MyStruct> {
    let mut min: Option<MyStruct> = None;
    for element in my_vec {
        min = match min {
            None => {
                Some(element)
            },
            Some(min) => {
                if element.my_f32 < min.my_f32 {
                    Some(element)
                } else {
                    Some(min)
                }
            }
        }
    }
    min
}

There has to be something I’m stupidly overlooking. Does anyone have an idea about how this can be simplified?


#2

The function you’ve written takes ownership of the vector, so immutability or not is irrelevant: you could change it to mut my_vec: Vec<MyStruct> and the callers wouldn’t know the difference.

However, the O(n log n) cost of a full sort is not great. An alternative to what you’ve written is a fold:

my_vec.into_iter().fold(None, |min, x| match min {
    None => Some(x),
    Some(y) => Some(if x.my_f32 < y.my_f32 { x } else { y }),
})