Table of Contents
1. Smart dynamic array structure
With the dynamic array structure, most of it will be similar to the Fixed Array Structure, except we now have to deal with memory management and pointers.
Instead of throwing exceptions if the array is full, with a dynamic array we
can resize it instead. However, we also now need to check for the array
pointer (m_array in this example) pointing to nullptr.
The class declaration could look like this:
class SmartDynamicArray { public: SmartDynamicArray(); ~SmartDynamicArray(); void PushBack( T newItem ); void PushFront( T newItem ); void PushAt( T newItem, int index ); void PopBack(); void PopFront(); void PopAt( int index ); T GetBack() const; T GetFront() const; T GetAt( int index ) const; int Search( T item ) const; void Display() const; int Size() const; bool IsEmpty() const; void Clear(); private: T* m_array; int m_arraySize; int m_itemCount; void ShiftLeft( int index ); void ShiftRight( int index ); void AllocateMemory( int size ); void Resize( int newSize ); bool IsFull() const; };
~
1.0.1. Constructor - Preparing the array to be used
With the constructor here, it is important to assign nullptr to
the pointer so that we don't try to dereference a garbage address.
The array size and item count variables should also be assigned to 0.
template <typename T> SmartDynamicArray<T>::SmartDynamicArray() { m_array = nullptr; m_itemCount = 0; m_arraySize = 0; }
1.0.2. Destructor - Cleaning up the array
Having a destructor is also very important since we're working with pointers. Before our data structure is destroyed, we need to make sure that we free any allocated memory.
template <typename T> SmartDynamicArray<T>::~SmartDynamicArray() { if ( m_array != nullptr ) { delete [] m_array; m_array = nullptr; } m_arraySize = 0; m_itemCount = 0; }
We can also put this functionality into the Clear() function, and call Clear() from the destructor.
1.0.3. void AllocateMemory( int size )
When the array is not in use, the m_array pointer will be pointing to
nullptr. In this case, we need to allocate space for a new array before
we can begin putting items into it.
Error checks:
- If the
m_arraypointer is NOT pointing to nullptr, throw an exception.
Functionality:
- Allocate space for the array via the
m_arraypointer. - Assign
m_arraySizeto the size passed in as a parameter. - Set
m_itemCountto 0.
template <typename T> void SmartDynamicArray<T>::AllocateMemory( int size ) { if ( m_array != nullptr ) { throw logic_error( "Can't allocate memory, m_array is already pointing to a memory address!" ); } m_array = new T[ size ]; m_arraySize = size; m_itemCount = 0; }
For this function, if the array is already pointing somewhere, we don't want to just erase all that data and allocate space for a new array. We want to try to prevent data loss, so it would be better to throw an exception instead so that the caller can decide how they want to handle it.
1.0.4. void Resize( int newSize )
We can't technically resize an array that has been created. We can, however, allocate more space for a bigger array and copy all the data over and then update the pointer to point to the new array. And that's exactly how we "resize" our dynamic array.
Error checks:
- If the new size is smaller than the old size, throw an exception.
Functionality:
- If
m_arrayis pointing to nullptr, then just call AllocateMemory instead. - Otherwise:
- Allocate space for a new array with the new size using a new pointer.
- Iterate over all the elements of the old array, copying each element to the new array.
- Free space from the old array.
- Update the
m_arraypointer to point to the new array address. - Update the
m_arraySizeto the new size.
template <typename T> void SmartDynamicArray<T>::Resize( int newSize ) { if ( newSize < m_arraySize ) { throw logic_error( "Invalid size!" ); } else if ( m_array == nullptr ) { AllocateMemory( newSize ); } else { T* newArray = new T[newSize]; // New array // Copy values over for ( int i = 0; i < m_itemCount; i++ ) { newArray[i] = m_array[i]; } delete [] m_array; // Deallocate old space m_array = newArray; // Update pointer m_arraySize = newSize; // Update size } }
1.0.5. Updating other functions
- ShiftLeft: If
m_arrayis pointing tonullptr, throw an exception. - ShiftRight:
- If
m_arrayis pointing tonullptr, throw an exception. - If the array is full, call Resize.
- If
- PushBack, PushFront, PushAt:
- If
m_arrayis pointing tonullptrcall AllocateMemory. - If the array is full, call Resize.
- If