C++ 如何避免重新分配指针数组时，我们从一开始就不知道确切的大小

发布于04月04日

我试图设计一个像data—struct一样的二元树，除了每个 node 可以有的子元素没有限制.现在，在每个 node 中，我可以这样声明node struct:

struct node {
  int id;
  int num_children;
  struct node ** child;
};

我的问题是，有没有办法避免使用:

realloc在这种情况下，所以当你释放和重新分配内存时，不要结束大量的碎片？每次我添加一个新的子元素将需要经过这个过程，
在数组中静态分配有限数量的指针，这意味着(a)在某个点上，我将无法添加到它(b)一些 node 将没有子元素，所以这是一种浪费&

推荐答案

首先分配固定数量的子指针，然后添加一个成员来存储列表的当前容量. 当你go 添加一个子元素到列表，如果列表是一个容量，两倍大小. 这将减少您需要做的重新定位的数量.

所以一个 node 被修改为如下所示:

struct node {
  int id;
  int capacity;
  int num_children;
  struct node ** child;
};

要创建 node ，请执行以下操作:

struct node *newnode = malloc(sizeof *newnode);
newnode->num_children = 0;
newnode->capacity = 10;
newnode->child = malloc(sizeof *newnode->child * newnode->capacity);

要在能力时添加一个子元素:

if (current->capacity == current->num_children) {
    current->capacity *= 2;
    current->child = realloc(current->child, 
         sizeof *current->child * newnode->capacity);
}
current->child[current->num_children++] = new_child;

注意:为了简洁起见，省略了错误判断.