如何在两个 Vec 之间来回移动元素

Question

我正在编写一个排序函数，它接受

Vec

输入，并输出排序后的

Vec

。部分处理需要在原始

Vec

和辅助

Vec

之间来回移动项目。实现这一目标的有效方法是什么？我目前的想法是使用这样的 Option+Box:

fn sort<T>(mut v: Vec<Option<Box<T>>>) -> Vec<Option<Box<T>>> {
    let mut aux: Vec<Option<Box<T>>> = vec![None; v.len()];
    ...
}

然后我可以和

std::mem::swap

交换物品。我还可以在函数内创建 Option：

fn sort<T>(mut v: Vec<T>) -> Vec<T> {
    let mut wrapped: Vec<Option<Box<T>>> = v.into_iter().map(|x| Some(Box::new(x))).collect();
    let mut aux: Vec<Option<Box<T>>> = vec![None; v.len()];
    ...
    // unwrap at the end
}

排序将始终在单个循环中交换

Vec

之间的所有项目，因此我不必担心在单个

None

中混合

Some

和

Vec

。我使用

Box<T>

而不是

Option<T>

的原因是

T

可能是一个大物体，我的理解是

Option<T>

的大小至少与

T

一样大。

我是 Rust 新手，所以我想知道这是否是一个解决空指针问题的天真的尝试。

Answer 1

我认为普通引用就足够了，正如 @Chayim Friedman 指出的那样，

Box

每次创建都需要额外的堆栈分配，而且据我所知，引用只是指针，可以节省时间和空间

use std::fmt::Debug;

fn my_sort<T: PartialOrd + Clone + Debug>(vec: Vec<T>) -> Vec<T> {
    // let mut wrapped = vec.iter().map(Option::Some).collect::<Vec<_>>();
    let mut buf = vec.iter().collect::<Vec<_>>();
    let mut aux: Vec<Option<&T>> = vec![None; vec.len()];

    quick(&mut buf, &mut aux, 0, vec.len());

    buf
        .into_iter()
        .cloned()
        .collect()
}

fn quick<'a, T: PartialOrd + Clone + Debug + 'a>(buf: &mut Vec<&'a T>, aux: &mut Vec<Option<&'a T>>, start: usize, end: usize) {
    if end - start <=0 { return; }
    let pivot = buf[start];

    // println!("buf  : {:?}", buf);
    // println!("aux  : {:?}", aux);
    // println!("start: {:?}", start);
    // println!("end  : {:?}", end);
    // println!("pivot: {:?}", pivot);

    let mut less = 0;
    let mut more = 0;
    for i in (start + 1)..end{
        if *buf[i] < *pivot {
            aux[start + less] = Some(buf[i]);
            less += 1;
        } else{
            aux[end - 1 - more] = Some(buf[i]);
            more += 1;
        }
    }
    aux[start + less] = Some(pivot);
    for i in start..end{
        buf[i] = aux[i].unwrap();
    }

    // println!("less : {:?}", less);
    // println!("more : {:?}", more);
    // println!("{:?}", buf);
    // println!("{:?}", aux);
    
    // let mut b = String::new();
    // std::io::stdin().read_line(&mut b).unwrap();

    quick(buf, aux, start, start + less);
    quick(buf, aux, end - more, end);
}

fn main () {
    let v = vec![3,5,2,6,8,4,45,18,45,7,989,3,2,1,8,487,78,7452,3,0];
    let v = my_sort(v);
    println!("{:?}", v);

    let mut sorted_v = v.clone();
    sorted_v.sort();
    assert_eq!(v,sorted_v);
}