Vector of Bools

This is the last assignment that will focus on our Vector template. There is one more specialization that we can provide to optimize the storage of our vectors, and that is a Vector<bool> specialization. Typically, each bool value will take up one byte, which means if we want to use our Vector template to represent a bit-vector, we will lose quite a bit of space. Instead, we will use a packed representation where we represent each bool with a specific bit in a vector of unsigned integers.

Obviously, it will be helpful to know how many bits are in the unsigned integers we decide to use. We will keep it simple and use the <cstdint> header, which defines types like uint32_t (a 32-bit unsigned integer). Of course, we could code our program to use any unsigned integer type; for example, if we used unsigned int as our type, we know that each value will hold 8 * sizeof(unsigned int) bits. We can in fact write all of our code in terms of expressions like this, so that our vector doesn't care what size the elements are that it uses.

Our Vector<bool> specialization should be able to take advantage of last week's refactoring of the vector code into a base-class that handles common operations. The vector can use uint32_t as the element type, and then map accesses to specific bits into this vector of uint32_ts. The mapping should be easy to figure out: if the bit at index i is being accessed, the bit will be stored in element i / 32, at position i % 32. (Again, you can code these things to be independent of the size of the element, so that it can be changed easily.) You will need to use bit-shift operations and the bitwise operators to read or write individual bits.

Supporting Access and Mutation of Bits

Supporting mutation of individual bits will take a bit of extra work. The reason why is that operators like the [] indexing operator must return a value that can be the target of an assignment; i.e. an lvalue. And, there is no way in C++ to return a reference to an individual bit within a larger value. Therefore, you will need to create a helper class that can be returned by the vector's non-const [] operator, that can write to a specific bit in the vector.

This helper class will obviously need to manipulate the internals of the vector's data structure, which means that it will either need to be a friend of the vector class, or it will need to be declared as a nested class within the template. (The second option is probably the easiest, given that we are working with a template.) The helper class can receive a reference to the vector, along with the index of the bit that will be written to. Then, it can implement the operator=(bool) assignment operator, setting the specified bit on the vector. Once this is done, you should be able to handle operations like this:

  Vector<bool> v(100);
  v[315] = false;

Note that your Vector<bool> specialization should also provide a const version of the [] operator that simply returns a bool, for the common case of reading a bit from the vector. It would be too expensive to return a whole object to handle this case.

Iterators

Once you support mutation of bits, iteration shouldn't be much harder to support. Again, you will need a helper class, since there is no way that you can return a pointer to a specific bit within an integer. Recall that iterators are a generalization of pointers, so your iterator class needs to support increment (pre and post), decrement (pre and post), and the dereference operator *. As with the assignment-helper class, this class needs to hold a reference to the vector, along with the index of the bit that is currently "pointed to" by the iterator. All operations are very straightforward to implement:

Don't forget that the increment and decrement operators must return a value (see lecture 1, slides 20-25 for details). The value returned by the operator will also be an iterator (either the same iterator, or a copy of the iterator with the old values); this is important so you can support operations like "postincrement-and-assign," e.g. "*it++ = false;".

All Done!

Once you have the above functionality working, you can submit your final vector template (which should include the general template, the partial specialization for pointers, and the specialization for bool vectors) on csman.