How do I change this array inside the function?

Question

This code is for a CS 235 class, but I'm new to C++ and I have no clue how they want me to do this. The grow function works by taking in an array and changing it to become twice as large. Coming from python, I guess this is the equivalent of mutating the array? Anyway, I can't get it do the same for the insert function. I need it to check if the position that we're trying to insert an item at is outside the array bounds and make the array big enough that it can insert the value. Everything works....inside the function. The array does not maintain the changes outside the function. I've tried passing it in as a pointer, as a (reference to a pointer?) like *&array, and basically any combination I can think of.

void grow(int *&original_array, unsigned int & capacity){
    int *temp = new int[capacity * 2];
    for (int i=0; i<capacity*2; i++){
        temp[i] = 0;
    }
    std::cout << "line 18: ";
    print_array(temp, capacity*2);
    for(int i=0; i<capacity; i++){
        temp[i] = original_array[i];
    }
    std::cout << "line 23: ";
    print_array(temp, capacity*2);

//    delete[] original_array;
    original_array = temp;
    std::cout << "line 27: ";
    print_array(original_array, capacity * 2);
    capacity = capacity * 2;
}

bool insert (int array[], unsigned int & maxSize, unsigned int & nFilled, unsigned int pos, int value){
    while (maxSize < pos){
        grow(array, maxSize);
        print_array(array, maxSize);
    }
    for(unsigned int i = nFilled - 1; i >= pos; i = i-1){
        array[i+1] = array[i];
    }
    array[pos] = value;
    print_array(array, maxSize);
    return true;
}

Here's some sample input and what my program outputs right now:

int main() {
    unsigned int my_size = 4;
    int new_array[4] = {1,2,3,4};
    unsigned int nFilled = 4;

    insert(new_array, my_size, nFilled, 5, 15);
    print_array(new_array, my_size);
    return 0;
}

Output:

line 18: {0, 0, 0, 0, 0, 0, 0, 0}
line 23: {1, 2, 3, 4, 0, 0, 0, 0}
line 27: {1, 2, 3, 4, 0, 0, 0, 0}
{1, 2, 3, 4, 0, 0, 0, 0}
{1, 2, 3, 4, 0, 15, 0, 0}
{1, 2, 3, 4, -152629248, 32758, 0, 8}

the second to last line is inside the function and the last one is outside the function. I need these to be the same

Any help is appreciated - the TA's and professors are being unhelpful

Thanks

Answer 1

There's two problems with your code working as written, the first one is that you can't reassign the value of new_array in main as written. As written it is not dynamically allocated, and so it cannot be changed. You will need to change that to be dynamically allocated:

int* new_array = new int[4];

for(int x = 0; x < 4; ++x)
{
    new_array[x] = x + 1;
}

That will address one issue, however the code still won't work, and that has to do with how variables are passed to insert and grow.

Your grow() function takes int*& a reference to a pointer to integer. This means that the underlying value passed in can be changed. However, your insert() function takes int[] an integer array that decays to to pointer to integer, and changes here will not be reflected at the call site of insert().

You can verify that by adding some more debugging statements:

bool insert (int array[],
    unsigned int & maxSize,
    unsigned int & nFilled,
    unsigned int pos,
    int value)
{

    // unchanged above...
    std::cout << "Inside insert: " << array << '\n';
    return true;
}


int main()
{
    // unchanged above...
    std::cout << "After insert: " << new_array << "\n";
    print_array(new_array, my_size);
    return 0;
}

You will get output similar to this:

line 18: {0 0 0 0 0 0 0 0 }
line 23: {1 2 3 4 0 0 0 0 }
line 27: {1 2 3 4 0 0 0 0 }
{1 2 3 4 0 0 0 0 }
{1 2 3 4 0 15 0 0 }
Inside insert: 0x548ed0
After insert: 0x548eb0
{1 2 3 4 0 0 49 0 }

Note that the array "Inside insert" and "After insert" are different.

To fix this, you need to make sure you pass something to insert() that allows for changing the value, similar to what was done for grow().

That change is as simple as changing the signature of insert() as follows:

bool insert (int *&array,
    unsigned int & maxSize,
    unsigned int & nFilled,
    unsigned int pos,
    int value)

Note the first parameter to insert() was changed to match the type in grow() a reference to pointer to integer. Now when we pass the pointer new_array to insert() a reference to that pointer is passed (which allows the value to be changed), and that is also passed to grow() (if necessary), allowing this to propagate all the way to the call site.

Be aware though there are stylistic problems with this approach -- unclear ownership semantics, potential for memory leaks (present in the posted code) etc.

I will also caveat that "reinventing" this type of data structure instead of using std::vector is not a good practice, however it does have its uses in a teaching context.