c++ - ブール配列の最小サイズの実装

Question

ブール配列の最小サイズの実装が必要です。配列のサイズはコンパイル時にわかります。

と を確認std::bitsetしboost::arrayましたが、どちらも小さい配列ではかなりのオーバーヘッドが発生します。たとえば、配列サイズが8の場合、コンテナーは1 バイトのメモリのみを使用する必要があります (一般的な CPU アーキテクチャを想定)。

これは存在しますか、それとも自分でロールバックする必要がありますか?

Answer 1

自分で作成することはできますが、最初から作成することはできません。実装には、 （SGI）または（MSVS）bitsetのように見える2行が必要です。タイプと名前空間を慎重に置き換えて、この方法で独自のコンテナを作成できます。タイプをcharに変更し、1を返します（pastebinのvs2010概念実証）typedef unsigned long _WordT;typedef _Uint32t _Ty;sizeof

Answer 2

簡単な例を次に示します。必要なことだけを行うので、 のように繰り返すことはできないことに注意してください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 3

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

Answer 4

たぶんあなたがこのようなことをしたなら：

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

ライブの例を見ると、いつN == 8戻ってくる1かがわかりますsizeof(array<8>)。

32を入れると、4が返されます。

あなたがする必要がある唯一のことはN > 8、ビット数に合うようにタイプが変わるようにテンプレートを特殊化することです。

私はテンプレートの天才ではありません、多分誰かが例を書くことを気にしますか？