realloc无效的旧大小

Question

免责声明:这是作业.我正在尝试它,不要指望或希望任何人为我做这件事.只是几个指针(呵呵),我出错了将不胜感激.

作业要求我创建一个int*包含10个元素的数组,然后尝试在其中插入一百万个int.每个插入检查是否需要调整数组的大小,如果需要,我会增加它的大小,以便它可以容纳一个元素.

当我插入10,000个元素时,它工作正常,但如果我尝试100,000个元素,我会收到以下错误:

*** glibc detected *** ./set2: realloc(): invalid old size: 0x00000000024dc010 ***

这是我正在运行的代码.我评论过它,因此很容易阅读.

void main()
{
    //begin with a size of 10
    int currentsize = 10;
    int* arr = malloc(currentsize * sizeof(int));       
    int i;

    //initalize with all elements set to INT_MAX
    for(i = 0; i < currentsize; i++) {
        arr[i] = INT_MAX;
    }


    // insert random elements
    for(i = 0; i < 100000; i++) {
        currentsize = add(rand() % 100,arr,currentsize);
    }

    free(arr);
}

/*
    Method resizes array if needed, and returns the new size of the array
    Also inserts the element into the array
*/
int add(int x, int* arr, int size)
{
    //find the first available location 
    int newSize = size;
    int i;
    for(i = 0; i < size; i++) {
        if (arr[i] == INT_MAX)
            break;
    }

    if (i >= size) {
        //need to realloc
        newSize++;
        arr = realloc(arr, newSize * sizeof(int) );     
    }

    arr[i] = x;

    return newSize;
}

Answer 1

该错误可能是因为您正确使用realloc来更改arr函数add,但add返回时此修改后的值将丢失.所以接下来的电话add会收到旧的,现在不好的价值.

另外我无法理解你为什么要使用for循环搜索.你知道你想在最后一个元素添加,为什么要搜索？只需重新分配阵列并将新值插入新插槽即可.

顺便说一句,我很确定你的老师试图让你看到每个成员的重新分配导致渐近的运行时问题.大多数实现realloc都会使用此算法进行大量复制.这就是真正的程序将数组大小增加一个因子(通常是1.5或2)而不是固定数量的原因.

通常的习惯用法是在结构中抽象变量大小的数组:

typedef struct array_s {
  int *elts;
  int size;
} VARIABLE_ARRAY;

void init(VARIABLE_ARRAY *a)
{
  a->size = 10;
  a->elts = malloc(a->size * sizeof a->elts[0]);
  // CHECK FOR NULL RETURN FROM malloc() HERE
}

void ensure_size(VARIABLE_ARRAY *a, size_t size) 
{
  if (a->size < size) {

    // RESET size HERE TO INCREASE BY FACTOR OF OLD SIZE
    // size = 2 * a->size;

    a->elts = realloc(size * sizeof a->elts[0]);
    a->size = size;

    // CHECK FOR NULL RETURN FROM realloc() HERE
  }
}

// Set the i'th position of array a. If there wasn't
// enough space, expand the array so there is.
void set(VARIABLE_ARRAY *a, int i, int val)
{
  ensure_size(a, i + 1);
  a->elts[i] = val;
}

void test(void)
{
  VARIABLE_ARRAY a;

  init(&a);

  for (int i = 0; i < 100000; i++) {
    set(&a, i, rand());
  }

  ...

}