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

Topic 1: Implementing an array class

Exercises

Synopsis

• Exercise 1
• Exercise 2
• Exercise 3
• Exercise 4
• Exercise 5
• Exercise 6
• Exercise 7
• Exercise 8
• Exercise 9
• Solutions to Exercises

Exercise 1

1. Could the "2D" allocation strategy used in Array be extended to three or more "dimensions"? If so, outline how. If not, explain why not?

2. Assuming it is feasible, explain what would be gained by such a "higher order" implementation¤.

3. Suggest what the disadvantages of such a multi-level approach might be.

There is a sample solution for Exercise 1.

Exercise 2

1. Explain why the expression n>>d is identical to n/D for both positive two's-complement integers.

2. Explain why the expression n&((1<<d)-1) is identical to n%D for positive two's-complement integers.

3. What advantage(s) do the "shift-based" versions have over the "division-based" versions?

4. What advantage(s) do the "division-based" versions have over the "shift-based" versions?

5. Under what circumstances might it not matter which version was used?

There is a sample solution for Exercise 2.

Exercise 3

Verify the reasoning used to justify the use of:

        reallocate(array.myNextFree+modBucketSize >> divBucketSize);

1. Rewriting the argument in your own words.

2. Graphing the equation:  
        B = floor( (E+S-1)/S )  
   for various values of E (the number of elements) and S (the bucket size).

Exercise 4

There is a sample solution for Exercise 4.

Exercise 5

1. The Array destructor uses operator delete[] instead of operator delete. Explain what difference this makes?

2. The destructor is not declared virtual, which implies a restriction on how class Array may be used. Describe that restriction and explain how it comes about.

There is a sample solution for Exercise 5.

Exercise 6

1. Redesign the Array::Contains member function so that it is able to return the index of the first matching element (rather than the index+1) and yet can still signal failure in some useful manner (hint: consider how the checked public access members achieve this).

2. Redesign the Array::Contains member function so that it is able to search for an index based on any (in)equality criterion (that is, less than, greater than, equals, not equals, etc.).

There is a sample solution for Exercise 6.

Exercise 7

        reallocate(myNextFree+array.myNextFree+modBucketSize>>divBucketSize);

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

        return *this;

Explain why that might not be a good idea.

There is a sample solution for Exercise 7.

Exercise 8

1. Neither Array::Reset() nor Array::RemoveLast(...) delete any buckets that becomes unused as a result of their actions. Rewrite them so that they do.

2. Discuss the advantages and disadvantages of having these member functions reclaim memory.

3. Suggest how Array::Reset() and Array::RemoveLast(...) could be re-implemented so as to improve their maintainability.

There is a sample solution for Exercise 8.

Exercise 9

1. The element-by-element comparison within the equality operator has been implemented as:  
    
       if (!(a1.access(i) == a2.access(i))) { return false; }   
    
   rather than the more obvious:  
    
       if (a1.access(i) != a2.access(i)) { return false; }   
    
   Explain the advantage of this decision.

2. Many STL¤ container classes¤ require that a "less than" operator (<) be defined on the stored element type. Hence, as it is currently defined, we could not create, for example, a map<int, Array<int> >. Implement an operator< for comparing two Arrays.

There is a sample solution for Exercise 9.

Last updated: Fri Feb 18 11:16:58 2000