Describe what changes need to be made to the extendable array implementation given in Code Fragment 6.2 in order to shrink the size N of the array by half any time the number of elements in the vector goes below N/4.

Data from in Code Fragment 6.2

A vector implementation using an extendable array. 

The member data for class ArrayVector consists of the array storage A, the current number n of elements in the vector, and the current storage capacity. The class ArrayVector also provides the ADT functions insert and remove. We discuss their implementations below. We have added a new function, called reserve, that is not part of the ADT. This function allows the user to explicitly request that the array be expanded to a capacity of a size at least n. If the capacity is already larger than this, then the function does nothing. 

Even though we have not bothered to show them, the class also provides some of the standard housekeeping functions. These consist of a copy constructor, an assignment operator, and a destructor. Because this class allocates memory, their inclusion is essential for a complete and robust class implementation. We leave them as an exercise (R-6.6). We should also add versions of the indexing operators that return constant references.

Transcribed Image Text:

ArrayVector::ArrayVector() : capacity (0), n(0), A(NULL) { } int ArrayVector::size() const { return n; } bool ArrayVector::empty() const { return size() == 0; } Elem& ArrayVector::operator [](int i) { return A[i]; } // constructor // number of elements // is vector empty? // element at index // element at index (safe) Elem& ArrayVector::at(int i) throw (IndexOutOfBounds) { if (i < 0 || i >= n) throw IndexOutOfBounds("illegal index in function at ()"); return A[i]; }