next up previous contents index
Next: Classi derivate. Polimorfismo. Streams Up: Alcuni tipi di dati Previous: Tabella   Indice   Indice analitico

Vettore di bit

Chiudiamo la nostra breve rassegna sui più comuni tipi di dati con la semplice implementazione di un vettore di bit (eng. ``bit vector''); si tratta di un tipo di dati molto importante perché trova innumerevoli applicazioni in programmi di tipo anche molto diverso. Si tratta semplicemente di un vettore, la cui particolarità è di contenere esclusivamente flags, cioè cifre binarie: 0 e 1. Essi nella pratica possono corrispondere a qualunque dato che possa assumere esclusivamente due valori: vero/falso, bianco/nero, abilitato/disabilitato, aperto/chiuso, visibile/invisibile, fisso/mobile. Inoltre è possibile rappresentare tramite un vettore di bit un insieme di proprietà, le quali sono molto comuni nelle librerie grafiche per la gestione, ad esempio, di finestre; supponiamo come esempio di volere rappresentare tramite un vettore di bit le proprietà di un tipo di carattere (font) grafico: possiamo impostare sul primo flag la proprietà ``grassetto'', sul secondo ``italico'', sul terzo ``sottolineato'' e così via con ``barrato'', ``maiuscolo'', e quanto altro necessitiamo per il nostro programma; con un solo vettore di bit possiamo accedere a tutte le proprietà in maniera sintetica e spendendo pochissimo in termini di memoria occupata visto che, come vedremo, un vettore di bit è un tipo di dato a basso costo di memoria.

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

ex-2
si completi la classe VettoreBit con le seguenti funzioni membro:


next up previous contents index
Next: Classi derivate. Polimorfismo. Streams Up: Alcuni tipi di dati Previous: Tabella   Indice   Indice analitico
Claudio Cicconetti
2000-09-06