数组初始化中的 malloc() 问题

Question

我目前正在处理一项使用稀疏集的任务。在一个特定的函数中，我被要求 初始化 [0..max_value] 范围内的稀疏集数据结构。因此我假设必须使用 malloc() 。但是我认为我错误地实现了这个功能，因为单元测试不起作用。（capacity是最大可以存储的元素个数，而max_value是最大可以存储的整数值）

sparse_set_ptr ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {

    struct sparse_set *d_arr = malloc(sizeof(capacity));
    struct sparse_set *s_arr = malloc(sizeof(max_value) + 1);

    return d_arr->sparseSetPtr, s_arr->sparseSetPtr;
}

这是有问题的结构：

struct sparse_set {
    int *d_arr;
    int *s_arr;
    sparse_set_ptr sparseSetPtr;
};

感谢任何帮助:)

编辑：给定的稀疏集定义如下：

A sparse set is a data structure used to store small sets of data. Its main use is in applications where a fixed number of items/elements need to be tracked. Sparse sets are used in compilers, development frameworks and more. This data structure offers extremely fast lookup, insertion and deletion times while also being cache-friendly. As with normal sets, duplicate items are not accepted in sparse sets.

A sparse set consists of two arrays working in tandem. These two arrays are referred to as the dense array and the sparse array.

The dense array, as its name suggests, is a compact array that stores its elements sequentially, with no gaps between the elements.

On the other hand, the sparse array is used as a lookup list, and stores indices that map to elements in the dense array. Whenever an operation is performed, the dense and the sparse array must be kept in sync. For example, consider a sparse set ranging over the numbers [0..7]. This means it can only store the elements 0, 1, 2, 3, 4, 5, 6, and 7. Suppose we want to store a maximum of four elements. This means that the sparse set will contain a sparse array of size 8 and a dense array of size 4.

Answer 1

我还没有 100% 理解该函数应该做什么，但也许这会有所帮助：

// NOTE: ss_init() name is unclear: does this function have to initialize
//   arrays d_arr and s_arr with values?
// NOTE 2: I assume sparse_set_ptr is typedef struct sparse_set*
sparse_set_ptr ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {
  struct sparse_set* result = malloc(sizeof(struct sparse_set));

  if (result == NULL) {
    return NULL;
  }

  result->d_arr = malloc(sizeof(int) * capacity);

  if (result->d_arr == NULL) {
    free(result);
    return NULL;
  }

  result->s_arr = malloc(sizeof(int) * (max_value + 1));

  if (result->s_arr == NULL) {
    free(result->d_arr);
    free(result);
    return NULL;
  }

  // TODO: do we fill d_arr with values?
  // TODO: do we fill s_arr with values?

  // I don't understand the purpose of member "sparseSetPtr"
  result->sparseSetPtr = NULL;
  // or maybe
  result->sparseSetPtr = result;

  return result;
}

编辑：我更新了代码，因为问题不是很清楚。

编辑 2：该死的，缺少分号。现已修复。

编辑 3：我做了一些澄清。

Answer 2

首先，您提供的函数签名要求 sparse_set_ptr 被 returned。您对实际是什么类型含糊其辞，但假设它是 struct sparse_set * 似乎是合理的。在那种情况下，您需要为（一个）struct sparse_set 动态分配 space，初始化它，并 return 一个指向它的指针：

struct sparse_set *ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {
    // ... maybe validate parameters ...

    struct sparse_set *the_set = malloc(sizeof *the_set);

    // ... initialize here (see below) ...

    return the_set;
}

注意你的...

    return d_arr->sparseSetPtr, s_arr->sparseSetPtr;

... 肯定是错误的，至少因为它会泄漏内存。它相当于...

    return s_arr->sparseSetPtr;

.

其次，在您描述的稀疏集合实现中，密集数组将足够大以容纳与集合容量一样多的元素，并且稀疏数组将至少比集合可以容纳的最大元素值。那不是你提供的。随意使用不必要的 typedef 会使事情变得有点模糊，但是可能你在密集数组中提供了足够的 space 来容纳一个或两个元素，并且足够 space 在稀疏数组中的最大值为一或两个，尽管实际值为 capacity 和 max_value。你可能想要更多这样的东西：

    the_set->d_arr = calloc(capacity * sizeof(*the_set->d_arr));
    the_set->s_arr = calloc((max_value + 1) * sizeof(*the_set->s_arr));
    // ... check for and handle allocation failure ...

使用 calloc() 而不是 malloc() 会导致 space 被零填充，这是确保对 [=19= 的所有有效值进行成员资格测试的正确行为所必需的]. sizeof 子表达式的计算结果为被初始化指针指向的对象的大小（以字节为单位）（无论它们是什么，即使它们后来从现在的状态发生变化），这些大小是乘以所需元素的数量。

sparseSetPtr 成员的目的和预期用途不明确。相反，应该有一个成员传递集合的当前元素数（应设置为 0），一个成员传递集合允许的最大值。按照惯例，还会有一个成员传达集合的容量。如果你不这样做，那么你必须依赖集合的用户不要尝试添加超过其容量的元素。例如，给定 struct sparse_set ...

的替代版本

struct sparse_set {
    int *d_arr;
    int *s_arr;
    sparse_set_elem_t max_value;
    sparse_set_index_t capacity;
    sparse_set_index_t size;
};

...您可能会完成初始化：

    the_set->max_value = max_value;
    the_set->capacity = capacity;
    the_set->size = 0;

数组初始化中的 malloc() 问题

Issue with malloc() in array initialisation

c

malloc