Реализация минимального размера для массива bool

Question

Мне нужна реализация минимального размера массива bools. Размер массива известен во время компиляции.

Я проверил std::bitset и boost::array, но они оба несут накладные расходы, что важно для небольших массивов. Например, если размер массива равен , то в контейнере должно использоваться только 1 байт памяти (при условии общей архитектуры ЦП).

Означает ли это, нужно ли мне рулон самостоятельно?

EDIT: Вот моя окончательная реализация, основанная на посту Тома Кенапена. Я добавил значение по умолчанию для конструктора и добавил бросание в случае индекса вне пределов. Огромное спасибо Тому и всем остальным.

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

Answer 1

Вот простой пример. Обратите внимание, что он выполняет только то, что ему нужно, поэтому вы не сможете повторять его как 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; 
} 

Выход на ideone.

Answer 2

Может быть, если ты сделал что-то вроде этого:

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

Если вы посмотрите на Live Example, вы будете видеть, когда N == 8 возвращает 1 для sizeof(array<8>).

Когда вы кладете в 32 он возвращает 4.

Единственное, что вы должны были бы сделать, это специализировать шаблон для N> 8, так что изменения типа, чтобы соответствовать число битов.

Я не гениальный шаблон, может быть, кто-то хочет написать пример?

Answer 3

Вы можете сделать это самостоятельно, но не с нуля. bitset реализация должна иметь пару строк, похожих на typedef unsigned long _WordT; (SGI) или typedef _Uint32t _Ty; (MSVS). Вы можете тщательно заменить тип и пространство имен и создать свой собственный контейнер таким образом. Я изменил тип СИМВОЛ и sizeof возвращает 1 (VS2010 проверки концепции на pastebin)

Answer 4

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