GCO4020/CSC428 - Advanced Object Oriented Techniques In C++
Week 1

Topic 1: Implementing an array class

Solutions to Exercises

Synopsis

Solution to Exercise 1
Solution to Exercise 2
Solution to Exercise 4
Solution to Exercise 5
Solution to Exercise 6
Solution to Exercise 7
Solution to Exercise 8
Solution to Exercise 9

Solution to Exercise 1

The "2D" allocation strategy used in Array could be extended to three or more "dimensions". For example, if a "3D" strategy were used, Array elements would still be stored in fixed-size buckets, but these buckets would in turn be stored in fixed-size "meta-buckets".

In order to implement this design, only the private member functions reallocate() and access would need to be re-implemented. The private member myElement would change from ElementType** to ElementType*** and an extra counter (myMetaBucketCount) would be needed to track the allocation of meta-buckets.

Conceptually, the new internal structure of the class would look like this:

[Diagram showing a pointer to a vector of pointers to (small, fixed-size) vectors
of pointers to (small, fixed-size) vectors of array elements]

The advantage of a "higher order" implementation¤ is that the amount of reallocation done by Array objects would be further reduced, since only the vector¤ of pointers to meta-buckets would ever need to be reallocated, and then only when every bucket in every meta-bucket were full.
There are several disadvantages in using a multi-level approach. Firstly, the total amount of memory allocated would increase, since space must be allocated for the meta-bucket vector¤ and for each meta-bucket and for each bucket. More significantly, access performance would be further degraded since any access now requires 3 (or, in general, N) pointer dereferences. Finally, there is the less tangible disadvantage of the small reduction in maintainability due to the increasingly complex multi-level memory management code required.

(End of solution)

Solution to Exercise 2

Given that n, d and D are non-negative integers and that D is equal to 2 raised to the power of d:

Consider the bit shift of a binary bit pattern one place to the right. The N'th bit in the original becomes the N-1'th bit in the shifted version. Now the "positional value" of the N'th bit is 2 raised to the N (1 for the rightmost bit (bit 0), 2 for the next (bit 1), 4 for the next (bit 2), etc.) and that of the N-1'th bit is 2 raised to the N-1. Hence shifting the N'th bit right one place reduces its contribution to the total value of the bit pattern by a factor of (2 to the N)/(2 to the N-1). That is, its value is halved.

Since all the bits of the bit pattern are shifted, the positional values of all the bits of the bit pattern are halved, so the overall value must also be halved. Hence a right-shift one place is a division by 2 (except that instead of being shifted to a positional value 0.5 (2 to the -1), the lowest bit is shifted out of existence, effectively rounding the division down, just as in integer arithmetic).

If a right shift by one place of a number halves its value, a right shift of two places halves the number then halves it again (that is, divides it by 2 to the 2). Likewise, a right shift of three places halves the number three times (divides it by 2 to the 3). Hence a right shift of d places divides a number by 2 to the d, which was previously defined to be D, as required.
The expression 1<<d produces a bit pattern with the d'th bit set to 1 and all other bits zero. Subtracting 1 from such a bit-pattern produces a bit pattern with bits d-1, d-2,..., 1, 0 set to 1 and all other bits zero (just as subtracting 1 from 1000000 gives 0999999 in base 10). A bitwise AND (&) of this pattern with a number n therefore sets all the bits greater than bit d-1 to zero, and retains the remaining bits as they were. Hence the expression n&((1<<d)-1) isolates the lowest d bits of n. Note that it is the very same lowest d bits which are lost when n is right-shifted d places (that is, when n is divided by D, as demonstrated in (i) above).

