Boost logo

Boost :

From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 2002-06-17 21:33:50

a sorted vector<unsigned short> would work just fine. Which operation on
this "type" do you not believe exists? set_union(), set_difference()
already exist in <algorithm>.

At Monday 2002/06/17 12:09, you wrote:

>Has any thought been given to adding a library to support sparse bitsets
>as well as dense bitsets supported in dyn_bitset and in the standard
>Dense bitsets use 1 bit of storage for each set element, and thus are very
>space efficient if the bitset has a fairly even distribution of zeros and
>However, there are some applications where the distribution of zeros and
>ones (or present in the set vs. not present in the set) are heavily
>skewed. For example, only 10 out of 10000 members of a set may be
>present. In these cases, a sparse bit set can be more efficient in terms
>of space and time for common operations (set union, set intersection,
>etc). Sparse bitsets store the indexes of those set elements that are
>present/absent from the set. The underlying representation is
>generally something like vector<unsigned short>.
>A dense bitset is O(log2(N)) in both storage and time for all
>operations (where N is the size of the set). A sparse bitset is
>O(M) where M is the number of elements present (or not present) in the
>set. For large skewed bitsets, M can be less than log2(N).
>I have found it useful in the past to have both sparse and dense
>implementations of a bit vector with identical interfaces. Thus, the
>appropriate bit_vector implementation can be chosen based on what the
>programmer knows about the data distribution.
>For example, in the source code to the SUIF compiler from Stanford, both
>dense and sparse "natural sets" are included with identical interfaces,
>and both are heavily used in the data-flow analysis of various
>optimization passes.
>Do others feel that sparse bit sets would be useful and appropriate with
>an interface matching dyn_bitset?
>I haven't reviewed the dyn_bitset implementation so I can't give an
>opinion on it, but I did want to toss this idea out to see what people
>-Tom Wenisch
>Computer Architecture Lab
>Carnegie Mellon University
>Unsubscribe & other changes:

Victor A. Wagner Jr.
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
The five most dangerous words in the English language:
               "There oughta be a law"

Boost list run by bdawes at, gregod at, cpdaniel at, john at