You will write your own class that uses dynamic arrays. The purpose of this clas
ID: 3597888 • Letter: Y
Question
You will write your own class that uses dynamic arrays. The purpose of this class will be to store integers, but in a clever way. Sometimes, when you store data, you later realize that you need to store some more. Unfortunately, the size of both static and dynamic arrays cannot be changed once your program is running. To remedy this shortcoming, your class will be resizable. But since dynamic arrays cannot be resized, in order to enlarge yours, you must first create a new and larger dynamic array, copy the old array over to the new one, then delete the old one. The problem with this is that it's not very efficient. Imagine if you had an array of a million items and you had to copy all of them over to a new array just to add a few more items. What if you had to add a few more items a million more times? Then, you'd be copying millions of items millions of times... bad news even for a fast machine!
The solution to this final problem is to DOUBLE the size of your array any time that you have to enlarge it. This unintuitive strategy actually drastically limits the number of times that you have to recopy your array contents. Let's look at an example. If you had an array with a total size of 128 and 100 of those elements are being used, then you could add up to 28 more elements without resizing. If you wanted to add 50 more elements, that would exceed the size, so a resize would be required. You would create a new array with a total size of 256, copy over the original 100 elements, then add the new 50 elements.
Let's look at an outline of the class that you'll be filling in...
class Doubling {
//private:
public:
int* arr;
int size;
int used;
//public:
Doubling() {
}
Doubling(int init[], int siz) {
}
void add(int toAdd) {
}
void print() {
}
};
Of course, you should create a main function that tests this class to make sure that it's working as expected.
In the previous example, how many times have array elements been copied? Well, the array size must double each time it resizes, so if it started at 1, then it resized at 2, 4, 8, 16, 32, 64, and finally at 128. If we add up all of those recopies, we get 256, which is equal to the final size of the array. Therefore, the maximum number of recopies required to maintain this resizable array is simply equal to the largest size that the array reaches! Not bad compared to trillions of recopies with the other strategy
Explanation / Answer
Here is the code updated for you:
#include <iostream>
using namespace std;
class Doubling {
//private:
public:
int* arr;
int size;
int used;
//public:
Doubling() {
arr = new int;
size = 1;
used = 0;
}
Doubling(int init[], int siz) {
arr = new int[siz];
for(int i = 0; i < siz; i++)
arr[i] = init[i];
size = used = siz;
}
void add(int toAdd) {
if(used == size) //If the array space is exhausted.
{
int* newArr = new int[size*2]; //Create a new array with double the space.
for(int i = 0; i < used; i++) //Copy all the elements from arr to newArr.
newArr[i] = arr[i];
size *= 2; //Double the size variable.
delete arr; //Delete the old space.
arr = newArr; //Assign the newly allocated space to arr.
}
arr[used] = toAdd; //Add the new element to arr.
used++; //Increase the used space by 1.
}
void print() {
cout << "[";
for(int i = 0; i < used-1; i++)
cout << arr[i] << ", ";
cout << arr[used-1] << "]" << endl;
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.