Deque
Owns an allocator-aware circular sequence with efficient operations at both ends.
Module std.collections
import std.collections;Public declaration contracts and authored examples. A page can document several related symbols. Implementation bodies are excluded.
Deque
pub final class Deque<T, A = DefaultAllocator>
where T: Movable where A: Allocator, Defaultable, MovableOwns an allocator-aware circular sequence with efficient operations at both ends.
Exactly Length logical slots from Head are live; other capacity is raw storage. Push/pop at either end costs O(1) without growth. Geometric growth gives amortized O(1) insertion and moves O(n) items on reallocation. At costs O(1). The container is noncopy and transfers its buffer/allocator together. Every structural mutation, move or destruction invalidates views and cursors. External synchronization is required. Wrapped storage has no contiguous slice. T: Movable element type; move assignment is not needed for ring operations. A: Movable Defaultable allocator owner, defaulting to DefaultAllocator.
Example
module example.deque;
from std.collections import Deque;
from std.memory import DefaultAllocator;
fn Main() -> i32 {
var Values = Deque<i32>.WithAllocator(default(DefaultAllocator));
if !Values.IsEmpty || Values.Length != 0 { return 1; }
if Values.TryReserve(4) is .Err { Error = _ } { return 2; }
if Values.TryPushBack(20) is .Err { Error = _ } { return 3; }
if Values.TryPushFront(2) is .Err { Error = _ } { return 4; }
if Values.TryPushBack(40) is .Err { Error = _ } { return 5; }
Values.At(1) = 21;
{
var Cursor = Values.CreateWritableIterator();
while Cursor.Next() is .Some { Value = Item } { Item += 1; }
}
if Values.Front().Unwrap() != 3 || Values.Back().Unwrap() != 41 { return 6; }
if Values.PopFront().Unwrap() != 3 || Values.PopBack().Unwrap() != 41 { return 7; }
var Moved = move(Values);
if !Values.IsEmpty || Moved.Length != 1 { return 8; }
Values = move(Moved);
if !Moved.IsEmpty || Values.At(0) != 22 { return 9; }
{
let Readonly: readonly Deque<i32>& = Values;
if Readonly.At(0) != 22 || Readonly.Front().Unwrap() != 22 ||
Readonly.Back().Unwrap() != 22 { return 10; }
var Cursor = Readonly.CreateIterator();
if Cursor.Next().Unwrap() != 22 { return 10; }
if Cursor.Next() is .Some { Value = _ } { return 11; }
}
{
var Cursor = Values.CreateIterator();
while Cursor.Next() is .Some { Value = Item } { Item += 1; }
}
Values.Clear();
if Values.TryShrinkToFit() is .Err { Error = _ } { return 12; }
if Values.Capacity != 0 { return 13; }
return 0;
}Deque.init
pub init()Creates an allocation-free empty owner.
Deque.init
pub init(mut Value: A)Creates an empty ring by transferring its allocator. Value: Allocator owner moved without allocation.
Deque.init
pub init(Source: readonly Self&) = delete;Rejects copying ring ownership. Source: Noncopy source.
Deque.init
pub init(Source: mut Self&&)Transfers the ring allocation and allocator, leaving an empty source. Source: Writable owner left destructible with zero capacity.
Deque.operator
pub fn operator =(Source: readonly Self&) -> void = delete;Rejects copying into live ring storage. Source: Noncopy source. Return: No value; deleted.
Deque.operator
pub fn operator =(Source: mut Self&&) -> voidReleases old storage and transfers another ring and allocator. Source: Writable owner left empty; exact self-assignment is unchanged. Return: No value; old live elements and allocation are released first.
Deque.WithAllocator
pub static fn WithAllocator(mut Value: A) -> Deque<T, A>Creates an allocation-free ring with a transferred allocator. Value: Allocator owner consumed by the result. Return: Empty noncopy ring owner.
Deque.Length
pub Length: usize;Observes logical length in O(1).
Deque.Capacity
pub Capacity: usize;Observes allocated raw-slot capacity in O(1).
Deque.IsEmpty
pub IsEmpty: bool;Observes whether no live elements remain.
Deque.TryReserve
pub fn TryReserve(MinimumCapacity: usize) -> Result<void, AllocationError>Reserves raw ring capacity without changing logical order. MinimumCapacity: Desired item capacity. Return: Ok or AllocationError; allocation failure preserves live contents. Warning: May allocate and move O(n) elements; relocation invalidates all views.
Deque.TryShrinkToFit
pub fn TryShrinkToFit() -> Result<void, AllocationError>Releases excess raw slots without changing logical order. Return: Ok or AllocationError; allocation failure preserves live contents. Warning: May allocate and move O(n) elements; relocation invalidates all views.
Deque.TryPushBack
pub fn TryPushBack(mut Item: T) -> Result<void, DequeInsertionError<T>>Inserts one owned item after the logical back. Item: Value transferred on success or owned by the returned error. Return: Ok or DequeInsertionError retaining the original uninserted item. Warning: May allocate; invalidates views. Selected lifecycle traps have no rollback.
Deque.TryPushFront
pub fn TryPushFront(mut Item: T) -> Result<void, DequeInsertionError<T>>Inserts one owned item before the logical front. Item: Value transferred on success or owned by the returned error. Return: Ok or DequeInsertionError retaining the original uninserted item. Warning: May allocate; invalidates views. Selected lifecycle traps have no rollback.
Deque.PopFront
pub fn PopFront() -> T?Transfers and removes the logical front without allocation. Return: Owned item, or none when empty; O(1) lifecycle work. Warning: Invalidates all borrowed references and cursors.
Deque.PopBack
pub fn PopBack() -> T?Transfers and removes the logical back without allocation. Return: Owned item, or none when empty; O(1) lifecycle work. Warning: Invalidates all borrowed references and cursors.
Deque.At
pub readonly fn At(Index: usize) -> T&Borrows one logical element readonly in O(1). Index: Logical index below Length; out of range traps. Return: Readonly reference invalidated by structural mutation/move/destruction.
Deque.At
pub fn At(Index: usize) -> mut T&Borrows one logical element writable in O(1). Index: Logical index below Length; out of range traps. Return: Writable reference invalidated by structural mutation/move/destruction.
Deque.Front
pub readonly fn Front() -> T&?Borrows the front readonly. Return: Optional readonly reference, none when empty. Warning: Structural mutation, move or destruction invalidates the borrow.
Deque.Front
pub fn Front() -> mut T&?Borrows the front writable. Return: Optional writable reference, none when empty. Warning: Structural mutation, move or destruction invalidates the borrow.
Deque.Back
pub readonly fn Back() -> T&?Borrows the back readonly. Return: Optional readonly reference, none when empty. Warning: Structural mutation, move or destruction invalidates the borrow.
Deque.Back
pub fn Back() -> mut T&?Borrows the back writable. Return: Optional writable reference, none when empty. Warning: Structural mutation, move or destruction invalidates the borrow.
Deque.CreateIterator
pub readonly fn CreateIterator() -> DequeIterator<T>Borrows a readonly logical-order cursor. Return: Nonowning allocation-free cursor. Warning: Structural mutation, move or destruction invalidates the cursor.
Deque.CreateIterator
pub fn CreateIterator() -> WritableDequeIterator<T>Borrows a writable logical-order cursor. Return: Nonowning allocation-free cursor. Warning: Structural mutation, move or destruction invalidates the cursor.
Deque.CreateWritableIterator
pub fn CreateWritableIterator() -> WritableDequeIterator<T>Explicitly borrows a writable logical-order cursor. Return: Nonowning allocation-free cursor. Warning: Structural mutation, move or destruction invalidates the cursor.
Deque.Clear
pub fn Clear() -> voidDestroys all live items in reverse logical order, retaining capacity. Return: No value; O(n) cleanup without allocation; invalidates all views.