c++ - 实现手写动态数组的插入数组方法 - C++

Question

所以我的代码应该采用一个动态数组并向其中插入一个较小的数组，如果较大数组中没有足够的空间，那么它会创建一个新数组并将旧数组中的值复制到新数组中，以便可以插入较小的数组。这是为新数组分配新大小的代码，dynamic_array &a 是较小的数组，i 是它插入的位置:

void dynamic_array::insert(dynamic_array &a, int i) {

    if (i < 0 or i > size){
        throw exception(SUBSCRIPT_RANGE_EXCEPTION);
    }
    int *new_array;
    int range = a.get_size(); //my get size method will return how many values are in a
    int blocks_needed = (size) / BLOCK_SIZE;
    if (size % 5 > 0) {
        blocks_needed = blocks_needed + 1;   //add a block if needed
    }   

    if (size + range >= allocated_size) { //new space needed
        //get more space
        try {
            new_array = new int[blocks_needed * BLOCK_SIZE]; 
        } catch (bad_alloc){
            throw exception (MEMORY_EXCEPTION);
        }

然后有 3 个不同的 for 循环。一个复制 i-1 之前的所有元素。第二个复制数组 a 中的所有元素。第三个将旧数组中的所有剩余元素复制到新数组中，同时移动它们:

    //copy array[0..i-1]
    for (int j = 0; j < i; j++) {
        new_array[j] = array[j];
    }

    //copy a
    for (int m = i; m < range; m++){
        new_array[m] = a[m];
    }

    //copy array[i..size-1]
    for (int k = i; k < size; k++) {
        new_array[k+range] = array[k];
    }

然后我更新尺寸:

size = size + range;
allocated_size = blocks_needed * BLOCK_SIZE;

现在，如果已经有足够的空间，那么我只需将数组向右移动并通过 for 循环插入值:

else { //no new space needed
        shift_right(i, size, range);
        for (int z = i; z < range; z++){
            array[z] = a[z];
        }
        size = size + range;
    }

现在我得到的输出非常接近我想要的，但它并不完全是我想要的。很多时候，数组值显示诸如 0 3 0 2 4 之类的东西，而它应该显示 0 1 3 2 4。当它显示它应该是 10 而它是 5 时，分配的大小有时也是错误的。对于所有测试的数组来说，大小看起来都很好，但它只是分配的大小和数组值才是问题所在。这是我的右移函数:

void dynamic_array::shift_right(int start, int end, int delta){
        for(int i=end; i>=start; i--){
            array[i+delta] = array[i];
        }
    return;
}

Answer 1

好吧，虽然我们没有所讨论方法的所有代码，也没有 dynamic_array::shift_right() 代码，但我立即注意到两个错误(感谢@TheDark 对我的修复挑剔):

第一个:

for (int m = i; m < range; m++) { new_array[m] = a[m]; }

应该是

for (int m = i; m < range + i; m++) { new_array[m] = a[m - i]; }
//                        ^^^                            ^^^

最后一个相同类型的移动循环:

for (int z = i; z < range; z++) { array[z] = a[z]; }

应该是:

for (int z = i; z < range + i; z++) { array[z] = a[z - i]; }
//                        ^^^                        ^^^

事实上，这些可能会导致尝试越界访问 a[] 时发生崩溃。附带说明一下，这就是为什么使用迭代器比使用简单的整数索引进行容器访问更好、更安全的原因之一。

我也不喜欢这个:

int blocks_needed = (size) / BLOCK_SIZE;
if (size % 5 > 0) {
    blocks_needed = blocks_needed + 1;   //add a block if needed
}

这看起来很像手写 ceil()功能。除此之外，5 显然应该等于 BLOCK_SIZE，否则这对我来说意义不大。因此，将 5 替换为 BLOCK_SIZE 或更好的是切换到 ceil()。

现在介绍与分配相关的错误。这是一个:

int blocks_needed = (size) / BLOCK_SIZE;

int blocks_needed = (size + range) / BLOCK_SIZE;
//                        ^^^^^^^

这是另一个，虽然不是真正的错误，但它仍然是次优行为:

if (size + range >= allocated_size) { //new space needed

if (size + range > allocated_size) { //new space needed
//              ^^^