Re: [boost] boost::compressed_bitset

Subject: Re: [boost] boost::compressed_bitset
From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2009-06-11 02:52:40

2009/6/10 Jeffrey Bosboom <jbosboom_at_[hidden]>:
>> I almost exclusively use this structure in a way that interval nodes
>> represent sequences of 1 bits, but it can just as easily be used the other
>> way around, where intervals represent sequences of 0 bits. Â In fact now
>> that
>> I think about it probably doesn't even matter.
>
> Since it will use less space if the bitset is sparse with occasional 0 or 1
> bits, this sounds like a good choice for a nontype template parameter.
> Â Obviously the user could just invert the sense of the bits themselves
> (instead of representing presence in a set, it could represent "lack of
> absence"), but a template parameter would be more user-friendly. Â A
> converting constructor could be provided for converting between the two.
>

I'm not sure it's worth the complexity.  It's usually not that hard to
invert a condition in user code, since renaming the variable from
visited to pending, free to allocated, or similar makes it just about
as readable.

I remember hearing about an interval template library; Is there any
possible useful overlap here?  Also, at first glace I thought you were
talking about what I'd call a sparse_bitset, where the storage is an
optimization of a map<offset, bitset<128> >.  (Specifically I'm
thinking of the LLVM class described here:
http://llvm.org/docs/ProgrammersManual.html#dss_sparsebitvector)
Obviously the interval method is more efficient for long runs of ones,
but the offset one is much better for short runs.  Can you elaborate
more on your usage?  Should boost maybe provide both?

And out of curiosity, did you compare the T-tree to other trees?
Perhaps there's also an intrusive::t_tree hiding in here =)