Something in between traditional bit vectors and sparse sets is described here:<p><a href="http://upcoder.com/9/fast-resettable-flag-vector/" rel="nofollow">http://upcoder.com/9/fast-resettable-flag-vector/</a><p>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.