Crate btree_vec

This crate provides a growable array (vector) implemented using a B-tree (more specifically, a B+ tree). It provides 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);
}

Modules

vec

Defines BTreeVec, a growable array implemented as a B+ tree.

Type Definitions

BTreeVec

vec::BTreeVec with a default branching factor.