vector<bool>, bit_vector, or something else?

[Scott Brady Drummonds]

Hi, everyone,

I have a program in which I need to store a series of Boolean values. A
vector<bool> would be ideal. However, I'm concerned about this data
structure because of Scott Meyers' Effective STL's Item 18: Avoid using
vector<bool>.

Plus, I'm loath to use bit_vector since SGI's STL implementation says it
will soon be dropped on the floor
(http://www.sgi.com/tech/stl/bit_vector.html).

Additionally, the bitset won't work because I don't know the number of
values I'll need at compile time. Lastly, Meyers' recommendation of using a
dequeue<bool> scares me a little because it appears that it won't pack the
sequence of bools into bits the way that a bitset does (and, frankly, the
way I'd like my data structure to do since there may be a lot of flags in
this container.)

What is the best way to compactly store a sequence of on/off flags and allow
for indexed addressing?

Thanks,
Scott

 

[Howard Hinnant]

| Hi, everyone,
|
| I have a program in which I need to store a series of Boolean values. A
| vector<bool> would be ideal. However, I'm concerned about this data
| structure because of Scott Meyers' Effective STL's Item 18: Avoid using
| vector<bool>.
|
| Plus, I'm loath to use bit_vector since SGI's STL implementation says it
| will soon be dropped on the floor
| (http://www.sgi.com/tech/stl/bit_vector.html).
|
| Additionally, the bitset won't work because I don't know the number of
| values I'll need at compile time. Lastly, Meyers' recommendation of using a
| dequeue<bool> scares me a little because it appears that it won't pack the
| sequence of bools into bits the way that a bitset does (and, frankly, the
| way I'd like my data structure to do since there may be a lot of flags in
| this container.)
|
| What is the best way to compactly store a sequence of on/off flags and allow
| for indexed addressing?

With all due respect to Mr. Meyers, std::vector<bool>.

Did the committee screw up when they created vector<bool> as opposed to
bitvector? Yes. But the functionality afforded by vector<bool> is
useful nonetheless. It just has a bad name, that's all.

A future standard might deprecate vector<bool>, but at the same time
introduce bitvector. There's no way (imho) that we will deprecate
vector<bool> without reintroducing that same functionality under a
different name. People need it.

You might protect yourself a bit with:

typedef std::vector<bool> MyVectorBool;

And then use MyVectorBool religiously. Then should you be on a
platform that offers bitvector, or should the standard change out from
under you, your maintenance can be easily accomplished during or after
a three martini lunch with a single change.

Don't be afraid of vector<bool> for the functionality it offers. It is
good stuff. Be wary of vector<bool> because it differs in subtle ways
from vector<int>. And I think that is probably the point to take away
from Scott's ESTL #18.

 

[Jerry Coffin]

Hi, everyone,

I have a program in which I need to store a series of Boolean values. A
vector<bool> would be ideal. However, I'm concerned about this data
structure because of Scott Meyers' Effective STL's Item 18: Avoid using
vector<bool>.

Additionally, the bitset won't work because I don't know the number of
values I'll need at compile time. Lastly, Meyers' recommendation of using a
dequeue<bool> scares me a little because it appears that it won't pack the
sequence of bools into bits the way that a bitset does (and, frankly, the
way I'd like my data structure to do since there may be a lot of flags in
this container.)

What is the best way to compactly store a sequence of on/off flags and allow
for indexed addressing?

....and another container that packs the bits won't likely be any better
than vector<bool> anyway.

It comes down to a simple choice: you can leave the bools unpacked, and
get normal semantics for the container. You can pack the bools, and get
compact storage. At least the way C++ is defined right now, I don't
know of a way to pack the bools one per bit, and still get normal
semantics for the container, so if packed bools is what you want, then
vector<bool> is at least as good as most of the alternatives.

 

[Evan]

vector<bool>.

I agree. As long as you're aware of the differences with the <bool>
specialization, you should be fine.