I need a minimum size implementation of an array of bools. The size of the array is known at compile time.
I checked std::bitset and boost::array, but they both incur an overhead that is significant for small arrays. For example, if the array size is 8, the container should only use 1 byte of memory (assuming common CPU architecture).
Does this exist or do I need to roll my own?
You can make it by your own, but not from scratch. bitset implementation should have a couple of lines looking like typedef unsigned long _WordT; (SGI) or typedef _Uint32t _Ty; (MSVS). You could carefully replace the type and namespace and make your own container this way. I changed the type to char and sizeof returns 1 (vs2010 proof-of-concept on pastebin)
Here is a simple example. Please note that it only does what it needs to, so you won't be able to iterate it like a std::bitset.
#include <climits>
#include <iostream>
#include <cassert>
template<int S> struct boolset {
static int const SIZE = ((S / CHAR_BIT) + (0 != (S % CHAR_BIT)));
unsigned char m_bits[SIZE];
public:
boolset() : m_bits() { for(int i = 0; i < SIZE; ++i) m_bits[i] = 0; }
bool get(int i) const {
assert(i < S);
return (m_bits[i / CHAR_BIT] & (1 << (i % CHAR_BIT)));
}
void set(int i, bool v) {
assert(i < S);
if(v) { m_bits[i / CHAR_BIT] |= (1 << (i % CHAR_BIT)); }
else { m_bits[i / CHAR_BIT] &= ~(1 << (i % CHAR_BIT)); }
}
void print(std::ostream & s) const {
for(int i = 0; i < S; ++i) {
s << get(i);
}
}
};
int main(int argc, char ** argv) {
std::cout << sizeof(boolset<1>) << std::endl;
std::cout << sizeof(boolset<8>) << std::endl;
std::cout << sizeof(boolset<9>) << std::endl;
std::cout << sizeof(boolset<16>) << std::endl;
std::cout << sizeof(boolset<17>) << std::endl;
std::cout << sizeof(boolset<32>) << std::endl;
std::cout << sizeof(boolset<33>) << std::endl;
std::cout << sizeof(boolset<64>) << std::endl;
std::cout << sizeof(boolset<129>) << std::endl;
std::cout << std::endl;
boolset<31> bs;
bs.set(0, true);
bs.set(28, true);
bs.set(2, true);
std::cout << bs.get(28) << std::endl;
bs.print(std::cout); std::cout << std::endl;
bs.set(2, false);
bs.print(std::cout); std::cout << std::endl;
}
Output on ideone.
template <int N>
class BitSet {
enum { BPC = 8 }; // Bits per char, #ifdef as needed
char m_bits[ (N + (BPC-1)) / BPC ];
public:
void SetBit( int i ) { m_bits[ i / BPC ] |= 1 << (i % BPC); }
void ClearBit( int i ) { m_bits[ i / BPC ] &= ~(1 << (i % BPC)); }
int GetBit( int i ) { return (m_bits[ i / BPC ] >> (i % BPC)) & 1; }
};
Maybe if you did something like this:
#include<vector>
#include <iostream>
template<int N>
struct array
{
char bits : N;
int getNthbit(int bitnr)
{
// important to make sure bitnr is not larger than the size of the type of `bits` in number of `CHAR_BITS`
return bits & (1 << bitnr);
}
};
//Specialize for N > 8
int main()
{
std::cout << sizeof(array<8>);
}
If you look at the Live Example, you'll see when N == 8 it returns 1 for sizeof(array<8>).
When you put in 32 it returns 4.
The only thing you'd need to do is specialize the template for N > 8 so that the type changes to fit the number of bits.
I'm no template genius, maybe someone cares to write an example?
1 << bitnr is implementation-defined for large values of bitnr (large means that it overflows the int type). However, some tinkering with your Live Example shows that at least the sizeof output behaves well.Disclaimer: I extracted this answer from the OPs question. Answers should not be contained in the question itself.
Here is my final implementation based on the post of Tom Knapen. I added a default value for the constructor and added throwing in case of out-of-bounds index. Many thanks to Tom and everyone else.
#include <stdexcept>
#include <climits>
/// Minimum size container for bool-arrays
/**
* TODO: may want to add to_uint32_t accessor and the like
* for sufficently small arrays
*/
template<int SIZE>
class bitarray
{
public:
bitarray(bool initial_value = false);
bool get(int index) const;
void set(int index, bool value);
private:
static const int ARRAY_SIZE = (SIZE + CHAR_BIT - 1) / 8;
unsigned char mBits[ARRAY_SIZE];
};
// ----------------------------------------------------
// Definitions
// ----------------------------------------------------
template<int SIZE>
inline bitarray<SIZE>::bitarray(bool initial_value)
{
for(int i = 0; i < ARRAY_SIZE; ++i)
mBits[i] = initial_value ? -1 : 0;
}
template<int SIZE>
inline bool bitarray<SIZE>::get(int index) const
{
if (index >= SIZE)
throw std::out_of_range("index out of range");
return (mBits[index / CHAR_BIT] & (1 << (index % CHAR_BIT)));
}
template<int SIZE>
inline void bitarray<SIZE>::set(int index, bool value)
{
if (index >= SIZE)
throw std::out_of_range("index out of range");
if (value)
mBits[index / CHAR_BIT] |= (1 << (index % CHAR_BIT));
else
mBits[index / CHAR_BIT] &= ~(1 << (index % CHAR_BIT));
}
std:bitsetshould only use one bit per element (asstd::vector<bool>does in some implementations). How did you check that it uses more?sizeof(std::vector<bool>)it returns 40std::vector<bool>weights 40 bytes even when empty). It does not take into account the heap memory allocated for the elements themselves.