pola bitowe, vector<bool>, wlasna implementacja..

czy ktoś z was miałby jakiś pomysł jak zrobić tablice pól bitowych, gdzie kazde pole bitowe bylo by typu unsigned int:1 ?

unsigned int tab[32]:1; //nie dziala
unsigned int tab[32]:32; //też nie dziala

probowalem opakowac to w strukture

struct a{
unsigned int _a:1;
}

lecz potem jak mialem
struct b{
a tab[32];
}

sizeof(b);// u mnie 128, nie 32...

nie wchodzi w gre użycie vector<bool> (ktory jest niby odpowiednio zaimplementowany, ale nie dla mnie), potrzebuje to zrobić sam...
ktos się może orientuje jak zaimplementowana jest specjalizacja klasy vector dla bool (tak zeby bool zajmowal jeden bit nie bajt)? pewnie pewne sztuczki z tej implementacji by się przydały..

[EDIT]

tak sobie teraz pomyślałem, że stricte jako tablicy się tego zapisac nie da...tablica, a przynajmniej jej nazwa to jakby wstaly wskaznik na poczatek..zatem t[i] to tak jakby t+i, gdzie t+i wskazuje na jakiejs miejsce w pamieci...niby ok...ale nie bardzo...skoro wskazuje, to posiada adres jakiegos konkretnego miejsca..I tu jest problem...adresy wskazuja na bajty nie bity...wiec chyba tego jako tablicy nie da sie zrobic... :/

wiec teraz juz faktycznie sie to sprowadza do tego....jak tworcy klasy vector<bool> napisali specjalizacje, ze bool zajmuje u nich wtedy tylko jeden bit?

....jak tworcy klasy vector<bool> napisali specjalizacje, ze bool zajmuje u nich wtedy tylko jeden bit?

uzyli vector<char> o wielkosci N/8 i nadpisali operator[](int n) tak aby bral n/8-ty bajt a nastepnie zwracal n%8-ty bit z tego bajtu..

no cóż, ogólna idea:

class pole {
   uint32_t values[64];
   public: bool& operator[](int index) {
      int nr_bajtu = index/32;
      int nr_bitu = index%32;
      return values[nr_bajtu] & (1<<nr_bitu);
      }
   };

oczywiście idea idzie się paść, bo zwracamy (liczba1 & liczba2). Czyli dobrze ustawioną wartość bita, ale do tego referencji to się zwrócić nie da :(

Rzuciłem okiem do nagłówka implementacji STL Hewlett-Packarda. Tak tylko rzuciłem, i widzę, że u nich idea została rozszerzona na:

class pole {
   uint32_t values[64];
   public: my_bool operator[](int index) {
      int nr_bajtu = index/32;
      int nr_bitu = index%32;
      return my_bool( values+nr_bajtu, 1<<nr_bitu );
      }
   };

a typ my_bool jest po prostu strukturą udającą referencję do bool.

struct my_bool {
    uint32_t* value;
    uint32_t maska;

    my_bool(uint32_t* _value, uint32_t _maska) :
        value(_value), _maska(maska) { }
        
    my_bool() : value(NULL), maska(0) { }
    
    operator bool() const {
        return (*value & maska); 
        }
    my_bool& operator=(bool x)  {
        if(x) *value |= maska;
        else *value &= ~maska;
        return *this;
        }    
    my_bool& operator=(const my_bool& x) {
        return *this = bool(x); 
        }
    bool operator==(const my_bool& x) const {
        return bool(*this) == bool(v); 
        }
    };

czyli nie tyle pola bitowe, co ręczna zabawa operatorami bitowymi jest używana.

(fuck! żebym sobie ze znacznikiem nie mógł poradzić... :/)</cpp>

quetzalcoatl: szybciej dałeś, ale nie dałeś myka kluczowego IMHO, jak właśnie referencję do tego "bita" zwrócić ;P

widzisz, magik nie powinien od razu ujawniac wszystkich trickow :)

Kiedyś potrzebowałem szybkiej struktury do realizacji:
-testowania czy dany bit jest równy 1
-do zerowania bitu(na początku zapełniłem wszystko jedynkami za pomocą memset(..,0xFFu,..);

Okazało się, że moja implementacja jest o około 40% szybsza od vector<bool>. (Nawet utworzonego za pomocą vector<bool>(MAX_N, true); bez używania push_backów)
Nie używam w ogóle operacji *, /, %.

Wiem, że to nie C++, a C, ale zawsze. Dorzucę też ustawianie na true.

#define MAX_N 100000000

#define UI unsigned int
#define UC unsigned char
#define ST_TYP UI

ST_TYP v[MAX_N/(8*sizeof(ST_TYP)) + 1];

UC* v_c = (UC*)(&v[0]);

inline bool test(UI i){
	return ((v_c[i>>3] >> (i & 7u)) & 1);
}

inline void set_false(UI i){
	v_c[i>>3] &= (~(1 << (i & 7u)));
}

inline void set_true(UI i){
	v_c[i>>3] |= (1 << (i & 7u));
}

a porownywales z bit_vector<N> ?

quetzalcoatl napisał(a)

a porownywales z bit_vector<N> ?

Mam gcc 4.1.3 i dostaję taki błąd:

error: bit_vector.h: No such file or directory
error: ‘bit_vector’ does not name a type

Jednak sprawdziłem i:

vector<char> a(100000000); zajmuje około 100MB
vector<bool> a(100000000); zajmuje około 14MB

http://www.sgi.com/tech/stl/bit_vector.html

The name bit_vector will be removed in a future release of the STL. The only reason that bit_vector is a separate class, instead of a template specialization of vector<bool>, is that this would require partial specialization of templates.

__krzysiek85 napisał(a)

http://www.sgi.com/tech/stl/bit_vector.html

The name bit_vector will be removed in a future release of the STL. The only reason that bit_vector is a separate class, instead of a template specialization of vector<bool>, is that this would require partial specialization of templates.

hm.. warte zapamietania, thx