2. [12 marks] Implement a C++ string class in files String.H and String.C
following the coding style and comment suggestions presented in the
lecture.
Strings are immutable, like in Java, i.e. once created, Strings cannot be
changed. This allows us to save memory when copying Strings by storing
character sequences in shared objects that are reference counted. I.e.,
whenever a String is created, a shared object is allocated that contains the
character sequence with an initial reference count of 1. Later, whenever a
String gets copied or assigned, the count is incremented and the new copy just
points to the shared object. When Strings are deleted, the reference count is
decremented. Once the count reaches 0, the shared object is no longer in use
and can be destroyed. In the shared objects, strings are stored as C-strings,
i.e. 0-terminated char arrays.
You may add private const data members and private methods to the class
definition, but no other members.
Your code has to compile using
g++ -Wall -Wextra -O -std=c++17 …
without generating errors nor warnings.
Make sure your implementation does not leak memory by testing it thoroughly
creating, assigning, copying, and destroying thousands of Strings in
mainString.C and running valgrind. You only submit String.* which don’t
contain test code.
============================================================================
3. [16 marks] Implement a memory efficient set class in files Set.H and Set.C
following the coding style and comment suggestions presented in the lecture.
The sets considered here represent subsets of { 0..n-1 } and are implemented
in terms of bit sequences stored in int arrays. For instance, for n = 4,
integer 11 = 1011 in binary represents set {0,1,3}. Each int can hold a
certain number of bits (use static const INT_BITS = sizeof(int)*8 in your
code). Your code needs to allocate a large enough int array to store n bits
(how many integers do you need exactly?) (Bit i) = 1 indicates that element i
is contained in the set. Use bit operations & | ~ to test, set, and negate
bits. E.g. the following test checks whether bit i is set in integer y:
if ((1 << i) & y) … ,
(b | c) computes the union of two bit sets encoded as integers b and c,
(b & c) computes the intersection, and
~b computes the complement set of b.
Sets are sole owners of their data, i.e. data aren’t shared when copying or
assigning sets and therefore have to be allocated and copied. Also, in
assignments, the lhs and rhs sets must have identical n’s.
You may add private const data members and private methods to the class
definition, but no other members.
Your code has to compile using
g++ -Wall -Wextra -O -std=c++17 …
without generating errors nor warnings.
Make sure your implementation does not leak memory by testing it
thoroughly. We suggest using valgrind. Also add assertions that ensure that
sets are compatible and elements are within range 0..n-1. See mainSet.C for
some examples. You only submit Set.* which don’t contain test code.
Assertions work as follows:
#include <cassert>
…
assert(i >= 0); // if i < 0 the program will stop here with an error message
To make your program faster after convincing yourself that it is correct,
checking assertions can be switched off by passing -DNDEBUG to the compiler.