In stable rust, how to move the minimum value out of an array, dropping the other values?

Question

I have a fixed-size array [T; SIZE] of values of a type T that is ordered (it implements Ord, but not necessarily Clone or Default). I would like to extract the smallest value of the array and drop all the others.

In nightly rust, I can use array::IntoIter to achieve that, but if possible, I would like my code to compile on stable.

Currently, I'm using the following (playground):

// Don't call this function if T has a custom Drop implementation or invalid bit patterns 
unsafe fn get_min<T: Ord>(mut arr: [T; SIZE]) -> T {
    let (idx, _) = arr.iter().enumerate().min_by(|(_, x), (_, y)| x.cmp(y)).unwrap();
    unsafe { replace(&mut arr[idx],  MaybeUninit::uninit().assume_init()) }
}

Of course, I'm not very happy with that. Is there a solution that is safer, and maybe less verbose?

Rotation

MaybeUninit::uninit().assume_init() is never a correct thing to do. You're right not to be happy about this solution. – Abraxas

If your T implements Drop, this code will call drop() for uninitialized memory. – Jemimah

Yes, in the general case, it is undefined behavior. However, for values of T that don't have invalid bit patterns nor a custom Drop implementation, I think it's safe. – Rotation

But why isn't the array droped? if the method takes ownership of it right? – Remus

@Rotation “However, for values of T that don't have invalid bit patterns nor a custom Drop implementation, I think it's safe.” No it's not. It's UB. The documentation explicitly mentions that MaybeUninit::uninit().assume_init() is UB even for trivial all-bit-patterns-valid non-drop Copy types like i32. – Abraxas

@Remus It is dropped, and that's the problem. We replaced one of the elements with unitialized memory, so we can't drop the element anymore. – Jemimah

@SvenMarnach aha, I overread and I was thinking the problem was something else. Thanks! – Remus

Answer 1

In the 2021 edition of Rust (available in Rust 1.56 and up), the into_iter() method on an array returns an iterator over the owned items, so this becomes easy:

fn get_min<T: Ord>(arr: [T; SIZE]) -> T {
    arr.into_iter().min().unwrap()     // assuming SIZE > 0
}

In earlier versions of Rust, you can move the minimum to the beginning of the array, and then use a slice pattern to move the first element out of the array:

fn get_min<T: Ord>(mut arr: [T; SIZE]) -> T {
    for i in 1..SIZE {
        if arr[i] < arr[0] {
            arr.swap(0, i);
        }
    }
    let [min, ..] = arr;
    min
}

(Playground)

Related questions:

• How do I move values out of an array one at a time?

Jemimah

Answer 2

use itertools::Itertools;

fn remove_smallest(numbers: &[u32]) -> Vec<u32> {
    let mut numbers = numbers.to_vec();
    match numbers.iter().position_min() {
        None => numbers,
        Some(m) => {numbers.remove(m); numbers}
    }
}

Cryotherapy

This operates on a slice rather than a fixed-size array, it unnecessarily moves them to a heap-allocated vector, and it returns everything except for the minimum element. – Needlefish

oops, it seems I need to learn how to read again... lol – Cryotherapy