257. VecDeque::rotate_left — Where the Ring Buffer Finally Pays Rent

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.