C++ dynamic array implementation

Question

As a C++ beginner coming from Java, I have become increasingly confused on the topic of memory management and how to avoid memory leaks. Is the code below risking a memory leak that I'm not currently aware of? Any help or constructive feedback would be greatly appreciated.

#pragma once

template <class T>
class DynamicArray {
private:
    T *m_arr;
    int m_length; //amount of elements currently being stored in the array
    int m_capacity; //actual size of the array
public:
    DynamicArray();
    ~DynamicArray();
    T get(int index); //O(1)
    void add(T obj); //no need to push any objects forward, O(1)
    void insert(int index, T obj); //pushes forward all objects in front of the given index, then sets the obj at the given index, O(n)
    void set(int index, T obj); //sets the given index of m_arr as obj, O(1)
    void remove(int index); //removes the object at the given index and pushes all the array contents back, O(n)
    int size(); //O(1)
    void print();
};

#include <iostream>
#include "Header.h"


template<class T>
DynamicArray<T>::DynamicArray() : m_arr(new T[1]), m_length(0), m_capacity(1) {}

template<class T>
DynamicArray<T>::~DynamicArray() {
    delete[] m_arr;
}

template<class T>
T DynamicArray<T>::get(int index) {
    if (index < m_length && index >= 0)
        return m_arr[index];
    else throw ("Index out of bounds!");
}

template<class T>
void DynamicArray<T>::set(int index, T obj) {
    if (index < m_length && index >= 0) {
        m_arr[index] = obj;
    } else throw ("Index out of bounds!");
}

template<class T>
void DynamicArray<T>::add(T obj) {
    if (m_length == m_capacity) {
        T *new_arr = new T[m_length * 2];

        for (int i = 0; i < m_length; i++) {
            new_arr[i] = m_arr[i];
        }

        delete[] m_arr;
        m_arr = new_arr;
        m_capacity = m_capacity * 2;
    }
    m_arr[m_length] = obj;
    m_length++;
}

template<class T>
void DynamicArray<T>::insert(int index, T obj) {
    if (index < m_length && index >= 0) {
        int size;
        if (m_length == m_capacity) size = m_length * 2;
        else size = m_capacity;
        T *new_arr = new T[size];

        for (int i = 0, j = 0; i < m_length; i++, j++) {
            if (i == index) {
                new_arr[j] = obj;
                j++;
            }
            new_arr[j] = m_arr[i];
        }

        delete[] m_arr;
        m_arr = new_arr;
        m_capacity = m_capacity * 2;
        m_length++;
    } else throw ("Index out of bounds!");
}

template<class T>
void DynamicArray<T>::remove(int index) {
    if (index < m_length && index >= 0) {
        T *new_arr = new T[m_capacity];

        for (int i = 0, j = 0; i < m_length; i++, j++) {
            if (i == index) i++;
            if(i < m_length) new_arr[j] = m_arr[i];
        }

        delete[] m_arr;
        m_arr = new_arr;
        m_capacity = m_capacity * 2;
        m_length--;
    } else throw ("Index out of bounds!");
}

template<class T>
int DynamicArray<T>::size() {
    return m_length;
}

template<class T>
void DynamicArray<T>::print() {
    std::cout << m_arr[0];
    for (int i = 1; i < m_length; i++) {
        std::cout << ", " << m_arr[i];
    }
}

Answer 1

Welcome to C++, and welcome to Code Review.

C++ memory management is, as you probably have realized, tough and error-prone. There are many things that can easily go wrong. Assuming that no exception is thrown, I don't see obvious memory leaks in your code; however, there are still some issues worth discussing.

You can take a look at my implementation of a non-resizable dynamic array or a stack-based full-fledged vector for some inspiration.

Special member functions

You have not defined copy constructors or move constructors, so the compiler will synthesize corresponding constructors that simply copy all the members — which is completely wrong, as now the two dynamic arrays will point to the same memory. Not only are the elements shared between the copies, causing modifications to one array to affect the other, but the two copies will attempt to free the same memory upon destruction, leading to a double-free error, which is way more serious than a memory leak.

Initialization semantics

It is generally expected that the constructor of the element type is called \$n\$ times if \$n\$ elements are pushed into the dynamic array. In your code, however, this is not the case, whre the amount of constructors called is determined by the capacity of the dynamic array. Elements are first default initialized, and then copy-assigned to.

The correct way to solve this problem requires allocating an uninitialized buffer, and using placement new (or equivalent features) to construct the elements, which is another can of worms.

Exception safety

Think of what happens when the construction of an element throws an exception — your code will halt halfway, and there will be a memory leak. Resolving this problem would require a manual try block, or standard library facilities like std::uninitialized_copy (which essentially do the same under the hood) if you switched to uninitialized buffers and manual construction.

Move semantics

All of the elements are copied every time, which is wasteful. Make good use of move semantics when appropriate.

Miscellaneous

Used std::size_t instead of int to store sizes and indexes.¹

get, size, and print should be const. Moreover, get should return a const T&. In fact, get and set would idiomatically be replaced by operator[].

Don't throw a const char*. Use a dedicated exception class like std::out_of_range instead.

Manual loops like

for (int i = 0; i < m_length; i++) {
    new_arr[i] = m_arr[i];
}

are better replaced with calls to std::copy (or std::move).

