btree-vec

此 crate 提供了一个使用 B 树（更确切地说，是 B+ 树）实现的可增长数组（向量）。它提供非摊销的 O(log n) 随机访问、插入和删除，以及 O(n) 迭代。分支因子也可以自定义。

设计类似于 Simon Tatham 描述的无序计数 B 树。

目前，该向量仅支持插入和删除单个元素，但将来可能会添加批量操作，包括 Extend 和 FromIterator 的实现。

示例

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 功能

如果启用 crate 功能 dropck_eyepatch，则 BTreeVec 中的项可以包含与向量本身寿命相同的引用。这需要 Rust 夜间版本，因为必须使用不稳定语言功能 dropck_eyepatch。

如果启用 crate 功能 allocator_api，则可以使用不稳定的 Allocator trait 配置 BTreeVec。或者，如果启用功能 allocator-fallback，则此 crate 将使用由 allocator-fallback 提供的分配器 API，而不是标准库的。