5

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?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
lovasoa
  • 6,419
  • 1
  • 35
  • 45
  • 1
    `MaybeUninit::uninit().assume_init()` is _never_ a correct thing to do. You're right not to be happy about this solution. – mcarton Jul 30 '20 at 10:06
  • If your `T` implements `Drop`, this code will call `drop()` for uninitialized memory. – Sven Marnach Jul 30 '20 at 10:10
  • 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. – lovasoa Jul 30 '20 at 10:12
  • But why isn't the array droped? if the method takes ownership of it right? – Netwave Jul 30 '20 at 10:17
  • 2
    @lovasoa “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`. – mcarton Jul 30 '20 at 10:24
  • @Netwave 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. – Sven Marnach Jul 30 '20 at 10:25
  • @SvenMarnach aha, I overread and I was thinking the problem was something else. Thanks! – Netwave Jul 30 '20 at 10:43

2 Answers2

11

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:

Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
-1
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}
    }
}
Adam Butler
  • 1