
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.
Rust std doc
The “default” usage of this type as a queue is to usepush_back
to add to the queue, andpop_front
to remove from the queue.extend
andappend
push onto the back in this manner, and iterating overVecDeque
goes front to back.
- Similar to
Vec
,VecDeque
has amortizedinsert to both ends of the container, but unlike
Vec
, it has amortizedremoval from both ends. (Recalling from
Vec
study, removal is strictlywith 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
andpop_back
which involve moving thehead
pointer andpush_front
andpop_front
which involve moving thetail
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!
Leave a Reply