Expand description
Fast implementation of vEB trees without internal allocation.
van Emde Boas tree is a data structure for maintaining a set of integers of bounded size supporting the following queries:
- insert(x) - inserts the integer x into the set
- remove(x) - removes the integer x from the set
- contains(x) - returns whether the set contains x
- next(x) - returns the smallest integer in the set that is greater or equal to x
- prev(x) - returns the smallest integer in the set that is greater or equal to x
All of these use $\mathcal{O}(\log \log U)$ time, and the structure uses $\mathcal{O}(U)$ space, where $U$ is the biggest integer you can put in the set.
Usage
use the trait VEBTree
and the type VEBTreeX
where X is the number of bits in the elements you will insert.
In other words, with VEBTreeX
you can only insert elements with
value less than 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
Performance
It is natural to use internal heap allocation and indirection to implement recursive data structures like vEB tree, but this implementation avoid that to be faster, at the cost of a bit cumbersome API.
A BTreeSet can do all of the operations a vEB tree can and much more, but is slower. A vEB tree is more appropriate if there are enough operations that the speed improvement matters, but the integers are small enough that the vEB tree doesn’t take too much space.
vEB tree is about 10 times faster than BTreeSet on tests downloaded from https://judge.yosupo.jp/problem/predecessor_problem, but this includes IO, which is probably a significant amount of the time spent for the vEB tree. Better benchmarks are needed.
Todo
- better benchmarks
- create a function to return a Box
of appropriate capacity - reverse iterator
Structs
This struct is created by the iter method on objects implementing VEBOperations
Traits
Common trait for the different implementations of sets for different sizes.