Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk