Re: Challenge: bit_vector/bit_string

From: boost_at_[hidden]
Date: 2001-05-14 08:59:52

--- In boost_at_y..., Gerhard Wesp <gwesp_at_c...> wrote:
> > *  It forces a space optimization on the user.
> > 
> > The first problem might be solved by relaxing the requirements, 
but that 
> > doesn't solve the second problem.
> 
> The user is free to use vector<char> or vector<int> if the space
> optimization isn't wanted.

Except that potentially has a performance overhead of it's own.
The compiler doesn't know that the widgets in you vector<some-other-
type> are boolean, so potentially has to check the values when you 
get them out, e.g.

vector<int> vi;
// ...
bool b = vi[0];  // which becomes "b = ( vi[0] ? true : false );"

So forcing people to use vector<char> or vector<int> [or whatever] is 
punishing them more twice over.

> 
> > Good question. I don't know the answer.  Does anyone have real-
world 
> > examples (NOT GUESSES!) as to how people are using vector<bool>?
> 
> well, personally i used it for a prime sieve and for an application
> where it was necessary to count the number of certain parts of a 
cube hit
> by a point sequence.  in both cases, the space optimization was 
nice to
> have.

The prime sieve is a great example of how a benchmark can make 
certain tradeoffs look good. Tweak the size of your sieve until there 
are too many bits for the thing to fit in CPU cache and watch what 
happens :-)

Regards,
 Andy Sawyer