Expand description
This crate provides a growable array (vector) implemented using a B-tree (more specifically, a B+ tree). It provides non-amortized O(log n) random accesses, insertions, and removals, as well as O(n) iteration. The branching factor is also customizable.
The design is similar to unsorted counted B-trees as described by Simon Tatham.
For now, the vector supports insertions and removals only of single
elements, but bulk operations, including implementations of Extend
and FromIterator, may be added in the future.
Example
let mut vec = BTreeVec::new();
for i in 0..20 {
vec.push(i);
}
for i in 0..10 {
assert!(vec.remove(i) == i * 2);
}
for i in 0..10 {
assert!(vec[i] == i * 2 + 1);
}
for i in 0..10 {
vec.insert(i * 2, i * 2);
}
assert!(vec.len() == 20);
for (i, n) in vec.iter().copied().enumerate() {
assert!(i == n);
}Crate features
If the crate feature dropck_eyepatch is enabled, items in a BTreeVec
can contain references with the same life as the vector itself. This
requires Rust nightly, as the unstable language feature dropck_eyepatch
must be used.
If the crate feature allocator_api is enabled, you can configure
BTreeVec with the unstable Allocator trait. Alternatively, if the
feature allocator-fallback is enabled, this crate will use the allocator
API provided by allocator-fallback instead of the standard library’s.