Re: Challenge: bit_vector/bit_string

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-05-12 07:43:48

on 5/10/01 4:37 PM, Beman Dawes at bdawes_at_[hidden] wrote:

> Of the 300 defects reported so far for the C++ Standard Library, most are
> pretty trivial, but one stands out as a more serious mess.  This is the
> vector<bool> specialization, which has at least two serious problems:
> 
> *  It doesn't meet the Standard Library's own requirements for a container
> (because element access returns a proxy).
> 
> *  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.
> 
> While the total solution to the vector<bool> problem is still unclear, part
> of the solution may be to provide a new class for those who do wish the
> space optimization.
> 
> The Standard Library once had such a class, named bit_string.  (It was in a
> header named <bitstring>, spelled with no "_", for reasons I can't
> remember.)  The class was removed from the library because it was assumed
> to be replaced by vector<bool>.
> 
> I exchanged email with Chuck Allison, the original author of bit_string, to
> see if he was interested in a Boost submission, and wondering about string
> vs iterator style interface.  Chuck is interested, and hopefully will join
> Boost.  He comments:
> 
> It seems to me that the first order of business is to answer
> the question of why we need the class (i.e., what purpose does
> it serve?) before we even consider interface style. Originally
> I developed the class to support efficient user interface widgets,
> like picklists (it seemed like a common sort of need).
> 
> How are people using vector<bool> now, anyway?
> 
> Good question. I don't know the answer.  Does anyone have real-world
> examples (NOT GUESSES!) as to how people are using vector<bool>?

I'm not sure this counts as an example, but I'm curious about what
bit_string is like.  I have an (inactive) project for an arbitrary-precision
integer type for Boost.  It strings together many bits for the value.  I've
had two choices for the bit container:

1.  vector<bool> since it stores the bits compactly
2.  deque<bool> to allow inserts from either end (for shifts)

If bit_string could provide compact representation with efficient pushing
(and popping) from either end, it would be great!

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com