Vecdeque

slice::rotate_left touches every element, every time. The same call on a VecDeque moves at most half of them — often far fewer.

Rotation on a slice is O(len)

Bite 133 covered slice::rotate_left: in-place, no allocation, but every rotation is O(len) — all elements physically move through memory.

This morning’s bite 256 showed the cost of VecDeque’s ring buffer: no single slice to hand out. Rotation is where that layout pays you back.

The deque version

VecDeque has its own rotate_left / rotate_right, and the ring buffer turns rotation into pointer arithmetic plus a short move:

1
2
3
4
5
6
7
8
9

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = (0..10).collect();

buf.rotate_left(3);
assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);

buf.rotate_right(3);
assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

It’s the loop you’d write by hand — pop one end, push the other — but done as a bulk move:

1
2
3
4
5
6

// rotate_left(3), spelled out:
for _ in 0..3 {
    let x = buf.pop_front().unwrap();
    buf.push_back(x);
}
assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);

Because elements may wrap around the allocation’s end, “moving” the front to the back mostly means shifting the head index. The documented bound is O(min(mid, len − mid)) time and no extra space — rotate_left(3) on a million-element deque moves 3 elements, not a million. The same call on a slice moves all of them.

Where it shines: round-robin

A scheduler that cycles through tasks is one rotate_left(1) per turn — O(1):

1
2
3
4
5

let mut tasks: VecDeque<&str> =
    ["fetch", "parse", "render"].into();

tasks.rotate_left(1);
assert_eq!(tasks, ["parse", "render", "fetch"]);

Both methods panic if mid > len(), so a full-cycle rotate_left(len) is legal (and a no-op) but len + 1 is not — use k % len if k can exceed the length.

If you’re rotating a Vec in a hot loop, that’s the signal to switch containers: VecDeque::from(vec) is O(1), and every rotation after that is the cheap kind.

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].

You insert a placeholder, then index back to fix it up. Two lookups, two bounds checks, one wobble. Vec::insert_mut — stable in 1.95 — hands you the &mut T directly.

The classic dance:

1
2
3
4

let mut v = vec![1, 2, 4, 5];
v.insert(2, 0);
v[2] = 3; // recompute the index, second bounds check
assert_eq!(v, [1, 2, 3, 4, 5]);

insert_mut returns the slot:

1
2
3
4

let mut v = vec![1, 2, 4, 5];
let slot = v.insert_mut(2, 0);
*slot = 3;
assert_eq!(v, [1, 2, 3, 4, 5]);

This shines when the value is built in pieces — push a default, then fill it in based on where it landed:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#[derive(Default, Debug, PartialEq)]
struct Job { id: u32, label: String }

let mut jobs: Vec<Job> = vec![Job { id: 1, label: "build".into() }];
let j = jobs.insert_mut(0, Job::default());
j.id = 0;
j.label = "setup".into();

assert_eq!(jobs[0], Job { id: 0, label: String::from("setup") });
assert_eq!(jobs[1].label, "build");

Rust 1.95 grew the whole _mut family alongside Vec::push_mut: Vec::insert_mut, VecDeque::push_front_mut, VecDeque::push_back_mut, VecDeque::insert_mut, LinkedList::push_front_mut, and LinkedList::push_back_mut. Same idea everywhere — the place-it method now returns a mutable reference to the slot it just placed.

1
2
3
4
5
6

use std::collections::VecDeque;

let mut q: VecDeque<i32> = VecDeque::from([2, 3]);
let head = q.push_front_mut(0);
*head += 1; // now 1
assert_eq!(q, VecDeque::from([1, 2, 3]));

Quietly useful, no churn — just fewer indices floating around.

Vec::pop_if got a deque-shaped sibling. As of Rust 1.93, VecDeque has pop_front_if and pop_back_if — conditional pops on either end without the peek-then-pop dance.

The problem

You want to remove an element from a VecDeque only when it matches a predicate. Before 1.93, you’d peek, match, then pop:

1
2
3
4
5
6
7

use std::collections::VecDeque;

let mut queue: VecDeque<i32> = VecDeque::from([1, 2, 3, 4]);

if queue.front().is_some_and(|&x| x == 1) {
    queue.pop_front();
}

Two lookups, two branches, one opportunity to desynchronize the check from the pop if you refactor the predicate later.

The fix

pop_front_if takes a closure, checks the front element against it, and pops it only if it matches. pop_back_if does the same on the other end.

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

use std::collections::VecDeque;

let mut queue: VecDeque<i32> = VecDeque::from([1, 2, 3, 4]);

let popped = queue.pop_front_if(|x| *x == 1);
assert_eq!(popped, Some(1));
assert_eq!(queue, VecDeque::from([2, 3, 4]));

// Predicate doesn't match — nothing is popped.
let not_popped = queue.pop_front_if(|x| *x > 100);
assert_eq!(not_popped, None);
assert_eq!(queue, VecDeque::from([2, 3, 4]));

The return type is Option<T>: Some(value) if the predicate matched and the element was removed, None otherwise (including when the deque is empty).

One subtle detail worth noting — the closure receives &mut T, not &T. That means |&x| won’t type-check; use |x| *x == ... or destructure with |&mut x|. The extra flexibility lets you mutate the element in-place before deciding to pop it.

Draining a prefix

The pattern clicks when you pair it with a while let loop. Drain everything at the front that matches a condition, stop the moment it doesn’t:

1
2
3
4
5
6
7
8

use std::collections::VecDeque;

let mut events: VecDeque<i32> = VecDeque::from([1, 2, 3, 10, 11, 12]);

// Drain the "small" prefix only.
while let Some(_) = events.pop_front_if(|x| *x < 10) {}

assert_eq!(events, VecDeque::from([10, 11, 12]));

No index tracking, no split_off, no collecting into a new deque.

Why both ends?

VecDeque is a double-ended ring buffer, so it’s natural to support the same idiom on both sides. Processing a priority queue from the back, trimming expired entries from the front, popping a sentinel only when it’s still there — all one method call each.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

use std::collections::VecDeque;

let mut log: VecDeque<&str> = VecDeque::from(["START", "a", "b", "c", "END"]);

let end = log.pop_back_if(|s| *s == "END");
let start = log.pop_front_if(|s| *s == "START");

assert_eq!(start, Some("START"));
assert_eq!(end, Some("END"));
assert_eq!(log, VecDeque::from(["a", "b", "c"]));

When to reach for it

Whenever the shape of your code is “peek, compare, pop.” That’s the tell. pop_front_if / pop_back_if collapse three steps into one atomic operation, and the Option<T> return makes it composable with while let, ?, and the rest of the Option toolbox.

Stabilized in Rust 1.93 — if your MSRV is recent enough, this is a free readability win.