Struct minivec::MiniVec [−][src]
#[repr(transparent)]pub struct MiniVec<T> { /* fields omitted */ }
Expand description
MiniVec
is a space-optimized implementation of alloc::vec::Vec
that is only the size of a single pointer and
also extends portions of its API, including support for over-aligned allocations. MiniVec
also aims to bring as
many Nightly features from Vec
to stable toolchains as is possible. In many cases, it is a drop-in replacement
for the “real” Vec
.
Implementations
append
moves every element from other
to the back of self
. other.is_empty()
is true
once this operation
completes and its capacity is unaffected.
Example
let mut vec = minivec::mini_vec![1, 2, 3];
let mut vec2 = minivec::mini_vec![4, 5, 6];
vec.append(&mut vec2);
assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
assert_eq!(vec2, []);
as_mut_ptr
returns a *mut T
to the underlying array.
- May return a null pointer.
- May be invalidated by calls to
reserve()
- Can outlive its backing
MiniVec
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
let mut p = vec.as_mut_ptr();
for idx in 0..vec.len() {
unsafe {
*p.add(idx) = *p.add(idx) + 3;
}
}
assert_eq!(vec, [4, 5, 6, 7]);
as_mut_slice
obtains a mutable reference to a slice that’s attached to the backing array.
Example
let mut vec = minivec::mini_vec![1, 2, 3];
{
let as_slice: &mut [_] = vec.as_mut_slice();
as_slice[0] = 1337;
}
assert_eq!(vec[0], 1337);
as_ptr
obtains a *const T
to the underlying allocation.
- May return a null pointer.
- May be invalidated by calls to
reserve()
- Can outlive its backing
MiniVec
- May allow access to unitialized memory/non-existent objects
- May create out-of-bounds memory access
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
let mut p = vec.as_mut_ptr();
let mut sum = 0;
for idx in 0..vec.len() {
unsafe {
sum += *p.add(idx);
}
}
assert_eq!(sum, 1 + 2 + 3 + 4);
as_slice
obtains a reference to the backing array as an immutable slice of T
.
Example
let vec = minivec::mini_vec![1, 2, 3, 4];
let mut sum = 0;
let as_slice : &[_] = vec.as_slice();
for idx in 0..vec.len() {
sum += as_slice[idx];
}
assert_eq!(sum, 1 + 2 + 3 + 4);
capacity
obtains the number of elements that can be inserted into the MiniVec
before a
reallocation will be required.
Note: MiniVec
aims to use the same reservation policy as alloc::vec::Vec
.
Example
let vec = minivec::MiniVec::<i32>::with_capacity(128);
assert_eq!(vec.len(), 0);
assert_eq!(vec.capacity(), 128);
clear
clears the current contents of the MiniVec
. Afterwards, len()
will return 0. capacity()
is not affected.
Logically equivalent to calling minivec::MiniVec::truncate(0)
.
Note: destruction order of the contained elements is not guaranteed.
Example
let mut vec = minivec::mini_vec![-1; 256];
let cap = vec.capacity();
assert_eq!(vec.len(), 256);
vec.clear();
assert_eq!(vec.len(), 0);
assert_eq!(vec.capacity(), cap);
dedeup
“de-duplicates” all adjacent identical values in the vector.
Logically equivalent to calling minivec::MiniVec::dedup_by(|x, y| x == y)
.
Example
let mut v = minivec::mini_vec![1, 2, 1, 1, 3, 3, 3, 4, 5, 4];
v.dedup();
assert_eq!(v, [1, 2, 1, 3, 4, 5, 4]);
dedup_by
“de-duplicates” all adjacent elements for which the supplied binary predicate
returns true.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
vec.dedup_by(|x, y| *x + *y < 8);
// 1 + 2 < 8
// 1 + 3 < 8
// 1 + 4 < 8...
// 1 + 7 == 8
assert_eq!(vec, [1, 7, 8, 9, 10]);
dedup_by_key
“de-duplicates” all adjacent elements where key(elem1) == key(elem2)
.
Example
let mut vec = minivec::mini_vec!["a", "b", "c", "aa", "bbb", "cc", "dd"];
vec.dedup_by_key(|x| x.len());
assert_eq!(vec, ["a", "aa", "bbb", "cc"]);
drain
returns a minivec::Drain
iterator which lazily removes elements from the supplied
range
.
If the returned iterator is not iterated until exhaustion then the Drop
implementation
for Drain
will remove the remaining elements.
Panics
Panics if the supplied range would be outside the vector
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let other_vec : minivec::MiniVec<_> = vec.drain(1..7).map(|x| x + 2).collect();
assert_eq!(vec, [1, 8, 9, 10]);
assert_eq!(other_vec, [4, 5, 6, 7, 8, 9]);
pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>ⓘNotable traits for DrainFilter<'_, T, F>impl<T, F> Iterator for DrainFilter<'_, T, F> where
F: FnMut(&mut T) -> bool, type Item = T;
where
F: FnMut(&mut T) -> bool,
pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>ⓘNotable traits for DrainFilter<'_, T, F>impl<T, F> Iterator for DrainFilter<'_, T, F> where
F: FnMut(&mut T) -> bool, type Item = T;
where
F: FnMut(&mut T) -> bool,
impl<T, F> Iterator for DrainFilter<'_, T, F> where
F: FnMut(&mut T) -> bool, type Item = T;
drain_filter
creates a new DrainFilter
iterator that when iterated will
remove all elements for which the supplied pred
returns true
.
Removal of elements is done by transferring ownership of the element to the iterator.
Note: if the supplied predicate panics then DrainFilter
will stop all usage of it and then
backshift all untested elements and adjust the MiniVec
’s length accordingly.
Example
let mut vec = minivec::mini_vec![
1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
39,
];
let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<minivec::MiniVec<_>>();
assert_eq!(removed.len(), 10);
assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
assert_eq!(vec.len(), 14);
assert_eq!(
vec,
vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
);
drain_vec
returns a new instance of a MiniVec
, created by moving the content out of self
.
Compared to drain
method, this is just simple swap of pointers. As result, any pointer to self
becomes
invalid.
Example
use minivec::mini_vec;
let mut vec = mini_vec![1, 2, 3, 4, 5, 6, 7, 9];
let new_vec = vec.drain_vec();
assert_eq!(vec.len(), 0);
assert_eq!(new_vec, [1, 2, 3, 4, 5, 6, 7, 9]);
let new_vec = vec.drain_vec();
assert_eq!(vec.len(), 0);
assert_eq!(new_vec, []);
from_raw_part
reconstructs a MiniVec
from a previous call to MiniVec::as_mut_ptr
or the pointer from into_raw_parts
.
Safety
from_raw_part
is incredibly unsafe and can only be used with the value of
MiniVec::as_mut_ptr
. This is because the allocation for the backing array stores metadata
at its head and is not guaranteed to be stable so users are discouraged from attempting to
support this directly.
Panics
Panics in debug mode if the supplied pointer is null.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
let ptr = vec.as_mut_ptr();
std::mem::forget(vec);
let new_vec = unsafe { minivec::MiniVec::from_raw_part(ptr) };
assert_eq!(new_vec, [1, 2, 3, 4]);
from_raw_parts
is an API-compatible version of alloc::vec::Vec::from_raw_parts
. Because
of MiniVec
’s optimized layout, it’s not strictly required for a user to pass the length
and capacity explicitly.
Like MiniVec::from_raw_part
, this function is only safe to use
with the result of a call to MiniVec::as_mut_ptr()
.
Panics
Panics in debug mode if the supplied pointer is null.
Safety
A very unsafe function that should only really be used when passing the vector to a C API.
Does not support over-aligned allocations. The alignment of the pointer must be that of its natural alignment.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
let len = vec.len();
let cap = vec.capacity();
let ptr = vec.as_mut_ptr();
std::mem::forget(vec);
let new_vec = unsafe { minivec::MiniVec::from_raw_parts(ptr, len, cap) };
assert_eq!(new_vec, [1, 2, 3, 4]);
insert
places an element at the specified index, subsequently shifting all elements to the
right of the insertion index by 1
Panics
Will panic when index > vec.len()
.
Example
let mut vec = minivec::mini_vec![0, 1, 2, 3];
vec.insert(1, 1337);
assert_eq!(vec, [0, 1337, 1, 2, 3]);
vec.insert(vec.len(), 7331);
assert_eq!(vec, [0, 1337, 1, 2, 3, 7331]);
into_raw_parts
will leak the underlying allocation and return a tuple containing a pointer
to the start of the backing array and its length and capacity.
The results of this function are directly compatible with from_raw_parts
.
Example
let vec = minivec::mini_vec![1, 2, 3, 4, 5];
let (old_len, old_cap) = (vec.len(), vec.capacity());
let (ptr, len, cap) = vec.into_raw_parts();
assert_eq!(len, old_len);
assert_eq!(cap, old_cap);
let vec = unsafe { minivec::MiniVec::from_raw_parts(ptr, len, cap) };
assert_eq!(vec, [1, 2, 3, 4, 5]);
is_empty()
returns whether or not the MiniVec
has a length greater than 0.
Logically equivalent to manually writing: v.len() == 0
.
Example
let vec = minivec::MiniVec::<i32>::with_capacity(256);
assert!(vec.is_empty());
assert!(vec.capacity() > 0);
leak
“leaks” the supplied MiniVec
, i.e. turn it into a ManuallyDrop
instance and return a reference to the backing array via &'a [T]
where 'a
is a
user-supplied lifetime.
Most useful for turning an allocation with dynamic duration into one with static duration.
Example
let vec = minivec::mini_vec![1, 2, 3];
let static_ref: &'static mut [i32] = minivec::MiniVec::leak(vec);
static_ref[0] += 1;
assert_eq!(static_ref, &[2, 2, 3]);
len
returns the current lenght of the vector, i.e. the number of actual elements in it
capacity() >= len()
is true for all cases
Example
let mut vec = minivec::mini_vec![-1; 256];
assert_eq!(vec.len(), 256);
MiniVec::new
constructs an empty MiniVec
.
Note: does not allocate any memory.
Panics
Panics when a zero-sized type is attempted to be used.
Example
let mut vec = minivec::MiniVec::<i32>::new();
assert_eq!(vec.as_mut_ptr(), std::ptr::null_mut());
assert_eq!(vec.len(), 0);
assert_eq!(vec.capacity(), 0);
push
appends an element value
to the end of the vector. push
automatically reallocates
if the vector does not have sufficient capacity.
Unlike the standard library Vec
, MiniVec::push
returns a mutable reference to the newly created element that’s
been placed at the back of the vector.
Example
let mut vec = minivec::MiniVec::<i32>::with_capacity(64);
for idx in 0..128 {
vec.push(idx);
}
assert_eq!(vec.len(), 128);
remove
moves the element at the specified index
and then returns it to the user. This
operation shifts all elements to the right index
to the left by one so it has a linear
time complexity of vec.len() - index
.
Panics
Panics if index >= len()
.
Example
let mut vec = minivec::mini_vec![0, 1, 2, 3];
vec.remove(0);
assert_eq!(vec, [1, 2, 3]);
remove_item
removes the first element identical to the supplied item
using a
left-to-right traversal of the elements.
Example
let mut vec = minivec::mini_vec![0, 1, 1, 1, 2, 3, 4];
vec.remove_item(&1);
assert_eq!(vec, [0, 1, 1, 2, 3, 4]);
reserve
ensures there is sufficient capacity for additional
extra elements to be either
inserted or appended to the end of the vector. Will reallocate if needed otherwise this
function is a no-op.
Guarantees that the new capacity is greater than or equal to len() + additional
.
Example
let mut vec = minivec::MiniVec::<i32>::new();
assert_eq!(vec.capacity(), 0);
vec.reserve(128);
assert!(vec.capacity() >= 128);
reserve_exact
ensures that the capacity of the vector is exactly equal to
len() + additional
unless the capacity is already sufficient in which case no operation is
performed.
Example
let mut vec = minivec::MiniVec::<i32>::new();
vec.reserve_exact(57);
assert_eq!(vec.capacity(), 57);
resize
will clone the supplied value
as many times as required until len()
becomes
new_len
. If the current len()
is greater than new_len
then the vector
is truncated in a way that’s identical to calling vec.truncate(new_len)
. If the len()
and new_len
match then no operation is performed.
Example
let mut vec = minivec::mini_vec![-1; 256];
vec.resize(512, -1);
assert_eq!(vec.len(), 512);
vec.resize(64, -1);
assert_eq!(vec.len(), 64);
resize_with
will invoke the supplied callable f
as many times as is required until
len() == new_len
is true. If the new_len
exceeds the current len()
then the vector will be resized via a call to truncate(new_len)
. If the new_len
and
len()
are equal then no operation is performed.
Example
let mut vec = minivec::MiniVec::<i32>::new();
vec.resize_with(128, || 1337);
assert_eq!(vec.len(), 128);
retain
removes all elements from the vector for with f(elem)
is false
using a
left-to-right traversal.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4, 5, 6];
let is_even = |x: &i32| *x % 2 == 0;
vec.retain(is_even);
assert_eq!(vec, [2, 4, 6]);
set_len
reassigns the internal len_
data member to the user-supplied len
.
Safety
This function is unsafe in the sense that it will NOT call .drop()
on the elements
excluded from the new len so this function should only be called when T
is a Copy
type.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
unsafe { vec.set_len(2) };
assert_eq!(vec.len(), 2);
shrink_to
will attempt to adjust the backing allocation such that it has space for at
least min_capacity
elements.
If the min_capacity
is smaller than the current length of the vector then the capacity
will be shrunk down to len()
.
If the capacity()
is identical to min_capacity
then this function
does nothing.
Panics
If the min_capacity
is larger than the current capacity this function will panic.
Otherwise, the allocation is reallocated with the new min_capacity
kept in mind.
Example
let mut vec = minivec::MiniVec::<i32>::with_capacity(128);
assert!(vec.capacity() >= 128);
vec.shrink_to(64);
assert_eq!(vec.capacity(), 64);
shrink_to_fit
will re-adjust the backing allocation such that its capacity is now equal
to its length
Example
let mut vec = minivec::MiniVec::with_capacity(512);
vec.push(1);
vec.push(2);
vec.push(3);
vec.shrink_to_fit();
assert_eq!(vec.capacity(), 3);
spare_capacity_mut
returns a mutable slice to MaybeUninit<T>
.
This is a more structured way of interacting with MiniVec
as an unitialized allocation vs
simply creating a vector with capacity and then mutating its contents directly via
as_mut_ptr
.
Once manipulation of the unitialized elements has been completed, a call to set_len
is required otherwise the contained elements cannot be accessed by MiniVec
’s normal
methods nor will the elements be dropped.
Example
let mut vec = minivec::MiniVec::<i32>::with_capacity(24);
let mut buf = vec.spare_capacity_mut();
for idx in 0..4 {
unsafe { buf[idx].as_mut_ptr().write(idx as i32) };
}
unsafe { vec.set_len(4) };
assert_eq!(vec, [0, 1, 2, 3]);
pub fn splice<R, I>(
&mut self,
range: R,
replace_with: I
) -> Splice<'_, <I as IntoIterator>::IntoIter>ⓘ where
I: IntoIterator<Item = T>,
R: RangeBounds<usize>,
pub fn splice<R, I>(
&mut self,
range: R,
replace_with: I
) -> Splice<'_, <I as IntoIterator>::IntoIter>ⓘ where
I: IntoIterator<Item = T>,
R: RangeBounds<usize>,
splice
returns a Splice
iterator. Splice
is similar in spirit to Drain
but instead of simply shifting the remaining elements from the vector after it’s been
drained, the range is replaced with the Iterator
specified by replace_with
.
Much like Drain
, if the Splice
iterator is not iterated until exhaustion then the
remaining elements will be removed when the iterator is dropped.
Splice
only fills the removed region when it is dropped.
Panics
Panics if the supplied range
is outside of the vector’s bounds.
Example
let mut x = minivec::mini_vec![1, 2, 3, 4, 5, 6];
let new = [7, 8];
let y: minivec::MiniVec<_> = x.splice(1..4, new.iter().cloned()).collect();
assert_eq!(x, &[1, 7, 8, 5, 6]);
assert_eq!(y, &[2, 3, 4]);
split_at_spare_mut
returns a pair containing two mutable slices: one referring to the currently
initialized elements and the other pointing to the spare capacity of the backing allocation as a
&mut [MaybeUninit<T>]
.
This is a convenience API that handles borrowing issues when attempting to do something like:
let (init, uninit) = (vec.as_mut_slice(), vec.spare_capacity_mut());
which results in borrowing errors from the compiler:
cannot borrow
vec
as mutable more than once at a time
Safety
When working with uninitialized storage, it is required that the user call set_len()
appropriately
to readjust the length of the vector. This ensures that newly inserted elements are dropped when
needed.
Example
let mut vec = minivec::MiniVec::<String>::with_capacity(4);
vec.push(String::from("hello"));
vec.push(String::from("world"));
let (_, uninit) = vec.split_at_spare_mut();
uninit[0] = core::mem::MaybeUninit::<String>::new(String::from("rawr"));
uninit[1] = core::mem::MaybeUninit::<String>::new(String::from("RAWR"));
unsafe { vec.set_len(4) };
assert_eq!(vec[2], "rawr");
assert_eq!(vec[3], "RAWR");
split_off
will segment the vector into two, returning the new segment to the user.
After this function call, self
will have kept elements [0, at)
while the new segment
contains elements [at, len)
.
Panics
Panics if at
is greater than len()
.
Example
let mut vec = minivec::mini_vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let tail = vec.split_off(7);
assert_eq!(vec, [0, 1, 2, 3, 4, 5, 6]);
assert_eq!(tail, [7, 8, 9, 10]);
swap_remove
removes the element located at index
and replaces it with the last value
in the vector, returning the removed element to the caller.
Panics
Panics if index >= len()
.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4];
let num = vec.swap_remove(0);
assert_eq!(num, 1);
assert_eq!(vec, [4, 2, 3]);
truncate
adjusts the length of the vector to be len
. If len
is greater than or equal
to the current length no operation is performed. Otherwise, the vector’s length is
readjusted to len
and any remaining elements to the right of len
are dropped.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4, 5];
vec.truncate(2);
assert_eq!(vec, [1, 2]);
with_alignment
is similar to its counterpart with_capacity
except it takes an additional argument: the alignment to use for the allocation.
The supplied alignment must be a number divisible by 2 and larger than or equal to the
result of core::mem::align_of::<*const ()>()
.
The internal allocation used to store the header information for MiniVec
is aligned to the
supplied value and then sufficient padding is inserted such that the result of as_ptr()
will always be aligned as well.
This is useful for creating over-aligned allocations for primitive types such as when using
SIMD
intrinsics. For example, some vectorized floating point loads and stores must be
aligned on a 32 byte boundary. with_alignment
is intended to make this possible with a
Vec
-like container.
Errors
Returns a Result
that contains either MiniVec<T>
or a LayoutErr
.
Example
#[cfg(target_arch = "x86")]
use std::arch::x86::*;
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;
let alignment = 32;
let num_elems = 2048;
let mut v1 = minivec::MiniVec::<f32>::with_alignment(num_elems, alignment).unwrap();
let mut v2 = minivec::MiniVec::<f32>::with_alignment(num_elems, alignment).unwrap();
v1
.spare_capacity_mut()
.iter_mut()
.zip(v2.spare_capacity_mut().iter_mut())
.enumerate()
.for_each(|(idx, (x1, x2))| {
*x1 = core::mem::MaybeUninit::new(idx as f32);
*x2 = core::mem::MaybeUninit::new(idx as f32);
});
unsafe {
v1.set_len(num_elems);
v2.set_len(num_elems);
// use vectorization to speed up the summation of two vectors
//
for idx in 0..(num_elems / 8) {
let offset = idx * 8;
let p = v1.as_mut_ptr().add(offset);
let q = v2.as_mut_ptr().add(offset);
let r1 = _mm256_load_ps(p);
let r2 = _mm256_load_ps(q);
let r3 = _mm256_add_ps(r1, r2);
_mm256_store_ps(p, r3);
}
}
v1
.iter()
.enumerate()
.for_each(|(idx, v)| {
assert_eq!(*v, idx as f32 * 2.0);
});
with_capacity
is a static factory function that returns a MiniVec
that contains space
for capacity
elements.
This function is logically equivalent to calling .reserve_exact()
on a vector with 0
capacity.
Example
let mut vec = minivec::MiniVec::<i32>::with_capacity(128);
assert_eq!(vec.len(), 0);
assert_eq!(vec.capacity(), 128);
extend_from_slice
will append each element from elems
in a left-to-right order, cloning
each value in elems
.
Example
let mut vec = minivec::mini_vec![1, 2];
let s : &[i32] = &[3, 4];
vec.extend_from_slice(s);
assert_eq!(vec, [1, 2, 3, 4]);
extend_from_within
clones the elements contained in the provided Range
and appends them
to the end of the vector, allocating extra space as required.
Panics
Panics if the provided range exceeds the bounds of [0, len)
.
Example
let mut vec = minivec::mini_vec![1, 2, 3, 4, 5];
vec.extend_from_within(1..4);
assert_eq!(vec, [1, 2, 3, 4, 5, 2, 3, 4]);
assume_minivec_init
is a helper designed to make working with uninitialized memory more ergonomic.
Safety
Whatever length the current MiniVec
has, it is consumed and then returned to the caller as a MiniVec<T>
thus
making the function unsafe
as it relies on the caller to uphold length invariants.
Example
let mut buf = minivec::mini_vec![core::mem::MaybeUninit::<u8>::uninit(); 512];
buf
.iter_mut()
.for_each(|v| *v = core::mem::MaybeUninit::new(137));
unsafe { buf.set_len(512) };
let bytes = unsafe { buf.assume_minivec_init() };
assert_eq!(bytes[0], 137);
assert_eq!(bytes[511], 137);
Trait Implementations
Mutably borrows from an owned value. Read more
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
Performs the conversion.
Creates a value from an iterator. Read more
This method returns an ordering between self
and other
values if one exists. Read more
This method tests less than (for self
and other
) and is used by the <
operator. Read more
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
Auto Trait Implementations
impl<T> RefUnwindSafe for MiniVec<T> where
T: RefUnwindSafe,
impl<T> UnwindSafe for MiniVec<T> where
T: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more