使动态数组变大

Question

这是一个非分级挑战问题，我希望尽快找到尽可能多的素数。其中一个限制是我必须使用 new/delete，因此 std::vector 不是一个选项。在这个问题中，我需要添加一个包含素数的数组（在我的例子中是一个动态创建的名为列表的数组）。我的目标是实现与 vector 类似的功能，如果当前数组中没有足够的空间，并且当当前数组填满分配长度的 2 倍的新数组时，才需要分配新内存。我向列表中添加一个素数的函数如下

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.
    }
}

注意：total 是一个私有数据成员，它包含到目前为止找到的素数数量。

我的问题是 else 语句（和耗时 allocation/deallocation）每次调用函数时都会发生（除了前两个调用总是运行第一个if 的一部分）。我认为 if 部分在绝大多数情况下都会运行 - 只要列表仍然有 space - 那为什么不呢？

Answer 1

发生这种情况的原因是您用于数组大小的表达式，即

sizeof(list)/sizeof(int)

是常量表达式。它的值不依赖于 list 指针指向的分配数组。

您需要单独存储分配的大小才能使此代码正常工作：

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

c++

arrays

primes

dynamic