flat-veb

不进行内部分配的 vEB 树的快速实现。

van Emde Boas 树是一种数据结构，用于维护有限大小的整数集合，支持以下查询

• insert(x) - 将整数 x 插入集合
• remove(x) - 从集合中删除整数 x
• contains(x) - 返回集合是否包含 x
• next(x) - 返回集合中最小的大于或等于 x 的整数
• prev(x) - 返回集合中最小的大于或等于 x 的整数

所有这些操作的时间复杂度都是 $\mathcal{O}(\log \log U)$，而该结构的空间复杂度是 $\mathcal{O}(U)$，其中 $U$ 是你可以放入集合中的最大整数。

用法

使用 VEBTree 特性和 VEBTreeX 类型，其中 X 是你将要插入的元素中的位数。换句话说，使用 VEBTreeX，你只能插入值小于 1 << X 的元素。

use flat_veb::{VEBTree, VEBTree24};
let mut tree = VEBTree24::new();

// note that VEBTree24 is a quite big object, using over 2 MB while empty,
// but the size doesn't increase when elements are inserted.

assert_eq!(tree.insert(123), true); // returns true if it wasn't already there
assert_eq!(tree.insert(1337), true);
assert_eq!(tree.insert(123), false); // false because it was already there

assert_eq!(tree.contains(123), true);
assert_eq!(tree.contains(42), false);

assert_eq!(tree.next(42), Some(123));
assert_eq!(tree.next(123), Some(123));
assert_eq!(tree.next(124), Some(1337));

assert_eq!(tree.remove(1337), true);
assert_eq!(tree.remove(1337), false); // it's not there when removing it the second time

assert_eq!(tree.next(124), None); // there is no element in te set >= 124

性能

在实现像 vEB 树这样的递归数据结构时，使用内部堆分配和间接引用是自然的，但这个实现避免了这一点，以获得更快的速度，代价是稍微繁琐的 API。

BTreeSet 可以执行 vEB 树能做的所有操作，还有很多更多，但速度较慢。当有足够的操作可以带来速度提升，而整数又足够小，使得 vEB 树不会占用太多空间时，vEB 树更为合适。

在从 https://judge.yosupo.jp/problem/predecessor_problem 下载的测试中，vEB 树比 BTreeSet 快约 10 倍，但这也包括 IO，这可能是 vEB 树花费大量时间的原因。需要更好的基准测试。

待办事项

• 更好的基准测试
• 创建一个返回适当容量 Box 的函数
• 反向迭代器

许可证：MIT