Re: [boost] powerset

From: spamjunk_at_[hidden]
Date: 2002-08-28 15:45:34

> Also (albeit without having put much thought into it) it seems to me that 
> there ought to be a lot of overlap with bitset/dyn_bitset/etc.  Can all of 
> these be rolled into one somehow?
> 
> Dave
> 

The discrete_set is a very different animal than bitset, vector<bool>, et al.

bitset is meant for "bit-fiddling" is a set only in the sense of "a group of
bits."  It doesn't supply operators for handling set operations (unless you
count &=, |=, ^=).  It similarility to discrete_set is only in how data is
stored in it.  They have different implementations, interfaces, and goals.

vector<bool> is also only similar in how it stores data.  It is also not a set;
it is a bit array, similar in nature to Ada's bit array.  It is also a dynamic
creature.  As an embedded programmer, I stay away from heap allocation if there
is an equivalent or better implementation that doesn't use the heap.

I wrote discrete_set because I needed a fast and compact class for manipulating
sets where the set's universe was a collection discrete values.  I also wanted
to be able to "bind" the set class to an element type for type safely.  The fact
that it stores the elements at the bit level was done to save space and facilite
the operating on multiple elements with a single machine instruction.

When I was first started designing the class, I looked at bitset and
vector<bool> for a possible base class, but quickly resolved not to. 
vector<bool> I dismissed quickly for it used heap allocation.  Since I required
only sets where the number of elements was known at compile-time, I didn't need
it.  Also, vector<bool> only allows access to one bit at a time which would make
for very slow operations.  bitset took a little longer for me to dismissed.  But
I ultimately did because the goal of that class was to create a group of easily
manipulated bit that fit into a machine word.  Hence, bitset is meant for a
small number of bits.  Beyond the first number of bits that fit into an unsigned
long int, bitset only allows access to the bits individually and would suffer
from the same loss in performance as vector<bool>.

regards, 
Rich
pop-server.stny.rr.com