Array doubling
Container classes in the standard template library have the ability to increase their capacity in order to accommodate new objects. One way of doing this is array doubling. In this strategy, we store our objects in an array. Whenever we run out of space, we request a new array that is double the size of the old array. The contents of the old array are then copied over to the new array, finally, the space of the old array is freed up.
Array doubling is the strategy used in some implementations of the standard template library. You can use the capacity function of the vector class to see the size of the underlying array that is used to store the content of the vector.
As you can see, "resizing" an array is an expensive task. This is why you shouldn't rely on the push_back function of the vector class if you know the maximum amount of space you require. For example, if you need space for a thousand elements in a vector, then use the constructor that creates a vector of size 1000 immediately. This is more efficient than having to create 10 new arrays when using array doubling.
The following function template uses the idea presented above to resize an array on the heap. The function can be used to either increase or decrease the size of the array. If the function is used to decrease the size of the array, then it cuts off the elements that don't fit.
//PRE: old_size, new_size >= 0.
// t = nullptr or points to an allocated array
// (of size >= old_size) on the heap.
//POST: t points to an array of size new_size.
// m = min(old_size, new_size).
// t[0, m) remains the same.
template <typename T>
void resize_array(T*& t, int old_size, int new_size) {
if (old_size == new_size) // Do nothing if the sizes are the same.
return;
T* new_t = new T[new_size]; // Create the new array.
for (int i = 0; i < old_size; i++) { // Copy from the old array to the new array.
new_t[i] = t[i];
}
delete[] t; // Free up the space of the old array.
t = new_t; // Set t to point to the new array.
}
For extra credit, use array doubling to remove the size limitation of the PriorityQueue class of homework 4. Add the comment //Dynamic!!! on the first line of your code to indicate you used dynamic memory. If I miss it after I grade it, just send me an emial to let me know.