Comment on Using Uninitialized Memory for Fun and Profit (2008)Comments−crispweed11ySomething in between traditional bit vectors and sparse sets is described here:http://upcoder.com/9/fast-resettable-flag-vector/This is designed for a fast clear, but doesn't actually have constant time clear, it's just O(n) clear with very small (amortized) constant. It's a bit more cache friendly, though, I think, and gave us some nice speedups in practice.
Comments
Something in between traditional bit vectors and sparse sets is described here:
http://upcoder.com/9/fast-resettable-flag-vector/
This is designed for a fast clear, but doesn't actually have constant time clear, it's just O(n) clear with very small (amortized) constant. It's a bit more cache friendly, though, I think, and gave us some nice speedups in practice.