Considering the nested array (indirection) this doesn’t seem that attractive for testing membership/insertion compared to a hashset. What am I missing?
Compared to a hash table, the binary array set: Has better worst-case insertion and search time, has zero slack space, and relies on comparisons rather than hashing.
No need for a nested array. You can simply lay them end to end in decreasing size and perform in-place merges. The structure is implicit in the size of the set.
Comments
Considering the nested array (indirection) this doesn’t seem that attractive for testing membership/insertion compared to a hashset. What am I missing?
Compared to a hash table, the binary array set: Has better worst-case insertion and search time, has zero slack space, and relies on comparisons rather than hashing.
No need for a nested array. You can simply lay them end to end in decreasing size and perform in-place merges. The structure is implicit in the size of the set.
Okay, I was looking at the Rust implementation (nested Vec).