pub struct Stack<T> { /* private fields */ }Implementations§
Source§impl<T> Stack<T>
impl<T> Stack<T>
Sourcepub const fn new() -> Self
pub const fn new() -> Self
Constructs a new, empty Stack<T>.
The stack will not allocate until elements are pushed onto it.
§Examples
use bump_stack::Stack;
let mut stack: Stack<i32> = Stack::new();Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Constructs a new, empty Stack<T> with at least the specified capacity.
The stack will be able to hold at least capacity elements without new
allocations. This method is allowed to allocate for more elements than
capacity. If capacity is zero, the stack will not allocate.
If it is important to know the exact allocated capacity of a Stack,
always use the capacity method after construction.
For Stack<T> where T is a zero-sized type, there will be no
allocation and the capacity will always be usize::MAX.
§Panics
Panics if the capacity exceeds isize::MAX bytes.
§Examples
let mut stk = Stack::with_capacity(10);
// The stack contains no items, even though it has capacity for more
assert_eq!(stk.len(), 0);
assert!(stk.capacity() >= 10);
// These are all done without additional allocations...
for i in 0..10 {
stk.push(i);
}
assert_eq!(stk.len(), 10);
assert!(stk.capacity() >= 10);
// ...but this may make the stack allocate a new chunk
stk.push(11);
assert_eq!(stk.len(), 11);
assert!(stk.capacity() >= 11);
// A stack of a zero-sized type will always over-allocate, since no
// allocation is necessary
let stk_units = Stack::<()>::with_capacity(10);
assert_eq!(stk_units.capacity(), usize::MAX);Sourcepub const fn capacity(&self) -> usize
pub const fn capacity(&self) -> usize
Returns the total number of elements the stack can hold without new allocating.
Sourcepub const fn len(&self) -> usize
pub const fn len(&self) -> usize
Returns the total number of elements the stack can hold without additional allocations.
§Examples
let mut stk: Stack<i32> = Stack::with_capacity(10);
stk.push(42);
assert!(stk.capacity() >= 10);A stack with zero-sized elements will always have a capacity of
usize::MAX:
#[derive(Clone)]
struct ZeroSized;
fn main() {
assert_eq!(std::mem::size_of::<ZeroSized>(), 0);
let stk = Stack::<ZeroSized>::with_capacity(0);
assert_eq!(stk.capacity(), usize::MAX);
}Sourcepub const fn is_empty(&self) -> bool
pub const fn is_empty(&self) -> bool
Returns true if the stack contains no elements.
§Examples
let mut s = Stack::new();
assert!(s.is_empty());
s.push(1);
assert!(!s.is_empty());Sourcepub fn first(&self) -> Option<&T>
pub fn first(&self) -> Option<&T>
Returns a reference to the first element of the stack, or None if it
is empty.
§Examples
let mut s = Stack::new();
assert_eq!(None, s.first());
s.push(42);
assert_eq!(Some(&42), s.first());Sourcepub fn first_mut(&mut self) -> Option<&mut T>
pub fn first_mut(&mut self) -> Option<&mut T>
Returns a mutable reference to the first element of the slice, or None
if it is empty.
§Examples
let mut s = Stack::new();
assert_eq!(None, s.first_mut());
s.push(1);
if let Some(first) = s.first_mut() {
*first = 5;
}
assert_eq!(s.first(), Some(&5));Sourcepub fn last(&self) -> Option<&T>
pub fn last(&self) -> Option<&T>
Returns the reference to last element of the stack, or None if it is
empty.
§Examples
let mut stk = Stack::new();
assert_eq!(None, stk.last());
stk.push(1);
assert_eq!(Some(&1), stk.last());Sourcepub fn last_mut(&mut self) -> Option<&mut T>
pub fn last_mut(&mut self) -> Option<&mut T>
Returns a mutable reference to the last item in the stack, or None if
it is empty.
§Examples
let mut stk = Stack::new();
assert_eq!(None, stk.last_mut());
stk.push(5);
assert_eq!(Some(&mut 5), stk.last_mut());
if let Some(last) = stk.last_mut() {
*last = 10;
}
assert_eq!(Some(&mut 10), stk.last_mut());Sourcepub fn push(&self, value: T) -> &T
pub fn push(&self, value: T) -> &T
Appends an element to the stack returning a reference to it.
§Panics
Panics if the global allocator cannot allocate a new chunk of memory.
§Examples
let stk = Stack::new();
let new_element = stk.push(3);
assert_eq!(new_element, &3);
assert_eq!(stk, [3]);§Time complexity
Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.
If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.
Sourcepub fn push_with<F>(&self, f: F) -> &Twhere
F: FnOnce() -> T,
pub fn push_with<F>(&self, f: F) -> &Twhere
F: FnOnce() -> T,
Pre-allocate space for an element in this stack, initializes it using the closure, and returns a reference to the new element.
§Examples
let stk = Stack::new();
let new_element = stk.push_with(|| 3);
assert_eq!(new_element, &3);
assert_eq!(stk, [3]);§Time complexity
Takes amortized O(1) time. If the stack’s current chunk of memory is exhausted, it tries to use the cached one if it exists, otherwise it tries to allocate a new chunk.
If the new chunk of memory is too big, it tries to divide the capacity by two and allocate it again until it reaches the minimum capacity. If it does, it panics.
Sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the stack, removing all elements.
This method leaves the biggest chunk of memory for future allocations.
§Examples
let mut stk = Stack::from([1, 2, 3]);
stk.clear();
assert!(stk.is_empty());
assert!(stk.capacity() > 0);Sourcepub fn iter(&self) -> impl Iterator<Item = &T>
pub fn iter(&self) -> impl Iterator<Item = &T>
Returns an iterator over the stack.
The iterator yields all items from start to end.
§Examples
let stk = Stack::from([1, 2, 4]);
let mut iterator = stk.iter();
assert_eq!(iterator.next(), Some(&1));
assert_eq!(iterator.next(), Some(&2));
assert_eq!(iterator.next(), Some(&4));
assert_eq!(iterator.next(), None);Since Stack allows to push new elements using immutable reference to
itself, you can push during iteration. But iteration is running over
elements existing at the moment of the iterator creating. It guarantees
that you won’t get infinite loop.
let stk = Stack::from([1, 2, 4]);
for elem in stk.iter() {
stk.push(*elem);
}
assert_eq!(stk.len(), 6);
assert_eq!(stk, [1, 2, 4, 1, 2, 4]);