How to sort or reverse VecDeque without `make_contiguous()`?

Question

I'd like to sort or reverse VecDeque. In Rust 1.48.0 or later, you can use make_contiguous() to mutably access the underlying slice to perform such operations:

v.make_contiguous().reverse(); //reverse
v.make_contiguous().sort(); //sort

However, I have to use Rust 1.42.0 in competitive programming. unsafe is allowed. Nightly Rust is not allowed.

I don't want to first collect VecDeque into Vec, then reverse or sort the result and finally collect Vec back to VecDeque, which seems unnecessarily very slow and verbose.

Is there any more elegant way?

Answer 1

Combine as_mut_slices and rotate_right.

fn sort_vecdeque<T: Ord>(x: &mut VecDeque<T>) {
    x.rotate_right(x.as_slices().1.len());
    assert!(x.as_slices().1.is_empty());
    x.as_mut_slices().0.sort();
}

This works because of how VecDeque is implemented: It's a single memory allocation with holes either at the end and start (if head > tail), or in the middle (if head < tail).

• If the holes are at the start and end, the elements are already contiguous.
• If the hole is in the middle, the front of the deque is at the end of the allocation, and the back of the deque is at the beginning of the allocation. rotate_right "pops the last k items and pushes them to the front.", i.e. it removes the elements at the start of the allocation and adds them to the elements at the back of the allocation, so the deque will be contiguous.
  (The way I read the docs, there's not really a guarantee that it will always be that way, which is why I like having the assert there.)

Lastly, if the deque is contiguous, as_slice (and its mut friend) will return two slices, but the second one will be empty, all elements are in the first.

Also, using SO for a coding competition might be considered cheating.