3 Container

In our ``rationale'', we talked about an array of booleans. This is a container. A container is essentially a type (class) that comprises of components, and each component can be accessed individually. By this definition, all arrays, including the built-in one in C/C++, are containers.

To stay focused on our main objective, let us assume that the number of booleans in our array is fixed at construction time. At the minimum, we need the following class definition:

class BArray
{
    int *bits;
    unsigned size;
    static const unsigned sizeofint;
  public:
    BArray(unsigned int size);
    ~BArray(void);
};

const unsigned BArray::sizeofint = sizeof(int)*8;

BArray::BArray(unsigned int size)
{
  bits = new int[(size + sizeofint - 1)/sizeofint];
  this->size = size;
}

BArray::~BArray(void)
{
  delete bits;
}

This minimum code just keeps track of the actual size of the array, and also to dynamically allocate the storage required for storing boolean values. The destructor ensures that we deallocate the storage for boolean values.

Here comes the question of how do we access individual bits? Surely, we can simply implement two public methods as follows:

void BArray::setbit(unsigned pos, bool v)
{
  if (pos <= size)
  {
    if (v)
    {
      bits[pos / sizeofint] |= 1 << (pos % sizeofint);
    }
    else
    {
      bits[pos / sizeofint] &= ~(1 << (pos % sizeofint));
    }
  }
}

bool BArray::getbit(unsigned pos) const
{
  bool result = false;
  if (pos <= size)
  {
    return bits[pos / sizeofint] & (1 << (pos % sizeofint));
  }
}

To a C programmer, this interface is sufficient. Everything else can be done with the public interface. However, this interface is not good enough for a C++ programmer. As an array, a C++ programmer expects to use the indexing operator [] to access individual items.

Here, we have a little bit of a problem. It is easy to specify a method as follows:

int & BArray::operator [] (unsigned int i)
{
  return bits[i / sizeofint];
}

This method does, indeed, return a reference to an integer. As a result, the return value can be on the left hand side of an assignment operator. However, it returns the reference of an integer, not that of a bit in an integer. We don't have direct access to a single bit.