Appunto. Visto che abbiamo spesso incontrato il tipo Array
, perché
semplicemente non creiamo un array di bool per ottenere il nostro
vettore di bit? Perché possiamo sfruttare la rappresentazione interna dei
numeri interi senza segno per costruire una struttura dati enormemente più
efficiente della precedente, come abbiamo già accennato nella sezione
riguardante gli operatori bit a bit. Basta dunque allocare un numero di
unsigned int sufficiente a contenere il numero di flags desiderati e
agire su di essi tramite tali operatori, i quali sono a bassissimo costo di
esecuzione perché operano praticamente a livello macchina. Siccome non
possiamo sapere su quale macchina dovrà essere compilato ed eseguito il
nostro programma, non sappiamo con certezza quanti bit vengono utilizzati per
rappresentare un unsigned int; dobbiamo allora ricorrere all'operatore
sizeof il quale, ricordiamo, restituisce a tempo di compilazione il
numero di bytes occupati dal tipo cui esso è applicato. Siccome useremo
spesso il tipo unsigned int, per brevità useremo il sinonimo
sintattico di esso: unsigned.
// vettorebit.h // classe rappresentante un vettore di bit #ifndef _VETTORE_BIT_H_ #define _VETTORE_BIT_H_ #include <iostream.h> class VettoreBit { public: VettoreBit (unsigned n); VettoreBit (const VettoreBit&); const VettoreBit& operator= (const VettoreBit&); ~VettoreBit (); unsigned quanti () const { return n_elementi; } bool operator[] (int i) const; bool modifica (int i, bool val); VettoreBit operator& (const VettoreBit&) const; VettoreBit operator| (const VettoreBit&) const; VettoreBit operator^ (const VettoreBit&) const; VettoreBit operator~ () const; private: unsigned* vettore; unsigned allocati; // numero di unsigned allocati unsigned n_elementi; // numero di elementi del vettore // funzione interna che accetta l'indice di un elemento del // vettore di bit, e salva nelle variabili a e b (passate per // riferimento) in quale elemento dell'array di unsigned si // trova l'elemento ed il suo indice void indice (int i, int& a, int& b) const { a = i / (sizeof(unsigned) * 8); b = i % (sizeof(unsigned) * 8); } }; ostream& operator<< (ostream&, const VettoreBit&); #endif // _VETTORE_BIT_H_
// vettorebit.cpp #include "vettorebit.h" VettoreBit::VettoreBit (unsigned n) { n_elementi = n; // 1 byte = 8 bits allocati = 1 + n_elementi / (sizeof(unsigned) * 8); vettore = new unsigned[allocati]; for (int i = 0; i < allocati; i++) vettore[i] = 0; // 000...0 } VettoreBit::VettoreBit (const VettoreBit& v) { n_elementi = v.n_elementi; allocati = v.allocati; vettore = new unsigned[allocati]; for (int i = 0; i < allocati; i++) vettore[i] = v.vettore[i]; } const VettoreBit& VettoreBit::operator= (const VettoreBit& v) { if (&v != this) { if (allocati != v.allocati) { delete[] vettore; allocati = v.allocati; vettore = new unsigned[allocati]; } n_elementi = v.n_elementi; for (int i = 0; i < allocati; i++) vettore[i] = v.vettore[i]; } return *this; } VettoreBit::~VettoreBit () { delete[] vettore; } bool VettoreBit::operator[] (int i) const { if (i < 0 || i >= n_elementi) return false; int a, b; indice(i, a, b); // creiamo una maschera per il confronto bit a bit unsigned m = 1; // 000...001 m <<= b; if ((vettore[a] & m) == 0) return false; return true; } bool VettoreBit::modifica (int i, bool val) { bool vecchio_valore = operator[](i); if (i >= 0 && i < n_elementi) { int a, b; indice(i, a, b); unsigned m = 1; // maschera binaria: 000...001 m <<= b; if (val == true) vettore[a] |= m; else { m = ~m; vettore[a] &= m; } } return vecchio_valore; } VettoreBit VettoreBit::operator& (const VettoreBit& v) const { VettoreBit tmp(*this); if (allocati == v.allocati) { for (int i = 0; i < allocati; i++) tmp.vettore[i] &= v.vettore[i]; } return tmp; } VettoreBit VettoreBit::operator| (const VettoreBit& v) const { VettoreBit tmp(*this); if (allocati == v.allocati) { for (int i = 0; i < allocati; i++) tmp.vettore[i] |= v.vettore[i]; } return tmp; } VettoreBit VettoreBit::operator^ (const VettoreBit& v) const { VettoreBit tmp(*this); if (allocati == v.allocati) { for (int i = 0; i < allocati; i++) tmp.vettore[i] ^= v.vettore[i]; } return tmp; } VettoreBit VettoreBit::operator~ () const { VettoreBit tmp(*this); for (int i = 0; i < allocati; i++) tmp.vettore[i] = ~vettore[i]; return tmp; } ostream& operator<< (ostream& os, const VettoreBit& v) { for (int i = 0; i < v.quanti(); i++) os << v[i]; return os; }
Un programma che mostri l'utilizzo di VettoreBit
è il seguente:
// ex11_5_1.cpp #include "vettorebit.h" void main() { VettoreBit v(40); for (int i = 0; i < 40; i+=3) v.modifica(i, 1); cout << v << "\n"; for (int i = 0; i < 40; i+=4) v.modifica(i, 0); cout << v << "\n"; VettoreBit a(5); a.modifica(0, 1); a.modifica(3, 1); cout << "a:\t" << a << "\n"; VettoreBit b(a); b.modifica(0, 0); b.modifica(1, 1); b.modifica(4, 1); cout << "b:\t" << b << "\n"; cout << "a & b:\t" << (a & b) << "\n"; cout << "a | b:\t" << (a | b) << "\n"; cout << "a ^ b:\t" << (a ^ b) << "\n"; cout << "~a:\t" << (~a) << "\n"; }
output:
1001001001001001001001001001001001001001 0001001001000001001001000001001001000001 a: 10010 b: 01011 a & b: 00010 a | b: 11011 a ^ b: 11001 ~a: 01101
VettoreBit
con le seguenti funzioni membro:
void ridimensiona(int n)
: modifica il vettore di bit in modo tale
che esso contenga n
flags;void azzera()
: imposta tutti i flags del vettore di bit a zero;void inverti()
: inverte l'ordine dei flags del vettore di bit;VettoreBit& operator+= (const VettoreBit& v)
: modifica il vettore
di bit in maniera tale che v
risulti ad esso concatenato;int zeri() const
: restituisce il numero di zeri nel vettore di
bit;operator char*() const
: operatore di conversione a
char*
; restituisce una stringa contenente il vettore di bit;