As of Rust 1.48, VecDeque
supports the make_contiguous()
method. That method doesn't allocate and has complexity of O(n), like shuffling itself. Therefore you can shuffle a VecDeque
by calling make_contiguous()
and then shuffling the returned slice:
use rand::prelude::*;
use std::collections::VecDeque;
pub fn shuffle<T>(v: &mut VecDeque<T>, rng: &mut impl Rng) {
v.make_contiguous().shuffle(rng);
}
Playground
Historical answer follows below.
Unfortunately, the rand::Rng::shuffle
method is defined to shuffle slices. Due to its own complexity constraints a VecDeque
cannot store its elements in a slice, so shuffle
can never be directly invoked on a VecDeque
.
The real requirement of the values
argument to shuffle
algorithm are finite sequence length, O(1) element access, and the ability to swap elements, all of which VecDeque
fulfills. It would be nice if there were a trait that incorporates these, so that values
could be generic on that, but there isn't one.
With the current library, you have two options:
Use Vec::from(deque)
to copy the VecDeque
into a temporary Vec
, shuffle the vector, and return the contents back to VecDeque
. The complexity of the operation will remain O(n), but it will require a potentially large and costly heap allocation of the temporary vector.
Implement the shuffle on VecDeque
yourself. The Fisher-Yates shuffle used by rand::Rng
is well understood and easy to implement. While in theory the standard library could switch to a different shuffle algorithm, that is not likely to happen in practice.
A generic form of the second option, using a trait to express the len-and-swap requirement, and taking the code of rand::Rng::shuffle
, could look like this:
use std::collections::VecDeque;
// Real requirement for shuffle
trait LenAndSwap {
fn len(&self) -> usize;
fn swap(&mut self, i: usize, j: usize);
}
// A copy of an earlier version of rand::Rng::shuffle, with the signature
// modified to accept any type that implements LenAndSwap
fn shuffle(values: &mut impl LenAndSwap, rng: &mut impl 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));
}
}
// 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].into_iter().collect();
shuffle(&mut v, &mut rand::thread_rng());
println!("{:?}", v);
}