CS11 Advanced C++ Lab 3: List Initialization and Vectors of Bool

We are finally nearing the end of our exploration of the Vector implementation! This week we will implement two remaining features that will complete our exposure to how collection classes are implemented:

List initialization for our Vector<T> class-template
Implement a specialization of our template for Vector<bool>

Since our goal is only to explore some of these features and how they work, you are not required to implement iterators for Vector<bool>. However, if you do complete working iterators for Vector<bool> then you will receive up to +1 bonus point on the assignment (depending on the quality of your implementation, of course).

As always, make sure you document your work completely and concisely, using the Doxygen commenting format.

Supporting Files

As was the case last time, a number of supporting files are provided in this archive to simplify your life. The archive includes some tests for this week's functionality, a Makefile for building, and a Doxyfile for generating documentation using Doxygen. You can look at the Makefile for details of what build targets exist.

You should copy your vector.h and iterator.h files from last lab into this directory, and implement the functionality required for this lab. When you submit, we expect you to only submit the vector.h, iterator.h, and vecbool.h files you create. Your code will be tested with a fresh version of the other files.

List Initialization

In C++11 and forward, the language uses the same syntax to initialize the contents of collection classes and objects as it does for arrays and structs. For example, we can initialize an STL vector like this:

    std::vector<int> v = {1, 2, 3, 5, 8, 13};

List initialization is surprisingly straightforward to support. The compiler will make the array of values available through a std::initializer_list<T> object, which wraps the array with some simple operations to find out how many elements there are, and to iterate over them via pointers.

Implement a Vector<T>(std::initializer_list<T>) constructor to support list initialization.
Also, implement an assignment operator that supports list initialization, i.e. Vector<T>::operator=(std::initializer_list<T>). This allows a vector to be set to an entirely new collection of values.

Vectors of `bool`

The last major task for this week is to implement a specialization of your Vector<T> template for Vector<bool>. As discussed in class, bool is typically one byte, but we know we can store each bool value in one bit. Therefore, it seems desirable to implement a specialization for this case, and the STL in fact includes such a specialization as well.

Before you start, you may notice that all of the tests in the test-suite currently pass, including the Vector<bool> tests. This is because your generalized Vector template is handling this situation properly. You may see regressions as you implement your Vector<bool> specialization, but it shouldn't be hard to get all the tests passing.

Implement your Vector<bool> specialization in a file vecbool.h. This file should use an include-guard, as usual. You will probably want to #include "vector.h" at the top, so that you can implement Vector<bool> in terms of Vector<some integer type>, as discussed in class.
You should update your vector.h file to #include "vecbool.h" at the end of the file, after the definition of the generic Vector<T> template. Again, if your include-guards are all working properly, this should be fine.

The benefit of this approach is that you can edit vector.h and comment out the #include "vecbool.h" line to see if tests are passing or failing, independent of the specialization you are creating.

Implementation Details

A good programmer is always lazy! Always do as little work to implement a solution as you possibly can. In this vein, our Vector<bool> class should be able to use a Vector<some int type> in the internal implementation, so that you don't have to implement memory management all over again. In fact, if you do this, you won't need to implement copy constructors, move constructors, copy-assignment/move-assignment operators, and all that malarkey. The default compiler-provided versions will work perfectly fine.

For this implementation, use uint64_t as the internal storage type.

Make your implementation generic by providing a using definition within your class, e.g.

using block_t = uint64_t;

This way you can use block_t throughout your Vector<bool> code, rather than having to specify some unintuitive integer type everywhere.
You may also want to define a constexpr like BITS_PER_BLOCK, which is just 8 * sizeof(block_t). This will turn out to be an extremely helpful constant in your code.

Supported Operations

Your Vector<bool> needs to support the following operations:

Initialization to a specific size, e.g. Vector<bool> v(5) should initialize a "5-bit" vector.
List initialization, and an assignment operator that supports list initialization; the same as Vector<T>.
(All other "Rule of Five" operations, e.g. copy-constructor, move-constructor, destructor, copy/move-assignment-operators, are not necessary to implement since we can rely on the compiler-generated defaults.)
The capacity() and size() member functions. The size() function should return the number of bits actually stored (i.e. not rounded up to the next block size). The capacity() function should return the number of bits that could be stored, given the space allocated by the Vector<bool>.
The push_back(bool) function, of course!

Array Indexing Operators

Your Vector<bool> type must support the array-index operator, just as before. However, this one is interesting. The const version of this operator can simply look up and return the requested bit. However, the non-const version can't do this, because it must support being the target of an assignment, and individual bits are not addressable.

Thus, your Vector<bool>'s non-const array-indexing operator must return some kind of a helper-object that can perform the bit-assignment operation on behalf of the Vector<bool>. For example, you can define a (private) struct inside your Vector<bool> class, which holds a reference to the internal Vector<block_t> member (so it can manipulate the collection's state directly), along with the index of the bit to get/set. This struct can then implement operator=(bool b), and perform the appropriate bit-manipulation tasks on behalf of Vector<bool>.

Note that the non-const array-index operator may be used by the compiler in other scenarios, to read the state of bits. Because of this, you will likely need to provide a mechanism to convert your helper-object into the corresponding bool value being accessed. You can do this by providing an implicit cast-to-bool operator on your helper object:

    `operator bool() const { ... /* Look up and return the specified bit */ }`

Since this is an implicit conversion operator, the compiler will automatically use it anytime someone uses the [] operator on your object, expecting to get a bool value in return.

Debugging Hint

Bit manipulation can lead to very annoying and strange bugs, especially on 64-bit platforms. For example, you may find that some of your operations work perfectly as long as you are working within the first 32 bits of a block, but then beyond that, they go disastrously wrong.

The important detail here is that C++ generally uses int values for arithmetic, if types are not otherwise specified. For example, given an expression like this:

    1 << bit_offset_in_block

This will be evaluated using a 32-bit int value, leading to serious issues if bit_offset_in_block happens to be 32 or more.

The solution is simple: just cast the value appropriately before performing any operations on it:

    (block_t) 1 << bit_offset_in_block

This way, the compiler knows to use an integer of the proper size in the computation, and you won't get bewildering bugs in your implementation.

OPTIONAL Extra Credit!

As before, the HW3 test code includes some completely optional tests to use your Vector<bool> type with iterators. To get these tests working, you must implement Vector<bool> iterators. This is not required, because it would be too much work to be worth it.

To enable the Vector<bool> iterator tests, you will need to #define the symbol TEST_VECBOOL_ITERS at the top of the test program. This is documented in the file, and shouldn't be hard to find.

Note that the tests are very basic, so you probably won't find them difficult to pass. If you want to implement more sophisticated tests, feel free to do so; if we like them then you will get additional bonus credit.

Submitting Your Work

Once you have completed the above tasks, and your code passes the basic tests provided with the assignment, you can submit these files through csman:

vector.h
iterator.h
vecbool.h

Don't submit the other files; we will use a fresh copy of them when evaluating your work. (NOTE: If you implemented additional tests, feel free to submit these, but be sure to indicate that you added tests so we know to look for them.)

Assignment Feedback Survey

Please also complete and submit a feedback survey with your submission, telling us about your experience with this assignment. Doing so will help us to improve CS11 Advanced C++ in the future.