Dynamic Array - Add and Resize

The add and resize functions will be central to this, and will have the main thinking around dynamic memory management. This will allow you to add new elements to a dynamic array, and to keep adding them even when you exceed the array’s initial capacity.

Resize

Add is going to need resize, so we are best to implement the resize code first. The following prompt should help Copilot get you something close to what we want.

/**
 * @brief Resize the capacity of the dynamic array.
 *
 * If the new capacity is smaller than the current size, the size
 * will be updated to match the new capacity.
 *
 * @tparam T the type of data in the dynamic array
 * @param array the dynamic array to grow
 * @param new_capacity the new capacity of the dynamic array
 * @returns true if this succeeded, or false if it could not reallocate memory
*/

For me, it kept wanting to do silly things like use malloc instead of realloc and then manually copying over the data one element at a time. This is slow, inefficient, and unnecessary. I ended up accepting the malloc suggestion, then I deleted the malloc code, and the code to copy the array over, and added a new comment at the right location to prompt it to use realloc. Similarly, I had to prompt it to update the capacity if the new capacity was smaller. The prompts are below.

// Resize the data in the array

// Update the size if the new capacity is smaller than the current size

Tip

The logic for resize should include the following:

• It is using realloc to allocate space on the heap based on the new capacity.
• You store the pointer returned from realloc in a local variable, and test that this is not null.
• If realloc returned null, you are out of memory, so you have to return false.
• Otherwise, set the new data and capacity
• Check to make sure that size is still less than or equal to capacity, and if not update the size to be equal to the new capacity
• Finally return true on success

• My code for if you get stuck

  #include <cstdlib>
  
  /**
   * @brief A dynamic array struct that contains the size, capacity,
   *        and data pointer used to implement this dynamic structure.
   *
   * @tparam T the type of data to store in the dynamic array
   * @field data a pointer to the data in the dynamic array on the heap
   * @field size the number of elements used in the dynamic array
   * @field capacity the number of elements the dynamic array can hold
   * @field default_value the default value to use when getting an element
   */
  template <typename T>
  struct dynamic_array
  {
      T *data;
      unsigned int size;
      unsigned int capacity;
  };
  
  /**
   * @brief Create a new dynamic array with the indicated initial capacity.
   *
   * @tparam T the type of data the array will store
   * @param capacity its initial capacity, with a default value of 50
   * @return dynamic_array<T>* a pointer to the new dynamic array
   */
  template<typename T>
  dynamic_array<T> *new_dynamic_array(unsigned int capacity = 50)
  {
    dynamic_array<T> *result = (dynamic_array<T>*)malloc(sizeof(dynamic_array<T>));
    // Make sure result was allocated
    if (result == nullptr)
    {
      return result;
    }
    result->data = (T*)malloc(sizeof(T) * capacity);
    result->size = 0;
    // Make sure that data was allocated, if not set capacity to 0
    if(result->data == nullptr)
    {
      result->capacity = 0;
    }
    else
    {
      result->capacity = capacity;
    }
    return result;
  }
  
  /**
   * @brief Free the memory allocated to the dynamic array. Once freed
   *        the data in the array will no longer be accessible.
   *
   * @tparam T the data type of the dynamic array
   * @param array a pointer to the dynamic array to free
   */
  template<typename T>
  void delete_dynamic_array(dynamic_array<T> *array)
  {
    // Ensure that the array is allocated
    if (!array) return;
  
    // Clear to ensure we remove any data from memory before freeing it
    array->size = 0;
    array->capacity = 0;
  
    // Free the data and the array itself
    free(array->data);
    // Ensure we don't have a dangling pointer
    array->data = nullptr;
  
    // Free the dynamic array itself
    free(array);
  }
  
  /**
   * @brief Resize the capacity of the dynamic array.
   *
   * If the new capacity is smaller than the current size, the size will be updated to match the new capacity.
   *
   * @tparam T the type of data in the dynamic array
   * @param array the dynamic array to grow
   * @param new_capacity the new capacity of the dynamic array
   * @returns true if this succeeded, or false if it could not reallocate memory
  */
  template<typename T>
  bool resize(dynamic_array<T> *array, unsigned int new_capacity)
  {
    // Ensure that the array is allocated
    if (!array) return false;
  
    // Resize the data in the array
    T* new_data = (T*)realloc(array->data, sizeof(T) * new_capacity);
    // Check if the allocation failed
    if (new_data == nullptr)
    {
      // We failed to allocate memory, so we can't resize the array
      return false;
    }
  
    // Update the array's data and capacity
    array->data = new_data;
    array->capacity = new_capacity;
  
    // Update the size if the new capacity is smaller than the current size
    if (new_capacity < array->size)
    {
      array->size = new_capacity;
    }
  
    return true;
  }
  
  int main()
  {
    // Create a dynamic array of int
    // and initialise it to a new dynamic array of 10 elements
    dynamic_array<int> *array = new_dynamic_array<int>(10);
  
    // Free the array and ensure we do not have a dangling pointer
    delete_dynamic_array(array);
    array = nullptr;
  
    return 0;
  }

Add

To put values in the array, the user (a programmer) will have to call the add method. This will insert the value at the end of the currently used part of the array, and increase the array’s size. If there is no capacity to do this, the array will first have to try to resize the array, if that succeeds then it can add as normal.

Here is a starting prompt:

/**
 * @brief Add an element to the end of the dynamic array
 *
 * @tparam T the type of data in the dynamic array
 * @param value the value to add to the end of the dynamic array
 * @param array the dynamic array to add the value to
 * @returns true if this succeeded, false if we cannot resize to fit the new element
 */