Re-allocating every time insert is called doesn't seem like a good idea. A better trade-off might be to append an element and then std::rotate it to the correct position (assuming rotation doesn't throw).

Also, print might take an std::ostream& (or perhaps std::basic_ostream<Char, Traits>&) argument for extra flexibility.

---

¹ As Andreas H. pointed out in the comments, this recommendation is subject to debate, since the use of unsigned arithmetic has its pitfalls. An alternative is to use std::ptrdiff_t and std::ssize (C++20) instead. You can write your own version of ssize as shown on the cppreference page if C++20 is not accessible.

Answer 2

• delete looks strange. There is no reason to create new_arr. Everything can (and should) be done in place. BTW, m_capacity = m_capacity * 2; there is just wrong (I suspect a copy-paste from insert).

• if in a tight loop incurs a strong performance penalty. Consider breaking the insertion loop into two:

    for (int i = 0,; i < index; i++) {
        new_arr[i] = arr[i];
    }
  
    new_arr[index] = obj;
  
    for (int i = index; i < m_length; i++) {
        new_arr[index + 1] = arr[index];
    }
  

• Which brings us to the next point: no naked loops. Two loops above copy ranges. Factor them into a function:

    copy_range(new_arr, arr, index);
    new_arr[index] = obj;
    copy_range(new_arr + index + 1, arr + index, m_length - index);
  

  Idiomatically, copy_range better be expressed in tems of iterators rather then indices.

• Consider shrinking the array after too many removals.

Answer 3

Const Correctness

A member function that doesn't modify the underlying object should normally be a const member function. For example:

    T get(int index); //O(1)

This doesn't modify the contents of the DynamicArray, and returns the element by value (not reference) so client code can't get access to the DynamicArray's internal data to modify it either. As such, this should almost certainly be a const member function:

    T get(int index) const;

Avoiding Unnecessary Copying

Right now your add, insert and set member functions all accept T objects by value.

void add(T obj);
void insert(int index, T obj);
void set(int index, T obj);

This means that when you're adding/inserting/setting an element in the DynamicArray, you're starting with one copy of the object in the client code, then copying that object to pass as an argument, then doing a copy assignment to put it into the array. For types that are "cheap" to copy (e.g., int) that's fine, but for types that are expensive to copy (e.g., if somebody creates a DynamicArray<DynamicArray<int>> where each sub-array is several megabytes of data) this would get extremely slow.

To avoid (at least some of) that copying, you can pass the input by reference instead:

void add(T const &obj);
void insert(int index, T const &obj);
void set(int index, T const &obj);

This avoids creating the copy solely for argument passing, so you end up with only two instances of the object: one in the client code and one in the array itself, but not an extra one being passed as the parameter.

Using a reference to a const object allows the reference to refer to a temporary object. For example, assume I have some Complex type that represents a complex number. If I have an expression like myComplex + yourComplex, that will create a temporary object. A reference to a const object can refer to that temporary (but without the const qualifier it can't).

Rule of 0/3/5

In C++, there's kind of a general rule that if you need to implement any of assignment, copy construction, and destruction, you probably need to implement all three to get a class that manages its resources correctly.

You have a destructor, and yes, you really need to do something to deal with copy construction and copy assignment. For example, if you create a copy of a DynamicArray:

    DynamicArray<int> foo;
    DynamicArray<int> bar = foo;

...the result tends to be on the ugly side (e.g., typically a core dump).

So you generally want to either implement (at least) copy construction and copy assignment, or else prevent code that tries to do it from compiling, usually with something like this:

    DynamicArray(DynamicArray const &) = delete;
    DynamicArray &operator=(DynamicArray const &) = delete;

Although it's not necessary to get correct (non-crashing) behavior, you may want to support move construction and move assignment as well:

    DynamicArray(DynamicArray &&) = delete;
    DynamicArray &operator=(DynamicArray &&) = delete;

So the rule of three covers destruction, copy construction and copy assignment. Adding move assignment and move construction gives the rule of 5.

That leaves the rule of 0: don't do any of this. In many cases you can use something like an std::unique_ptr to automate handling of the copying/assignment/destruction, so your class doesn't need to do any of the above.

Answer 4

Your implementations for "insert" and "remove" are very inefficient. First, there is no obvious reason why "remove" would reallocate the array. And there is no reason why "insert" would always reallocate the array. Here's what I would do:

1. Add a private method where you pass the intended capacity. If the intended capacity is greater than the capacity, it increases the array size. If the intended capacity is much less than the capacity, decrease the array size.

2. For "add", set the intended capacity to length + 1, then add the element. For "insert", set the intended capacity to length + 1, copy the elements at the end of the vector using copy_backwards, then store the new element. For "remove", use std::copy to move everything in the right place, then set the intended size to length - 1.

3. For "insert", you should allow the position (length), with the same effect as "add".

Using std::copy and std::copy_backwards means that instead of a for-loop you will run the most optimised code possible to move the array elements.

PS. Apple uses an array implementation that makes inserting / removing array elements both at the beginning and the end of the array cheap (operations at index i take O (min (i, length - i)) steps); this is done by allowing element 0 to be stored anywhere in the array, and allowing the array to wrap around at the end of the storage).

PPS. If you shrink the array when it becomes too small, make sure that you can't run into a situation where inserting one element grows the array, then deleting one element shrinks it, etc. etc.