Vectors are re-sizable arrays which are very useful for storing data. I did this exercise as a way to learn about memory management as well as basic recursion.
Functions:
Resize:
One of the first functions needed in order for the vector to work is a private function to resize the vector. It works by doubling the size of the vector whenever it runs out of space. It's important to keep this function private because we don't want the size of the vector doubled unless we need it to be since doubling takes up quite a lot of memory. The function does two things. First it makes a new array that is twice the size of the old one. It then transfers the values from the old vector to the new vector and sets empty spaces at the end to the default value of zero. Once everything is finished it deletes the old vector to free the memory and then changes the vector pointer to point at the new vector.
void intVector::resize() { int temp = size;// holds the intial size of the array size = temp * 2;// doubles size int* tempArray = new int[size];//makes a new array twice the size of the old one //stores values from old array into the new one for (int i = 0; i < temp; i++) { tempArray[i] = p[i]; } //sets empty spaces at end of vector to zero int tempInt = size - capacity;//vairble for number of spaces at the end of the array for (int j = 0; j < tempInt; j++) { tempArray[capacity + j] = 0; } delete[] p;//free memory for the old array by deleteing it p = tempArray;//sets array pointer to point at the new array }
Push back:
This is a simple function for adding values to our vector. It works by placing the values at the end of the vector. It starts by checking to be sure that there is room for the new values in the vector. If there is not it calls resize to make space in the vector. It then puts the new value after the other values and increments capacity to keep track of the number of values in the vector.
void intVector::push_back(int a) { //if all array elements are full call resize to double array if (capacity == size) { resize(); } //place user value at the end of the array p[capacity] = a; capacity++;//increment capacity to keep track of elements in the array }
Shrink to fit:
This function shrinks the vector so that the size is equal to the number of elements in the vector. This is useful for make sure that the vector is taking up the least about of space in memory as possible. It works by making a vector the size of the number of elements. It then transfers the values over to the new vector.
void intVector::shrink_to_fit() { //make a new array the size of the elements currently in the array int* temp_array = new int[capacity]; //copy over values from old array for (int k = 0; k < capacity; k++) { temp_array[k] = p[k]; } size = capacity;//set new size to capacity delete[] p;//delete old array to free memory p = temp_array;//set array pointer to point at new array }
Print vector:
This is a function used to check the current size and capacity of the vector as well as what values are contained inside. It was very useful as a debugging tool while I was writing the other functions in this class.
void intVector::print_vector() const { //print the size and capacity of the vector cout << "Size:" << size << endl; cout << "Capacity:" << capacity << endl; //prints elements in the array for (int i =0; i < size; i++) { cout<< p[i] << endl; } }
Push front:
This is a function that adds a user defined value to the front of the vector. It's a bit more complicated than push back because you have to shift all the current values to the right by one. To start check to see if there is space in the vector. If there is not resize the vector. Next make a new vector that is the same size as the current vector. Make the user defined value the first element of the vector then transfer the values from the old vector to the new vector starting at the second element of the vector. Once the values are transferred set any empty spaces to zero. Then delete old vector and change the vector pointer to point at the new vector.
void intVector::push_front(int b) { //if all the elements in the array are full call resize if (capacity == size) { resize(); } int* tempArray = new int[size]; // make a new array tempArray[0] = b;//set the first element equal to the user given value //copy over elements from the old array for(int i = 0; i < capacity; i++) { tempArray[i+1] = p[i]; } capacity++; //sets empty spaces at end of vector to zero int tempInt = size - capacity; for (int j = 0; j < tempInt; j++) { tempArray[capacity + j] = 0; } delete[] p;//deletes old array to free memory p = tempArray;//sets pointer to point at new array }
Resize:
As a way to give the user control over the size of the vector I also wrote a public version of the resize function. This function works by taking in a user define size and then making a new vector that is that size and transferring any current values from the old vector to the new vector.
void intVector::resize(int c) { //if the user gives a size smaller than the current capacity give them a warning if (c < capacity) { cout << "New vector is too small. Some data will be lost." << endl; capacity = c; } size = c;//set new size int* tempArray = new int[c];// make a new array the size of c //copy over values from old array for (int i = 0; i < capacity; i++) { tempArray[i] = p[i]; } //sets empty spaces at end of vector to zero int tempInt = size - capacity; for (int j = 0; j < tempInt; j++) { tempArray[capacity + j] = 0; } delete[] p;//delete old array to free memory p = tempArray;//set array pointer to point at new array }
Sort:
This function uses the merge sort algorithm to organize the values from least to greatest inside the vector. It starts by using recursion to divide the vector into smaller arrays the size of 2 or 1. This allows for each piece of the vector to be organized least to greatest. It then merges them back together by checking which of the smaller arrays has the smallest value, placing that value into the original array and then beginning the check again until all values are back in the vector.
void intVector::sort(int* p, int size) { //make a break case if(size == 2) { //if the second element is smaller than the first flip them if(p[0] > p[1]) { int temp = p[0]; p[0] = p[1]; p[1] = temp; return; } return; } else if (size == 1) { return; } int smallSizeA, smallSizeB; //checks if array size is divisable by 2 if(size % 2 == 0) { //sets both small size to be old size divided by two smallSizeA = size/2; smallSizeB = size/2; } //if it's not make one small size bigger to accomidate the remaineder else { smallSizeA = size/2; smallSizeB = (size/2) + 1; } //make two new arrays to hold the halves of the first array int* arryA = new int[smallSizeA]; int* arryB = new int[smallSizeB]; //this puts the elements of the first array into the two new arrays for(int i = 0; i < size; i++) { if (i < smallSizeA) { arryA[i] = p[i]; } else { arryB[i-smallSizeA] = p[i]; } } //use recursion to breakdown into sizes 2 or 1 sort(arryA, smallSizeA); sort(arryB, smallSizeB); //merge arrays back together sorted int i = 0, j = 0; //while both arrays have numbers in them while(i < smallSizeA && j < smallSizeB) { //if the value of the first arry is less if (arryA[i] < arryB[j]) { //insert value from arrayA back into the first array p[i+j] = arryA[i]; i++; } //if value of the second array is less or equal to else { //insert value from arrayB back into the first array p[i+j] = arryB[j]; j++; } } //if there are no more values in arrayA if(i == smallSizeA) { //while there are still values in arrayB insert them back into first array while(j < smallSizeB) { p[i+j] = arryB[j]; j++; } } //if there are no more values in arrayB if(j == smallSizeB) { //while there are still values in arrayA insert them back into first array while(i < smallSizeA) { p[i+j] = arryA[i]; i++; } } //delete small arrays to free memory delete[] arryA; delete[] arryB; }
Insert:
This function allows the user to insert a value where every they want to inside the vector.
It then takes the values that were at and after the given insert position and shifts them one to the right. If the given position was not in the vector the vector resizes until it is.
void intVector::insert(int val, int pos) { //check and see if pos is greater than vector size //if it is resize until it's not if(pos > size || pos == capacity) { while(pos >= size) { resize(); } } // going to need to store all values at and to the right of the postion in a temp array if(pos < capacity) { //need size of new temp array(capacity - pos) int tempSize = capacity - pos; //get values to store int* temp = storeValues(pos, tempSize); //place values back into the array shifted one to the right for(int i = 0; i < tempSize; i++) { p[pos + 1 + i] = temp[i]; } } //overwrite postion with given value p[pos] = val; capacity++; }
Remove:
This function allows the user to remove values from the vector by giving a position inside the vector. If there are values after the deleted value the function then shifts them one to the left so there are no gaps in data.
void intVector::remove(int pos) { //check postion against size //if it's greater return if(pos > size) { cout << "position not in vector" << endl; return; } p[pos] = 0; //if there were values after the deleted value if(pos < capacity) { //need size of new temp array(capacity - pos) int tempSize = capacity - pos; int tempPos = pos + 1; //make a temp array with values int* temp = storeValues(tempPos, tempSize); //shift values one to the left for(int i = 0; i < tempSize; i++) { p[pos + i] = temp[i]; } //set the now empty place to zero p[capacity - 1] = 0; } capacity--; }
Link to program on github: https://github.com/irisra1/C-projects/tree/master/Vector
