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