It is clear that by reversing parts of the argument in (i) above we can demonstrate that left-shifting by d places is equivalent to multiplying by D. Now the modulo operation n%D can defined as n-(n/D)*D, where / denotes integer division. Hence to compute (n/D)*D we could first right-shift n by d places and then left-shift the result by d places. Since left-shifting d places fills the lowest d bits with zeros, the difference between n and (n>>d)<<d will be the value of those lowest d bits, or n&((1<<d)-1 as proved above.

But the difference between n and (n>>d)<<d is equal to n-n/D*D or n%D. Hence n&((1<<d)-1 is equal to n%D, as required.
The advantage of the "shift-based" versions is that, on many machine architectures, bit-wise and additive operations are considerably cheaper than division and modulo operations.
The advantage the "division-based" versions have over the "shift-based" versions is that code which uses them is clearer in its purpose and hence more maintainable.
There are circumstances under which, from the point of view of efficiency, it might not matter which version was used. For example, the compiler may be able to generate assembler code which takes advantage of inbuilt fast division hardware, or the optimiser may be intelligent enough to recognize the "division-by-a-power-of-2" operations and automatically convert them to shift-based equivalents.

(End of solution)

Solution to Exercise 4

If the Array class provided a single "pre-allocation constructor":

        template <class ElementType>
        Array<ElementType>::Array(int initsize,
        			  const ElementType& initval,
        			  bool empty = false)
        : myBucketCount(0)
        , myNextFree(empty?0:initsize)
        , myElement(0)
        {
        	reallocate((initsize+modBucketSize >> divBucketSize);
        	if (!empty)
        	{
        		for (int i=0;i<myNextFree;i++)
        		{
        			access(i) = initval;
        		}
        	} 
        }

then there would be no conflict with the special case of:

        template <>
        Array<int>::Array(const int& elem);

and "uninitialized" arrays could still be constructed thus:

        Array<string> name  (20, string(), true);
        Array<double> score (20, double(), true);

Note however that this solution is considerably less convenient and also less self-documenting.

(End of solution)

Solution to Exercise 5

The Array destructor must use operator delete[] rather than operator delete because all the memory allocated by reallocate() is allocated using operator new[] ("new array of"), not operator new ("new single instance of"). Using mismatched versions of new and delete results in undefined behaviour that typically corrupts the free store and is always difficult to debug. Worse still, older compilers may accept the mismatch, creating subtle, hard-to-find bugs when compilers are upgraded or code ported to another system.
By not declaring the destructor virtual the class designer is (implicitly) asserting that class Array should never be used as a public base class, or at least that instances of its derived classes should never be polymorphically delete'd through an Array*. (TDCS, § ????).

(End of solution)

Solution to Exercise 6

We could redesign Array::Contains(...) along the lines of Array::operator[], so that it throws an exception on failure. It should be renamed something like Array::IndexOf(...) since it can no longer be used as a simple Boolean containment test (for an approach which would provide a better solution to this interface¤ design problem and which does retain the desirable Boolean test capability, see "Topic 17: Fallible Types".)

        	template <class ElementType>
        	struct Array<ElementType>::NoSuchElement
        	{
        		NoSuchElement(const ElementType& t) : target(t) {}

        		const ElementType& target;
        	};

        	template <class ElementType>
        	int
        	Array<ElementType>::IndexOf(const ElementType& target) const
        	{
        		for (int i=0;i<myNextFree;i++)
        		{
        			if (target == access(i)) { return i; }
        		}
        		throw NoSuchElement(target);
        	}

        	// AND LATER....

        	while (cin >> searchValue)
        	{
        		try 
        		{
        			int index = array.IndexOf(searchValue);
        			cout << records[index] << endl;
        		}
        		catch (const Array<Record>::NoSuchElement& nse)
        		{
        			cout << "No match for " << nse.target << endl;
        		}
        	}

To enable Array::Contains to search on any (in)equality criterion we could give it a second parameter which specified how to compare elements. The simplest, but least flexible and least maintainable option would be to use an enum value to control a switch specifying the possible alternatives (see source code listing: EnumContains.C). More flexibility could be gained by passing a function pointer, which implements the operation (see source code listing: FnPtrContains.C). The most flexible solution makes Array::Contains a templated member function and uses so-called "Comparators" (see "Topic 21: Functors I" and (TDCS, § 20.3.3) for more details.)

(End of solution)

The proposed implementation of Array::Append(const Array& array) is flawed because the for loop never terminates if an array is appended to itself (for example: array.Append(array);). This is because in that case the aliasing of *this and array makes the proposed loop equivalent to:

        for (int i=0; i<array.myNextFree; i++)
        {
        	array.access(array.myNextFree++) = array.access(i);
        }

which will never terminate (except in the trivial case where array.myNextFree is initially 0), because array.myNextFree is incremented as frequently as i.

(End of solution)

Solution to Exercise 8

The following versions of Array::Reset() and Array::RemoveLast(...) delete any memory that becomes unused:

        template <class ElementType>
        Array<ElementType>&
        Array<ElementType>::Reset(void)
        {
                myNextFree = 0;
        	while (myBucketCount>0)
        	{
        		delete[] myElement[--myBucketCount];
        	}
        	delete[] myElement;
        	myElement = 0;
                return *this;
        }

        template <class ElementType>
        Array<ElementType>&
        Array<ElementType>::RemoveLast(int n)
        {
        	if (myNextFree<=n) { myNextFree = 0; }
        	else               { myNextFree -= n; }

        	int newBucketCount = (myNextFree+modBucketSize>>divBucketSize);
        	while (myBucketCount>newBucketCount)
        	{
        		delete [] myElement[--myBucketCount];
        	}
        	if (newBucketCount==0)
        	{
        		delete [] myElement;
        		myElement = 0;
        	}

                return *this;
        }

The advantage of reclaiming memory when elements are removed is that the amount of free store used at any time is minimal. This may be significant when the maximum number of elements an Array object is likely to store greatly exceeds the average number of elements it will store. The principal disadvantage is that deletions are often slow, making the removal operations expensive, particularly if an alternating series of deletions and insertions are performed, causing the memory management to "thrash".
Array::Reset() is clearly a special case of the more general Array::RemoveLast(...), and could be coded as such, thereby localizing the implementation¤ of the removal components of the class to a single member function. The downside of this approach are a slight increase in the cost of calling Array::Reset() because, being a special case, it can be directly implemented slightly more efficiently.

        template <class ElementType>
        inline Array<ElementType>&
        Array<ElementType>::Reset(void)
        {
        	return RemoveLast(myNextFree);
        }

(End of solution)

Solution to Exercise 9

The advantage of using a negated == is that we avoid adding another constraint on ElementType, namely that operator!= be defined for ElementType (ElementType is already required to define operator==, because that operator is also required by Array::Contains(...)).
Although the meaning of Array equality is reasonably obvious, it is less clear how to define the "less-than" operation between two arrays. One reasonable approach would be to generalize the existing comparison rules for char[], as implemented by the library function strcmp.

That is, an array a1 is "less than" an array a2 if there exists a index i such that 0 <= i < a2.Count() and either a1.Count() <= i or a1[i] < a2[i].

The corresponding implementation¤ of operator< looks like this:


        template <class ElementType>
        bool
        operator< (const Array<ElementType>& a1, const Array<ElementType>& a2)
        {
        	if (&a1==&a2) { return false; }
        	for (int i=0; i<a2.myNextFree; i++)
        	{
        		if (a1.myNextFree <= i || a1.access(i) < a2.access(i))
        		{
        			return true;
        		}
        	}
        	return false;
        }

Last updated: Fri Feb 18 11:17:01 2000