btree-vec

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.

Documentation

Documentation is available on docs.rs.

License

btree-vec is licensed under version 3 of the GNU General Public License, or (at your option) any later version. See LICENSE.

Please note that this does not mean you have to license your project under the GPL if you use btree-vec. Your project can be licensed under any GPLv3-compatible license, including nearly all permissive licenses such as MIT or Apache 2.0. The terms of the GPL will apply only to the combination of your project with btree-vec (e.g., source code must be provided along with any compiled binaries); any portion of your project that does not depend on btree-vec may be used without adherence to the GPL.

Contributing

By contributing to btree-vec, you agree that your contribution may be used according to the terms of btree-vec’s license.