Subject: Re: [boost] boost::compressed_bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-06-24 08:07:19
2009/6/11 Zachary Turner <divisortheory_at_[hidden]>
> I know there's over a zillion bitset implementations, but often times I have
> found myself in need of a bitset that is efficient (space-wise) at storing
> millions, billions, or even trillions (no joke) of bits. For this I have
> developed an in-house class which stores bits in a structure vaguely
> reminiscent of a "T-Tree" (http://en.wikipedia.org/wiki/T_tree). You can
> think of it basically as an std::map<boost::uint64_t, boost::uint64_t> where
> <key, value> represents the *interval* of bits [key, key+value-1]. So it's
> basically run-length encoded, with logarithmic lookups instead of linear
I have developed a very similar class coming form a different background.
Working on problems of date and time, I came up with a collection of
interval set and map class templates, that I have called Interval Template
It is interesting to see that the same useful data types occur and reoccur
from different problem domains. Fortunately boost is a good place to
collect, discuss and develop those useful data types.
The compressed_bitset that you are presenting seems to be similar
to the ITL's interval_set<T>. As with your class the idea is to represent
large sets in a compact way using intervals that are efficiently organized
using a balanced tree.
May be, a look at my library can be helpful for your project.
--- The current sources of the ITL are in the boost sandbox: https://svn.boost.org/svn/boost/sandbox/itl/ The latest release (3.0.0) is in the boost vault: http://sourceforge.net/projects/itl (section containers). Release 2.0.1 is available form sourceforge: http://sourceforge.net/projects/itl Online documentaiton at: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk