Rust std study series: VecDeque

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

Adouble-endedqueueimplemented with agrowable ring buffer.
The “default” usage of this type as a queue is to use push_back toaddto the queue, and pop_front toremovefrom the queue. extend and append push onto the back in this manner, and iterating over VecDeque goes front to back.

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

Similar to Vec 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 alwaysleaves one space empty), truncate, shrink_to etc. exist and follow the same observations as in Vec study. The notable methods arepush_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() -> Tas_slices (and the mut one) which contains, in order the content of the VecDeque.

That’s it for now!