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.
rust
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);
}
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.