我如何改变VecDeque？

Question

我可以像这样简单地改变常规向量:

extern crate rand;
use rand::Rng;

fn shuffle(coll: &mut Vec<i32>) {
    rand::thread_rng().shuffle(coll);
}

问题是,我的代码现在需要使用std::collections::VecDeque替代,这导致此代码无法编译.

解决这个问题的最简单方法是什么？

Answer 1

不幸的是,该rand::Rng::shuffle方法被定义为随机切片.由于其自身的复杂性约束,VecDeque无法将其元素存储在切片中,因此shuffle永远不能直接调用VecDeque.

算法values参数的真正要求shuffle是有限序列长度,O(1)元素访问,以及交换元素的能力,所有这些都VecDeque满足.如果有一个特征包含这些特征会很好,所以这values可能是通用的,但没有一个.

使用当前库,您有两种选择:

• 使用Vec::from(deque)复制VecDeque到一个临时Vec,洗牌的向量,并返回内容回VecDeque.操作的这种复杂性将保持为O(n),但是它将需要临时向量的潜在大且昂贵的堆分配.

• 对VecDeque自己实施洗牌.在费雪耶茨洗牌的使用rand::Rng是很好理解的,易于实现,在其现代形式把它归结为大约只有5行代码.虽然理论上标准库可以切换到不同的混洗算法,但实际上不太可能发生.

第二个选项的通用形式,使用特征来表达len-and-swap要求,并获取代码rand::Rng::shuffle,可能如下所示:

extern crate rand;

use std::collections::VecDeque;

// Real requirement for shuffle
trait LenAndSwap {
    fn len(&self) -> usize;
    fn swap(&mut self, i: usize, j: usize);
}

// An exact copy of rand::Rng::shuffle, with the signature modified to
// accept any type that implements LenAndSwap
fn shuffle<T, R>(values: &mut T, mut rng: R)
    where T: LenAndSwap,
          R: rand::Rng {
    let mut i = values.len();
    while i >= 2 {
        // invariant: elements with index >= i have been locked in place.
        i -= 1;
        // lock element i in place.
        values.swap(i, rng.gen_range(0, i + 1));
    }
}

// VecDeque trivially fulfills the LenAndSwap requirement, but
// we have to spell it out.
impl<T> LenAndSwap for VecDeque<T> {
    fn len(&self) -> usize {
        self.len()
    }
    fn swap(&mut self, i: usize, j: usize) {
        self.swap(i, j)
    }
}

fn main() {
    let mut v: VecDeque<u64> = [1, 2, 3, 4].iter().cloned().collect();
    shuffle(&mut v, rand::thread_rng());
    println!("{:?}", v);
}