orx-fixed-vec

An efficient fixed capacity vector with pinned element guarantees.

A FixedVec implements PinnedVec; you may read the detailed information about pinned element guarantees and why they are useful in the motivation-and-examples section. In brief, a pinned vector does not allow implicit changes in memory locations of its elements; such as moving the entire vector to another memory location due to additional capacity requirement.

Features

A fixed vec is simply a wrapper around the standard vector with the following two key differences:

• It is always created with an initial fixed capacity which cannot implicitly change.
• If we add more elements than the fixed capacity, the vector panics.

This leads to the following properties:

• Its implementation is uninteresting as it does nothing but exposes standard vector methods.
• For the very same reason, it is as performant as the standard vector; details can be found at the benches folder.
• It satisfies the pinned element guarantees, and hence, it implements PinnedVec unlike the standard vector.

Using a fixed capacity vector has limited use cases as this information is usually not available in situations where we use a vector. Therefore, we more frequently use the SplitVec as a dynamic capacity vector with pinned element guarantees. FixedVec, on the other hand, must be used only when we have the perfect knowledge on the upper bound of vector length.

In order to illustrate, consider an operation where we compute n outputs from n inputs; i.e., we map each element to a new element. Further, we want to collect or write the results in a new vector. In this case, we could safely use a FixedVec created with a capacity of n elements. This is exactly the parallel iterator Par does under the hood when the length of the output is known with certainty. In other situations, SplitVec is used as the pinned vector.

Examples

FixedVec api resembles and aims to cover as much as possible the standard vector's api.

use orx_fixed_vec::prelude::*;

// capacity is not optional
let mut vec = FixedVec::new(4);

assert_eq!(4, vec.capacity());

vec.push(0);
assert!(!vec.is_full());
assert_eq!(3, vec.room());

vec.extend_from_slice(&[1, 2, 3]);
assert_eq!(vec, &[0, 1, 2, 3]);
assert!(vec.is_full());

// vec.push(42); // push would've panicked when vec.is_full()

vec[0] = 10;
assert_eq!(10, vec[0]);

vec.remove(0);
vec.insert(0, 0);

assert_eq!(6, vec.iter().sum());

assert_eq!(vec.clone(), vec);

assert_eq!(&vec, &[0, 1, 2, 3]);

// allows zero-cost conversion into and from std Vec
let _std_vec: Vec<_> = vec.into();

Its main difference and objective is to provide pinned element guarantees as demonstrated in the example below.

use orx_fixed_vec::prelude::*;

let mut vec = FixedVec::new(100);

// push the first element
vec.push(42usize);
assert_eq!(vec, &[42]);

// let's get a pointer to the first element
let addr42 = &vec[0] as *const usize;

// let's push 99 new elements
for i in 1..100 {
    vec.push(i);
}

for i in 0..100 {
    assert_eq!(if i == 0 { 42 } else { i }, vec[i]);
}

// the memory location of the first element remains intact
assert_eq!(addr42, &vec[0] as *const usize);

// we can safely dereference it and read the correct value
// dereferencing is still unsafe for FixedVec,
// but the underlying guarantee will be used by wrappers such as ImpVec or SelfRefCol
assert_eq!(unsafe { *addr42 }, 42);

// the next push when `vec.is_full()` panics!
// vec.push(0);

Contributing

Contributions are welcome! If you notice an error, have a question or think something could be improved, please open an issue or create a PR.

License

This library is licensed under MIT license. See LICENSE for details.