For me this kept trying to put the resize code in add, rather than calling the resize we had already created. Here are some of the extra comments that I added.

// Check if we need to resize the array, and if we failed to resize the array
// Add the value to the end of the array

Tip

You want to make sure that add has the following:

• It checks if size is at capacity, and resize if it is.
• When we resize, you can resize so that the new capacity is double the current capacity.
• Remember to check if resize fails, which means you are out of memory!
• If the resize fails, we need to return false.
• You need to update the element at array->size index
• Then increment array->size
• Finally return true on success

• My code for if you get stuck

  #include <cstdlib>
  
  /**
   * @brief A dynamic array struct that contains the size, capacity,
   *        and data pointer used to implement this dynamic structure.
   *
   * @tparam T the type of data to store in the dynamic array
   * @field data a pointer to the data in the dynamic array on the heap
   * @field size the number of elements used in the dynamic array
   * @field capacity the number of elements the dynamic array can hold
   * @field default_value the default value to use when getting an element
   */
  template <typename T>
  struct dynamic_array
  {
      T *data;
      unsigned int size;
      unsigned int capacity;
  };
  
  /**
   * @brief Create a new dynamic array with the indicated initial capacity.
   *
   * @tparam T the type of data the array will store
   * @param capacity its initial capacity, with a default value of 50
   * @return dynamic_array<T>* a pointer to the new dynamic array
   */
  template<typename T>
  dynamic_array<T> *new_dynamic_array(unsigned int capacity = 50)
  {
    dynamic_array<T> *result = (dynamic_array<T>*)malloc(sizeof(dynamic_array<T>));
    // Make sure result was allocated
    if (result == nullptr)
    {
      return result;
    }
    result->data = (T*)malloc(sizeof(T) * capacity);
    result->size = 0;
    // Make sure that data was allocated, if not set capacity to 0
    if(result->data == nullptr)
    {
      result->capacity = 0;
    }
    else
    {
      result->capacity = capacity;
    }
    return result;
  }
  
  /**
   * @brief Free the memory allocated to the dynamic array. Once freed
   *        the data in the array will no longer be accessible.
   *
   * @tparam T the data type of the dynamic array
   * @param array a pointer to the dynamic array to free
   */
  template<typename T>
  void delete_dynamic_array(dynamic_array<T> *array)
  {
    // Ensure that the array is allocated
    if (!array) return;
  
    // Clear to ensure we remove any data from memory before freeing it
    array->size = 0;
    array->capacity = 0;
  
    // Free the data and the array itself
    free(array->data);
    // Ensure we don't have a dangling pointer
    array->data = nullptr;
  
    // Free the dynamic array itself
    free(array);
  }
  
  /**
   * @brief Resize the capacity of the dynamic array.
   *
   * If the new capacity is smaller than the current size, the size will be updated to match the new capacity.
   *
   * @tparam T the type of data in the dynamic array
   * @param array the dynamic array to grow
   * @param new_capacity the new capacity of the dynamic array
   * @returns true if this succeeded, or false if it could not reallocate memory
  */
  template<typename T>
  bool resize(dynamic_array<T> *array, unsigned int new_capacity)
  {
    // Ensure that the array is allocated
    if (!array) return false;
  
    // Resize the data in the array
    T* new_data = (T*)realloc(array->data, sizeof(T) * new_capacity);
    // Check if the allocation failed
    if (new_data == nullptr)
    {
      // We failed to allocate memory, so we can't resize the array
      return false;
    }
  
    // Update the array's data and capacity
    array->data = new_data;
    array->capacity = new_capacity;
  
    // Update the size if the new capacity is smaller than the current size
    if (new_capacity < array->size)
    {
      array->size = new_capacity;
    }
  
    return true;
  }
  
  /**
   * @brief Add an element to the end of the dynamic array
   *
   * @tparam T the type of data in the dynamic array
   * @param value the value to add to the end of the dynamic array
   * @param array the dynamic array to add the value to
   */
  template<typename T>
  bool add(dynamic_array<T> *array, T value)
  {
    // Ensure that the array is allocated
    if (!array) return false;
  
    // Check if we need to resize the array, and if we failed to resize the array
    // We double the capacity and add 1 to address issues where capacity is 0 initially
    if (array->size >= array->capacity && !resize(array, array->capacity * 2 + 1))
    {
      // We didn't have space, and we failed to resize the array!
      return false;
    }
  
    // Add the value to the end of the array
    array->data[array->size] = value;
    array->size++;
  
    return true;
  }
  
  int main()
  {
    // Create a dynamic array of int
    // and initialise it to a new dynamic array of 10 elements
    dynamic_array<int> *array = new_dynamic_array<int>(10);
  
    // Free the array and ensure we do not have a dangling pointer
    delete_dynamic_array(array);
    array = nullptr;
  
    return 0;
  }

Test in main

To test this in main I used the following comment as a prompt.

// Add 15 values to the array

At this point, main is looking like this for me.

int main()
{
  // Create a dynamic array of int
  // and initialise it to a new dynamic array of 10 elements
  dynamic_array<int> *array = new_dynamic_array<int>(10);

  // Add 15 values to the array
  for(int i = 0; i < 15; i++)
  {
    add(array, i);
  }

  // Free the array and ensure we do not have a dangling pointer
  delete_dynamic_array(array);
  array = nullptr;

  return 0;
}

Make sure your program builds and runs before you move on.

Try working with an initial capacity of 0. I ended up changing my add method to double and + 1 so that it works when the capacity was originally 0. As 2 * 0 is still 0.