
Boost : 
From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 20020617 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
>bitset?
>
>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
>ones.
>
>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 dataflow 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
>thought.
>
>Regards,
>Tom Wenisch
>Computer Architecture Lab
>Carnegie Mellon University
>
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Victor A. Wagner Jr. http://rudbek.com
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP DH 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk