C/C++中的变长结构体

1. 问题来源

首先看下如下的一段代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_LEN 1024

typedef struct KDtree{
    double data[MAX_LEN]; // 数据
    int dim; // 选择的维度
    struct KDtree *left; // 左子树
    struct KDtree *right; // 右子树
}kdtree_node;

int main()
{
    kdtree_node *kd_node = (kdtree_node *)malloc(sizeof(kdtree_node));
    printf("kdtree_node: %ld\n", sizeof(kdtree_node)); // 8216
    printf("kd_node: %ld\n", sizeof(kd_node));
    free(kd_node);

    return 0;
}

在这段代码中，为了存储数据，申请了最大长度为1024的double型数组。若是数据的长度远远小于MAX_LEN，这样的写法，是及其浪费空间的。

2. 解决的方法

在Ｃ语言中，有如下的一种构建方法：

struct mumble {
	//stuff
	char pc[];    
};

对于这种最后一个成员的长度不固定的写法称为柔性数组，也叫伸缩性数组，即变长数组。即声明结构体的时候不指定声明的数组的大小，等到需要使用的时候根据具体情况申请足够大小的空间。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct mytest{
	int a;
	double b;
	int c[];  //c不占用空间，只是作为一个符号地址存在，而且必须是结构体的最后一个成员
}mt;

int main(){
    printf("mt: %ld\n", sizeof(mt));  // 16
	int t[10] = {0,1,2,3,4,5,6,7,8,9};
	mt* pmt = (mt*)malloc(sizeof(mt) + sizeof(int)*10 + 1);
    int i = 0;
    if (NULL != pmt){
        pmt->a = 1;
        pmt->b = 11;
        for (i = 0; i < 10; i++) {
            (pmt->c)[i] = t[i];
        }
    }
    free(pmt);
    return 0;
}

至于这里的sizeof(mt)为什么是16，涉及到sizeof对结构体计算时的地址对齐问题。意：柔性数组只能为结构体的最后一个成员。

参考文献

• 柔性数组-读《深度探索C++对象模型》有感