12

What's the best way to store a bit array in C++ (no Boost, just standard containers), representing, for example, a volume allocation bitmap?

I thought std::vector<bool> was a great idea, but apparently it's Evil and deprecated, so is there a better choice?

Also:

If I have a byte array in memory, how would I go about copying them to the recommended container?
(I'm having trouble figuring this out for vector<bool>.)

14
  • 1
    The article you linked to recommends std::dynamic_bitset... Commented Oct 20, 2011 at 0:41
  • @GregHewgill: That doesn't seem to be in standard C++...? Or am I just not finding it? Commented Oct 20, 2011 at 0:44
  • It's not that evil if you don't need flip() or other special behavior. :P Commented Oct 20, 2011 at 0:53
  • 1
    dynamic_bitset is in Boost. Commented Oct 20, 2011 at 0:53
  • 6
    There's nothing wrong with vector<bool>, unless you expect it to behave like a standard container. Commented Oct 20, 2011 at 0:53

6 Answers 6

3

For vanilla C++, there's std::bitset.

Bitset is very similar to vector (also known as bit_vector): it contains a collection of bits, and provides constant-time access to each bit. There are two main differences between bitset and vector. First, the size of a bitset cannot be changed: bitset's template parameter N, which specifies the number of bits in the bitset, must be an integer constant. Second, bitset is not a Sequence; in fact, it is not an STL Container at all.

Matt Austern has a nice article on its use.

Also: If your byte array (bit array?) fits into an unsigned long, then you can assign it to a std::bitset directly:

unsigned long myByteArray = 0xABCD;
std::bitset<32> bitten( myByteArray );
Sign up to request clarification or add additional context in comments.

Comments

3

Just posting this 6 years later for posterity: like one of the commenters said, I came to the conclusion that it's perfectly fine to use std::vector<bool> as its own specialized type. The only thing you need to be careful of is not to treat it like a standard bool container, since it isn't.

Comments

2

The std::bitset will do, as long as your bit array is of fixed size.
As a side note there's also std::dynamic_bitset, but am not 100% sure it made it into the standard.

4 Comments

Nah, the size is variable, like in my example (volume bitmap).
@Mehrdad: then just use vector<bool> as long as you understand how it differs from the "regular" vector<T>. If you choose to implement such a bit array yourself you'll probably just reinvent vector<bool>, just with a less confusing name.
@EugenConstantinDinca The issue with using vector<bool> is that: vector<bool> must die.
@EugenConstantinDinca Just rename vector<bool> bitvector, or what you want.
2

a char array and then masking by 0x1 will act as a bit array.

Example:

char bitarray[4]; // since 4*8 this array actually contains 32 bits

char getBit(int index) {
    return (bitarray[index/8] >> 7-(index & 0x7)) & 0x1;
}

void setBit(int index, int value) {
    bitarray[index/8] = bitarray[index/8] | (value & 0x1) << 7-(index & 0x7);
}

of course these operations are usually comparatively slow, but if memory is an issue this is a decent way to go. I chose char's for this to reduce the number of shifts needed. However it may still be faster with integers.

7 Comments

Sure, I could implement it myself, but how is that beneficial to using vector<bool>?
you quoted a perfect example of why you should not use vector<bool>, this does not suffer from its downfall and if you wish you can also address your array in 4 bit chunks, which can be handy in some situations. I am not a C/C++ guru but this just seems more correct, since bool was a hack in C anyway.
yeah, wow, how did I mess that up, thanks for pointing that out. fixes
Actually you should use CHAR_BIT or something like that instead of assuming that the byte size is 8 bit.
It would be difficult to justify doing anything more than: #if (CHAR_BIT != 8) #error.
|
0

I think some of the points made on the site you linked to are not correct by the way. On almost every computer the size of a bit is really one byte (same as a character) because computers can only address a byte not a bit within a byte (if you could then you would only have one eighth of the addressing space you currently have with bytes)

I would just use a byte for your vector because it gives other people who read your code a better idea of the memory footprint of your application.

Ram is very plentiful in modern computers so you may be able to use larger integral types but realistically you can't go smaller than a byte.

To copy data from one container to another first create an iterator for the container

vector::iterator myItr = myVector.begin()

and iterate through the vector with a while loop or a for loop until myItr reaches myVector.end().

For example

for(vector<bool>::iterator myItr = myVector.begin(); myItr<myVector.end(); ++myItr)
{
   otherContainer.append(*myItr);
}

2 Comments

The trouble with copying data like that^ is that it's painfully slow. Not just because it's bit-by-bit, but because implementations (e.g. Visual C++) sometimes arbitrarily decide to lock a critical section on every single access, so it becomes ridiculously impractical. I was looking for a bulk movement operation (something like items.assign(myArray, numBits), which would turn out to be more practical, but I couldn't find it.
"_the size of a bit _" Hug? What do you mean?
0

Powerful C/С++ bit array library: https://github.com/noporpoise/BitArray

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.