256. VecDeque::make_contiguous — Turn a Wrapped Ring Buffer Into One Sortable Slice

VecDeque has no .sort(), and any API that wants &[T] rejects it. The catch is the ring buffer underneath — and one call flattens it.

Why a VecDeque isn’t a slice

A VecDeque is a ring buffer: pushes and pops at both ends are O(1) because the contents are allowed to wrap around the end of the allocation. After a few pops and pushes, the elements may sit in memory as two separate runs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = VecDeque::with_capacity(4);
buf.extend([3, 1, 4, 1]);
buf.pop_front();
buf.pop_front();
buf.push_back(5);
buf.push_back(9); // wraps around the buffer's end

let (front, back) = buf.as_slices();
assert_eq!(front, [4, 1]);
assert_eq!(back,  [5, 9]); // two pieces, not one

That’s why there’s no VecDeque::sort, and why you can’t pass one to anything expecting a &[T] — there is no single slice to hand out.

The built-in

make_contiguous rotates the elements back into one run and returns the whole thing as &mut [T]:

1
2
3

let slice = buf.make_contiguous();
slice.sort_unstable();
assert_eq!(slice, [1, 4, 5, 9]);

The deque itself is unchanged as a collection — same elements, same order you left them in — but now it’s backed by a single run:

1
2
3

let (front, back) = buf.as_slices();
assert_eq!(front, [1, 4, 5, 9]);
assert!(back.is_empty()); // one piece

Sorting was the classic motivation, but any slice-only API works after the call: windows, chunks, bite 247’s sort_unstable, or an FFI boundary that wants a pointer and a length.

What it costs

If the deque is already contiguous — which it always is fresh after new() or from(vec) — the call is free. Otherwise it moves elements within the existing buffer: no allocation, worst case O(n) moves. Do it once, then take slices as often as you like.

One nuance: binary_search and friends exist directly on VecDeque, so you don’t need this call just to search. Reach for make_contiguous when the API you’re feeding — or the mutation you want, like an in-place sort — demands one contiguous &mut [T].