Minimum size implementation for bool array

bit-manipulation, c++

Solution

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.

Problem

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?

Original source