How to store a bit-array in C++?

Question

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>.)

Answer 1

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.

Answer 2

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);
}

Answer 3

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.

Answer 4

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.

Answer 5

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 );

Answer 6

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