Challenge: bit_vector/bit_string

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-05-10 15:37:47

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>?

--Beman