在 Rust 中有条件地对 Vec 进行排序

Question

假设我想对 非克隆 项的 Vec 进行排序 - 但只是可能（这是我代码中问题的一个简单示例）。

我的尝试是这样的：

fn maybe_sort<T>(x: Vec<T>) -> Vec<T>
where
    T: std::cmp::Ord,
{
    // First, I need a copy of the vector - but only the vector, not the items inside
    let mut copied = x.iter().collect::<Vec<_>>();
    copied.sort();
    // In my actual code the line below depends on the sorted vec
    if rand::random() {
        return copied.into_iter().map(|x| *x).collect::<Vec<_>>();
    } else {
        return x;
    }
}

唉，借阅检查员不高兴。我对 Vec 中的每个项目都有一个共享引用，虽然我从来没有返回对同一项目的 2 个引用，但 Rust 无法分辨。

没有 unsafe 有没有办法做到这一点？（如果没有，使用 unsafe.

最干净的方法是什么

Answer 1

您可以 .enumerate() 保留其原始索引的值。您可以根据其值 T 对其进行排序，并决定是 return 排序后的版本，还是通过按原始索引排序来反转排序。

fn maybe_sort<T: Ord>(x: Vec<T>) -> Vec<T> {
    let mut items: Vec<_> = x.into_iter().enumerate().collect();
    items.sort_by(|(_, a), (_, b)| a.cmp(b));
    
    if rand::random() {
        // return items in current order
    }
    else {
        // undo the sort
        items.sort_by_key(|(index, _)| *index);
    }
    
    items.into_iter().map(|(_, value)| value).collect()
}

Answer 2

如果 T 实现了 Default，您可以使用单一排序而不使用 unsafe，像这样：

fn maybe_sort<T: Ord + Default> (mut x: Vec<T>) -> Vec<T> {
    let mut idx = (0..x.len()).collect::<Vec<_>>();
    idx.sort_by_key (|&i| &x[i]);
    if rand::random() {
        return x;
    } else {
        let mut r = Vec::new();
        r.resize_with (x.len(), Default::default);
        for (i, v) in idx.into_iter().zip (x.drain(..)) {
            r[i] = v;
        }
        return r;
    }
}

Playground

如果T没有实现Default，可以用MaybeUninit做同样的事情：

use std::mem::{self, MaybeUninit};

fn maybe_sort<T: Ord> (mut x: Vec<T>) -> Vec<T> {
    let mut idx = (0..x.len()).collect::<Vec<_>>();
    idx.sort_by_key (|&i| &x[i]);
    if rand::random() {
        return x;
    } else {
        let mut r = Vec::new();
        r.resize_with (x.len(), || unsafe { MaybeUninit::uninit().assume_init() });
        for (i, v) in idx.into_iter().zip (x.drain(..)) {
            r[i] = MaybeUninit::new (v);
        }
        return unsafe { mem::transmute::<_, Vec<T>> (r) };
    }
}

Playground

最后，这是一个安全的解决方案，它不需要 T 来实现 Default，但会分配一个额外的缓冲区（理论上有一种方法可以对索引进行重新排序，但我'我会把它作为练习留给 reader ☺):

fn maybe_sort<T: Ord> (mut x: Vec<T>) -> Vec<T> {
    let mut idx = (0..x.len()).collect::<Vec<_>>();
    idx.sort_by_key (|&i| &x[i]);
    if rand::random() {
        let mut rev = vec![0; x.len()];
        for (i, &j) in idx.iter().enumerate() {
            rev[j] = i;
        }
        for i in 0..x.len() {
            while rev[i] != i {
                let j = rev[i];
                x.swap (j, i);
                rev.swap (j, i);
            }
        }
    }
    x
}

Playground

在 Rust 中有条件地对 Vec 进行排序

Conditionally sort a Vec in Rust

rust

borrow-checker