Ehsan's Blog

Continuing from Rust standard library study series, it’s time for VecDeque<T>. Because of its similarity to Vec, there isn’t much to say.

A double-ended queue implemented with a growable ring buffer.
The “default” usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from the queue. extend and append push onto the back in this manner, and iterating over VecDeque goes front to back.

Rust std doc

• Similar to Vec, VecDeque has amortized insert to both ends of the container, but unlike Vec, it has amortized removal from both ends. (Recalling from Vec study, removal is strictly with no shrink factor involved)
• Similar to Vec, indexing is

Similar to Vec<T> study, here’s the stripped down definition of VecDeque<T>

struct VecDeque<T> {
    // tail and head are pointers into the buffer. Tail always points
    // to the first element that could be read, Head always points
    // to where data should be written.
    // If tail == head the buffer is empty. The length of the ringbuffer
    // is defined as the distance between the two.
    tail: usize,
    head: usize,
    buf: RawVec<T>,
}

// Default Global allocator
struct RawVec<T, A: Alloc = Global> {
    ptr: Unique<T>,
    cap: usize,
    a: A,
}

#[repr(transparent)]
struct Unique<T: ?Sized> {
    pointer: *const T,
    _marker: PhantomData<T>,
}

The same Vec methods, such as with_capacity (note that ring buffer always leaves one space empty), truncate, shrink_to etc. exist and follow the same observations as in Vec study. The notable methods are

• push_back and pop_back which involve moving the head pointer and push_front and pop_front which involve moving the tail pointer.
• retain which acts as the filter method.
• resize_with with a generator: impl FnMut() -> T
• as_slices (and the mut one) which contains, in order the content of the VecDeque.

That’s it for now!