make dynamic array larger

Question

This is for a non-graded challenge problem where I am looking to find as many prime numbers as fast as possible. One of the constraints is that I must use new/delete, so std::vector is not an option. In this problem, I need to add to an array (in my case a dynamically created array named list) that holds the primes. My goal is to achieve similar functionality to vector, where new memory only needs to be allocated if there isn't enough room in the current array, and when the current array fills up a new array with 2 times the length is allocated. My function to add a prime to the list is below

void PrimeList::addPrimeToList(int newPrime) {
    if( sizeof(list)/sizeof(int) > total ) { // there is still room in the array
        list[total++] = newPrime;
    } else { // list has run out of space to  put values into
        int *newList = new int [total*2]; // new list to hold all previous primes and new prime
        for(int i=0; i < total; i++) { // for every old prime
            newList[i] = list[i]; // add that old prime to the new list
        }
        newList[total++] = newPrime; // set largest and the last index of the new list to the new prime
        delete [] list; // get rid of the old list
        list = newList; // point the private data member list to the newly created list.
    }
}

Note: total is a private data member that holds the amount of primes found up to this point.

My issue is that the else statement (and the time consuming allocation/deallocation) is happening every single time the function is called (with the exception that the very first two calls always run the first part of the if). I would think that the if part would run the vast majority of the time - whenever the list still has space - so why isn't it?

score 1 · Accepted Answer · answered Jan 27 '15 at 05:29

The reason this happens is that the expression that you use for the array size, i.e.

sizeof(list)/sizeof(int)

is a constant expression. Its value is not dependent on the allocated array pointed to by the list pointer.

You need to store the allocated size separately to make this code work:

if( allocatedSize > total ) { // there is still room in the array
    list[total++] = newPrime;
} else { // list has run out of space to  put values into
    int *newList = new int [total*2]; // new list to hold all previous primes and new prime
    allocatedSize *= 2;
    for(int i=0; i < total; i++) { // for every old prime
        newList[i] = list[i]; // add that old prime to the new list
    }
    newList[total++] = newPrime; // set largest and the last index of the new list to the new prime
    delete [] list; // get rid of the old list
    list = newList; // point the private data member list to the newly created list.
}

make dynamic array larger

1 Answers1