How dynamic Arrays actually work

Dynamic arrays, with their ability to handle an arbitrary number of elements, are indispensable tools in modern programming. In this section, we’ll embark on a journey to create our own dynamic array implementation using C++ classes. By doing so, we’ll gain insights into the inner workings of dynamic arrays, including memory allocation and element copying.

Dynamic allocation and copying

Let’s learn how it works by creating our own Dynamic Array

Let’s start by defining a class named DynamicArray to encapsulate the functionality of our custom dynamic array. This class will manage the storage of elements and handle dynamic resizing as needed.

#include <iostream>

class DynamicArray {
private:
    int* data;          // Pointer to dynamically allocated array
    int size;           // Number of elements currently stored
    int capacity;       // Current capacity of the array

public:
    // Constructor
    DynamicArray() : data(nullptr), size(0), capacity(0) {}

    // Destructor
    ~DynamicArray() {
        delete[] data;  // Release dynamically allocated memory
    }

    // Method to add an element to the end of the array
    void push_back(int element) {
        // If the array is full, resize it
        if (size == capacity) {
            // Double the capacity (resize strategy)
            capacity = (capacity == 0) ? 1 : capacity * 2;

            // Allocate new memory
            int* newData = new int[capacity];

            // Copy existing elements to the new memory
            for (int i = 0; i < size; ++i) {
                newData[i] = data[i];
            }

            // Release the old memory
            delete[] data;

            // Update the pointer to the new memory
            data = newData;
        }

        // Add the new element at the end
        data[size++] = element;
    }

    // Method to display elements of the array
    void display() {
        std::cout << "Dynamic Array Elements:" << std::endl;
        for (int i = 0; i < size; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }

    // Return the capacity
    int get_capacity() {
        return capacity;
    }
};

Exploring Dynamic Array Operations

Now that we have our DynamicArray class defined, let's put it to use by adding elements and observing the allocation and copying processes.

int main() {
    // Create an instance of our custom DynamicArray
    DynamicArray dynamicArray;

    // Add elements to the dynamic array
    for (int i = 0; i < 10; ++i) {
        dynamicArray.push_back(i);
        std::cout << "Capacity: " << dynamicArray.get_capacity() << std::endl;
    }

    // Display the elements of the dynamic array
    dynamicArray.display();

    return 0;
}

Observing Memory Allocation and Copying

As we run the code, we’ll observe the following:

1. Memory Allocation: When the array reaches its capacity limit, a new, larger block of memory is allocated using the resizing strategy implemented in the push_back method.
2. Copying Elements: Existing elements from the old array are copied to the new array during the resizing process to ensure data integrity.
3. Capacity Expansion: The capacity of the dynamic array increases dynamically as elements are added, reflecting the resizing of the underlying memory.

Navigating the Trade-offs: Understanding Drawbacks of Custom Dynamic Arrays

While dynamic arrays offer unparalleled flexibility and convenience, they come with their own set of drawbacks that warrant careful consideration. In this section, we’ll explore two significant drawbacks of custom dynamic arrays implemented in C++: the slow nature of heap allocation and the performance impact of copying elements during resizing.

1. Slow Heap Allocation

Dynamic arrays rely on heap memory allocation to expand and contract dynamically, which can incur overhead due to the overhead of managing memory on the heap.

Heap allocation involves interacting with the operating system’s memory manager, which introduces overhead in terms of time and resources. Each allocation request may involve traversing data structures maintained by the memory manager to find a suitable block of memory, leading to variable allocation times.

Additionally, heap allocation may result in memory fragmentation over time, where the memory is divided into small, non-contiguous blocks, making it challenging to allocate large contiguous blocks efficiently.

2. Performance Impact of Copying Elements

When resizing a dynamic array, existing elements must be copied from the old array to the new array to ensure data integrity. This process can be time-consuming, especially for large arrays or arrays containing complex objects.

Copying elements involves iterating over each element in the old array and copying it to the corresponding position in the new array. For arrays with a large number of elements, this operation can become a performance bottleneck, impacting the overall efficiency of operations such as insertion and deletion.

Furthermore, copying elements may lead to unnecessary memory churn, where memory is allocated and deallocated frequently, potentially fragmenting the heap and degrading performance over time.

Mitigating Drawbacks

While the drawbacks of heap allocation and copying elements are inherent to dynamic arrays, there are strategies to mitigate their impact:

• Preallocation: Preallocating memory for the dynamic array based on an estimated size can reduce the frequency of resizing operations, minimizing the overhead of heap allocation and copying.
• Capacity Management: Implementing a smart resizing strategy, such as increasing the capacity by a constant factor or using exponential resizing, can reduce the frequency of resizing operations, mitigating the performance impact of copying elements.
• Memory Pools: Using custom memory pools or memory allocators tailored to the specific requirements of the application can improve memory allocation performance by reducing fragmentation and overhead associated with heap allocation.

Conclusion

While dynamic arrays offer unparalleled flexibility and convenience, they come with inherent drawbacks such as the slow nature of heap allocation and the performance impact of copying elements during resizing. By understanding these drawbacks and employing mitigation strategies, developers can make informed decisions when designing and using dynamic arrays in C++ applications, striking a balance between flexibility and performance.