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?
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>.)
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.
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 );
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.
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.
vector<bool>? –
Valtin 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. –
Allard CHAR_BIT or something like that instead of assuming that the byte size is 8 bit. –
Oliviaolivie 0x7, I'd probably need a class that can determine which hex to use and work from there. Unless someone can convert CHAR_BIT to 0xCHAR_BIT-1 easily. –
Allard (CHAR_BIT-1). But you could no longer use bitwise AND as a faster modulo. Using only 8 bits per byte is fine, any wasted space will be more than compensated for by the increased speed. –
Demonstrator #if (CHAR_BIT != 8) #error. –
Immobile 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.
vector<bool> is that: vector<bool> must die. –
Mastiff vector<bool> bitvector, or what you want. –
Mastiff 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);
}
items.assign(myArray, numBits), which would turn out to be more practical, but I couldn't find it. –
Valtin Powerful C/С++ bit array library: https://github.com/noporpoise/BitArray
© 2022 - 2024 — McMap. All rights reserved.
std::dynamic_bitset... – Randidynamic_bitsetis in Boost. – Varicoloredvector<bool>, unless you expect it to behave like a standard container. – Sanburnvector<bool>, then, how should I copy to it the data from a byte array? (I had trouble figuring this out -- doing it bool-by-bool is very slow because of locking issues, so I'm hoping for a bulk operation.) – Valtinbool, but there are many ways in which it breaks expectations. For one, you cannot take the address of the first element and have a contiguous array of bool, as you can with every other vector. And even though you know the internal representation is an array of bytes, there's no way to access it. P.S. if you ever really need a vector of boolean values that acts like a true vector, usevector<char>and be aware that it will use 8 times memory of a more optimized solution. – Sanburndynamic_bitsetfrom Boost seems like a good candidate. But since you don't want Boost, can't you just get that small part from Boost, or copy just that part to a separate library? – Sluggish