Looking for bitset data structure crate for storing sets of vector indices

help
1

I have some code that manipulates small vectors (<100 elements) and needs to pass around subsets of the elements of those vectors a lot in a high-performance way. It occurs to me that you can represent a subset of the elements of a vector via a bit set, where a "1" bit means the element is included in the subset and a "0" means the element is not included.

I really like the EnumSet crate for doing similar things to this, and what I want is basically just an EnumSet over the integers 0-100. Is there an existing crate that provides this functionality? Thanks!

2

I would suggest bitvec.

In particular, BitArray might be a good fit:

  • const length.
  • Can set individual bits with set.
  • Can iterate through the indexes of bits set to 1 using iter_ones.
  • Has trait implementations for bitwise operators, to do set operations.
1 Like
3

I sometimes think there are too many crates - and too many redundant methods on crates.

In this case maybe you could use u128 and twiddle the bits yourself?

 s |= 1<<k % u128::BITS  // set bit k
 s &= !(k % u128::BITS)  // clear bit k
 s & (1<<k % u128::BITS) !=0 // test if bit k is set
4

If the length of your bitvec is not const (so you can’t use BitArray) but is usually less than 63, then smallbitvec might be a good fit. This is a very small library used in Servo and Firefox.

2 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.