Collection Adapters and Specialized Types

VecDeque<T>

VecDeque<T> (std::collections::VecDeque<T>) is a growable double-ended queue backed by a heap-allocated circular ring buffer, providing amortized $O(1)$ insertion and removal at both ends alongside $O(1)$ random access by logical index.

Internal Structure and 32-Byte Header

While Vec<T> always stores logical element 0 at physical offset 0 of its heap buffer (24-byte stack header: ptr, len, capacity), VecDeque<T> adds a head offset (32-byte stack header on 64-bit: ptr, capacity, head, len) so elements can be prepended or popped at the front by decrementing or incrementing head modulo capacity without shifting existing elements:

Stack (`VecDeque<T>`, 32 bytes)      Heap Ring Buffer (`capacity = 8`)
+----------------+                   +----+----+----+----+----+----+----+----+
| ptr      (8 B) +-----------------> | e2 | e3 | -- | -- | -- | -- | e0 | e1 |
| capacity = 8   |                   +----+----+----+----+----+----+----+----+
| head     = 6   |                    [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]
| len      = 4   |                          ▲                        ▲
+----------------+                      last elem               logical index 0

Constructing, Indexing, and Rotating a VecDeque<T>

Method Signature Time Complexity Behavior
VecDeque::new() const fn new() -> VecDeque<T> $O(1)$ (0 allocs) Creates an empty deque
VecDeque::with_capacity(n) fn with_capacity(n: usize) -> VecDeque<T> $O(1)$ alloc Pre-allocates ring buffer for at least n items
q[i] / q.get(i) fn get(&self, index: usize) -> Option<&T> $O(1)$ Maps logical index i to (head + i) % cap
q.rotate_left(k) / q.rotate_right(k) fn rotate_left(&mut self, n: usize) $O(\min(k, \text{len} - k))$ Rotates queue elements in place (often just adjusts head when full!)
q. binary_search(&x) fn binary_search(&self, x: &T) -> Result<usize, usize> $O(\log n)$ Searches a sorted VecDeque<T> directly across both ring slices 
use std::collections::VecDeque;

fn main() {
    let mut ring = VecDeque::from([10, 20, 30, 40]);

    // Indexing works by logical offset `0..ring.len()` regardless of wrap-around:
    ring.push_front(5);
    println!("Logical elements: {ring:?}");
    println!("ring[0] = {}, ring[2] = {}", ring[0], ring[2]);

    // Rotate 2 elements from the front to the back:
    ring.rotate_left(2);
    println!("After rotate_left(2): {ring:?}");
}

Logical elements: [5, 10, 20, 30, 40]
ring[0] = 5, ring[2] = 20
After rotate_left(2): [20, 30, 40, 5, 10]

I/O Trait Implementations on VecDeque<u8> (Read and Write)

A VecDeque<u8> implements both std::io::Read (consuming bytes from the front via pop_front / slice copy) and std::io::Write (appending bytes to the back via push_back / slice copy), making VecDeque<u8> an in-memory FIFO byte pipe out of the box:

use std::collections::VecDeque;
use std::io::{Read, Write};

fn main() {
    let mut pipe: VecDeque<u8> = VecDeque::new();

    // Write bytes to the back of the queue:
    pipe.write_all(b"HELLO WORLD").unwrap();

    // Read the first 5 bytes from the front of the queue:
    let mut header = [0_u8; 5];
    pipe.read_exact(&mut header).unwrap();

    println!("Read header:     {}", String::from_utf8_lossy(&header));
    println!("Remaining bytes: {}", pipe.len());
}

Read header:     HELLO
Remaining bytes: 6