Minimale Größe Implementierung für Bool-Array

Question

Ich brauche eine minimale Größe Implementierung einer Reihe von Bools. Die Größe des Arrays ist zur Kompilierzeit bekannt.

Ich überprüfte std::bitset und boost::array, aber beide verursachen einen Overhead, der für kleine Arrays von Bedeutung ist. Wenn die Array-Größe beispielsweise ist, sollte der Container nur 1 Byte des Arbeitsspeichers verwenden (unter der Annahme einer gemeinsamen CPU-Architektur).

Gibt es das oder muss ich meine eigenen rollen?

BEARBEITEN: Hier ist meine endgültige Implementierung basierend auf dem Beitrag von Tom Knapen. Ich habe einen Standardwert für den Konstruktor hinzugefügt und im Falle eines Out-of-Bounds-Indexes das Argument hinzugefügt. Vielen Dank an Tom und alle anderen.

#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

Hier ist ein einfaches Beispiel. Bitte beachten Sie, dass es nur das tut, was es benötigt, so dass Sie es nicht wie ein std :: bitset durchlaufen können.

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

Ausgabe auf ideone.

Answer 2

Vielleicht, wenn Sie so etwas wie dies tat:

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

Wenn man sich die Live Example betrachten, sehen Sie, wenn N == 8 es 1 für sizeof(array<8>) zurückgibt.

Wenn Sie in 32 legte es zurück 4.

Das einzige, was Sie tun müssen, würde, ist die Vorlage spezialisiert für N> 8, so dass die Art ändert die Anzahl der Bits passen.

Ich bin kein Template-Genie, vielleicht interessiert es jemanden, ein Beispiel zu schreiben?

Answer 3

Sie können es selbst machen, aber nicht von Grund auf neu. bitset Implementierung sollte ein paar Zeilen wie typedef unsigned long _WordT; (SGI) oder typedef _Uint32t _Ty; (MSVS) aussehen. Sie können den Typ und den Namespace sorgfältig ersetzen und auf diese Weise Ihren eigenen Container erstellen. Ich änderte den Typ char und sizeof gibt 1 (VS2010 Proof-of-concept auf 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; } 
};