Module std::deque

Deque, a double-ended queue: push and pop at both ends in amortised O(1), and index from the front. Pushing asks with Alloc because the ring may grow; nothing else allocates.

Source: std/deque.weir; committed interface: std/deque.iface. Index

struct Deque

pub struct Deque<T> {
    /* private fields */
}

A double-ended queue over a growable ring buffer.

Elements are indexed from the front (0 is Deque::front). Pushing at either end is amortised O(1): a full ring doubles (4 slots at first) without moving the elements one by one. Popping and reading never allocate.

impl<T> Deque<T>

method len

pub fn len(&self) -> usize

The number of elements.

Committed interface (std/deque.iface): the signature alone.

method is_empty

pub fn is_empty(&self) -> Bool

Whether the deque holds no element.

Committed interface (std/deque.iface): the signature alone.

method get

pub fn get(&self, i: usize) -> Option<&T>

The element at index i from the front; None when i is not below len().

Committed interface (std/deque.iface): the signature alone.

method get_mut

pub fn get_mut(&mut self, i: usize) -> Option<&mut T>

The element at index i from the front, mutably; None when i is not below len().

Committed interface (std/deque.iface):

writes through self: everything

method front

pub fn front(&self) -> Option<&T>

The first element; None when empty.

Committed interface (std/deque.iface): the signature alone.

method back

pub fn back(&self) -> Option<&T>

The last element; None when empty.

Committed interface (std/deque.iface): the signature alone.

method pop_front

pub fn pop_front(&mut self) -> Option<T>

Removes and returns the first element; None when empty.

Committed interface (std/deque.iface):

writes through self: {head, len}
stores T in regions _

method pop_back

pub fn pop_back(&mut self) -> Option<T>

Removes and returns the last element; None when empty.

Committed interface (std/deque.iface):

writes through self: {len}
stores T in regions _

impl<T: copy> Deque<T>

method iter

pub fn iter(&self) -> DequeIter<T>

An iterator over copies of the elements, front to back. It borrows the deque while it lives.

Committed interface (std/deque.iface): the signature alone.

impl<T: drops {Alloc}> Deque<T>

method new

pub fn new() -> Deque<T> with Alloc

An empty deque; its ring is sized on the first push.

Committed interface (std/deque.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc

method with_capacity

pub fn with_capacity(n: usize) -> Deque<T> with Alloc

An empty deque that holds n elements without growing.

Committed interface (std/deque.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc

method push_back

pub fn push_back(&mut self, x: T) with Alloc

Appends x at the back; with Alloc because a full ring grows (amortised O(1)). x is always kept: a failed allocation aborts through Alloc, never a silent drop.

Committed interface (std/deque.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc
writes through self: {len, ring.cap, ring.data, ring.len} and its shape
destroys values of T

method push_front

pub fn push_front(&mut self, x: T) with Alloc

Prepends x at the front; with Alloc because a full ring grows (amortised O(1)). x is always kept: a failed allocation aborts through Alloc, never a silent drop.

Committed interface (std/deque.iface):

bound Alloc: Alloc any
aborts: Alloc.alloc
writes through self: {head, len, ring.cap, ring.data, ring.len} and its shape
destroys values of T

struct DequeIter

pub struct DequeIter<T>: forget {
    /* private fields */
}

The iterator Deque::iter returns: copies of the elements front to back, borrowing the deque.

Implementations: