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, gregod at, cpdaniel at, john at