Description
Background
Earlier in the semester, you studied the concept of a vector. As you recall, a vector acts very much like an array, except that a vector automatically grows to hold more data when it is required. In this project, you will create a class that works like a vector of integers.
An important element in the design of a vector is the use of a dynamically allocated array, via a pointer that keeps track of where the array is in memory. As you continue your training as a programmer, you will need to master the use of dynamically allocated storage and pointers.
Important note: You may not use std::vector to do any of this — you are creating your own vector class! We will use the original name used by the C++ Standards Committee before they changed it to vector: DynArray (for “dynamic array”).
Objectives:
Students will gain confidence in the use of pointers and dynamically allocated storage.
The DynArray Class
For efficiency of operation, DynArray has two notions of size:
the current “capacity”, which is the size of the dynamic array on the heap at the moment, and
The actual “size”, which is the number of elements currently in use.
If these values are the same, then the array is full and needs to be made larger so it can hold more items. This is done by:
allocating a new, larger array (typically 1.5 times the current capacity)
copying the currently used data to the first “size” locations of the new array
deleting the old array, thus returning its memory to the heap
having your internal pointer point to the new heap array
In order to operate like a true vector, your class must contain at least the following functions:
A default constructor that creates a DynArray with a default capacity of 2. Its size will initially be zero. Remember that size refers to the number of elements currently stored by the user in the DynArray.
A parameterized constructor receiving an integer, n, that creates a DynArray of capacity n. Its size will initially be zero.
A destructor that deletes any dynamically allocated storage. This prevents a memory leak.
A function size( ) that returns the current size of your DynArray instance. The size will change as integer values are added.
A function capacity( ) that returns the allocated capacity of the DynArray. The capacity is defined as the number of integer values that can be stored in the DynArray instance. The capacity changes when the underlying array grows.
A function clear( ) that deletes all of the elements from the DynArray and resets its size to zero and capacity to the default of two. This must be fresh heap memory.
A function push_back(int n) that adds the integer value n to the end of the DynArray. If it is not large enough to hold this additional value, you must make increase the size of the backing array, as explained above.
A function pop_back( ), that decrements the “size” of the DynArray by 1. No change is made to the allocation.
A function at(int n) that returns the value of the integer stored at index n of the DynArray. If the index is outside the range of the vector (no element at that index), this function should throw a runtime_error with an appropriate message.
Implementing DynArray
Read the information here to see how to implement a vector. One of the best things that you can do as you develop and test your DynArray code is to draw pictures as I have done here.
You should also read this page to see how to implement a destructor.
Your Program
Here is a driver that will test your DynArray class. Use it without change. After developing your DynArray class, add the driver to your project and compile and link to create your executable.
Format and document your code in accordance with the course style guidelines. Include a file prologue identifying you as the author. Submit your project using the instructions outlined in the Course Syllabus, Programming Projects section.
File(s) to Submit:
Place your source code and execution screen shot into a zip file and submit canvas as Project #6.
Grading Criteria:
Your program meets the grading guidelines:
Source code files contain a declaration that you did not copy any code
Submitted to Canvas
Code meets style guidelines
Code is properly documented
You have a DynArray class that matches the project’s specifications.
Your backing array grows when required
All of the required functions work as specified
There are no memory leaks
Your program works correctly with the driver that has been provided.