Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

C99中的柔性数组

柔性数组是C99引入的feature。

1
2
3
4
5
struct Data
{
  int i;
  int a[0];
};

其中柔性数组a处于结构体的末尾,并且声明的大小为0。

那么它有什么性质呢?

1,首先,a不占用结构体空间。它只是一个占位符而已。因此

sizeof(Data) = sizeof(int) (这里的int是那个变量i)

2,我们可以利用a来分配动态内存:

1
Data *p = (Data*) malloc(sizeof(Data) + 10 * sizeof(int))

这样,p就包含了10个int型元素构成的数组。

3,有些人说,为什么我们不这样呢?

1
2
3
4
5
6
7
struct Data
{
  int i;
  int *a;
};
Data *p = (Data*) malloc(sizeof(Data));
p->a = (int*) malloc(10 * sizeof(int));

这样子不是挺好的么?是挺好的,但是这样结构体大小就得翻倍了,因为这下a不是占位符而是实实在在的指针变量了。

这还算小事。大事呢?这就是我们第三点要扯的:如果改成这样后,结构体成员i和数组a中的(首个)元素,地址将几乎肯定不是挨着的!!!这可能会带来很多问题,包括cache unfriendly等。

而如果使用柔性数组,我们可以简单做个实验发现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
struct Data
{
  int i;
  int a[0];
};
int main()
{
  Data *p = (Data*)malloc(sizeof(Data) + 100 * sizeof(int));
  cout<<&(p->i)<<endl;
  cout<<&(p->a[0])<<endl;
  cout<<sizeof(Data)<<endl;
  return 0;
}

在ubuntu 14.04 64位系统+gcc 4.8下编译运行后,程序输出:

0x8a9010
0x8a9014
4

不额外占用空间、实现变长结构体、连续地址。能同时做到这三点的,除了柔性数组,不知还能有谁?不过这玩意,个人意见能少用尽量少用,能不用尽量不用,毕竟可能有移植性问题。

柔性数组的一个很常见的应用是跳表(Skip List)。由于跳表中不同的节点拥有不尽相同的高度,每个节点所包含的后继指针数量也不尽相同,因此此时柔性数组的合理使用可以最大利用内存空间.