Creating dynamically allocated array

Question

I am trying to create a dynamically allocated array, that when filled, creates a new array large enough to hold everything and copies all the values from the old array to the new array. I do in my append function, which when called dynamically allocates a new array with tmp pointing to it, and then moves the values from arr[i] to tmp [i]. However, I'm wondering if I need to delete tmp when I'm done with it? Because when I try to print the contents of the array without deleting tmp, it prints just fine, but when I do delete tmp, things just start getting weird and the contents no longer print the way they should. Here's my code:

ArrayList::ArrayList(int initsize): last(0), size(initsize), origsize(initsize)
{
    arr = new int[size];
}

ArrayList::ArrayList() 
{
    last = 0;
    size = 16;
    origsize = 16;
    arr = new int[size];
}

void ArrayList::append(int value) 
{
    if (last<size) {
        arr[last] = value;
    }

    last++;

    if (last == size) {

        int* tmp = new int[size+origsize];
        int i = 0;

        for (i=0; i<(size+origsize); i++)
            tmp[i] = arr[i];

        size = size+origsize;
        arr = tmp;
        arr[last] = value;

        //delete tmp;
    }
}

Answer 1

Your arr is now tmp. I mean they both points to a new array. And you need to delete the old one. Do

int* old = arr;
arr = tmp;
delete [] old;
arr[last] = value;

Answer 2

The problem is here:

for (i=0; i<(size+origsize); i++) {

        tmp[i] = arr[i];

    }

arr is of length 'size' but you are trying to access elements beyond it. It shall result in undefined behaviour.

IMO, you should not try to re-size an array in your program. If you want a dynamic sized container, use a std::vector instead.

EDIT: As others have pointed out, if this is for academic reason, then you can modify your code something like the following:

void ArrayList::append(int value) 
{
    if (last<size) {
        arr[last] = value;
        last++;
    } else { // last shall be equal to size.

        int* tmp = new int[size+origsize];
        int i = 0;

        for (i=0; i<(size); i++) // delete + originalsize
            tmp[i] = arr[i];

        size = size+origsize;
        int* newTemp = arr; // make a new pointer point to where arr was pointing
        arr = tmp;         // make arr point to where tmp was pointing.
        //tmp = newTemp; // You do not need this statement.
        arr[last] = value;
        last++;
        delete [] newTemp; // delete the old array memory block
    }
}

Answer 3

The new array is point to the old one.

So in your code(withou modifications) you cannot delete the arr

Answer 4

You definitely should delete tmp because, since you've declared it as a pointer using the *. It will not be automatically deallocated once you leave the scope (leaving the next }), and will cause a memory leak. Helpful post here about the pointer and how declaring it puts it on the heap and requires it to be manually deleted. Since you're trying to make a dynamic array here. I think you want arr to be the pointer, not tmp. Check out this c++ tutoriall

Answer 5

You are using new and delete, which is C-ish. In C++ you should be trusting existing facilities to handle memory for you. We could use std::vector, though it would thwart the exercise; instead I propose that we use std::unique_ptr.

class ArrayList {
public:
    ArrayList();

    explicit ArrayList(size_t i);

    void append(int i);

private:
    size_t last;                  // position to append to
    size_t size;                  // current size of the array
    std::unique_ptr<int[]> array; // actual array of data
}; // class ArrayList

Note: rather than using origsize, we can double the capacity at each expansion, thus gaining "amortized constant" complexity for append.

// We first need a creation function for raw memory:
std::unique_ptr<int[]> allocate(size_t n) {
    return std::unique_ptr<int[]>(new int[n]);
}

// Now, the default constructor
ArrayList::ArrayList(): last(0), size(16), array(allocate(size)) {}

// And the user constructor
ArrayList::ArrayList(size_t i): last(0), size(i), array(allocate(size)) {}

With this out of the way, let us focus on append:

void ArrayList::append(int e) {
    if (last >= size) { // need to reallocate
        std::unique_ptr<int[]> neo = allocate(size*2);

        for (size_t i = 0; i < size; ++i) {
            neo[i] = array[i];
        }

        size *= 2;
        swap(neo, array);
    } // reallocation

    array[last] = e;
    ++last;
}

How does it differ from your code:

1. When copying from one array to another, I only copy size elements (you were reading out of bounds)
2. I do not handle memory manually, instead I defer memory handling to std::unique_ptr.
3. There is no need to re-allocate after you inserted e in append, you can just wait to have run out of place to do so.
4. Using amortized constant complexity for append is more efficient