柔性数组,这个名词对我来说算是比较新颖的,在学习跳跃表的实现时看到的。这么好听的名字,的背后到底是如何的优雅。
柔性数组,其名称的独特和迷惑之处在于“柔性”这个词。
在C/C++中定义数组,是一个定长的数据结构,最常用的定义如下
int arr[100];
上述代码的中arr
数组的长度已知,我们把上面的语句称之为声明语句,因为在编译期数组的长度已经确定了,我暂且发明了一个词来称呼这类数组——“刚性”数组(声明,这个词是我臆想的,是不存在这种说法的)。
你可能会说:等等,C/C++不是有可以在运行期通过malloc
调用来创建动态数组的做法吗?
没错,柔性数组正是需要malloc
来实现的,其柔性也是在这个地方体现的。
套路先行
我们先来看一看柔性数组到底是用来干什么的吧?
柔性数组(flexible array member)也叫伸缩性数组成员,这种结构产生与对动态结构体的去求。在日常编程中,有时需要在结构体中存放一个长度是动态的字符串(也可能是其他数据类型),一般的做法,实在结构体中定义一个指针成员,这个指针成员指向该字符串所在的动态内存空间。
在通常情况下,如果想要高效的利用内存,那么在结构体内部定义静态的数组是非常浪费的行为。其实柔性数组的想法和动态数组的想法是一样的。
先修知识
-
不完整类型
在C/C++中对于不完整类型的定义是这样的:
不完整类型是一种缺乏足够的信息去描述一个完整对象的类型
还是以数组的定义/声明为例子。
// 一个为知长度的数组属于不完整类型
// 这个语句属于声明语句,不是定义语句
extern int a[];
// 这样的语句是错误的, extern关键字不能去掉
// int a[]
// 不完整类型的数组需要补充完整才能使用
// 下面的语句是声明语句(定义+初始化)
int a[] = {10, 20};
-
结构体
看到这个标题的你可能会说,什么?结构体还用得着你来补充?
如果各位看官对结构体和内存对其比较熟悉的话,可以跳过这部分,看总结本段的总结,对后面柔性数组的说明有点帮助。
对于内存对齐的部分已经超出了文章所要讨论的内容了。那我想讲的是什么东西,且看下面的代码
#include<stdio.h>
struct test{
int i;
char *p;
};
int main(void){
struct test t;
printf("t: %p
", &t);
printf("t.i: %p
", &(t.i));
printf("t.p: %p
", &(t.p));
}
我们看到t.i
的地址和t
的地址是一样的。t.p
的地址就是(&t + 0x8)
,0×8这个偏移地址就是成员p在编译时就被编译器给hard code了的地址。
总结:不管结构体的实例是什么,访问其成员就是实例的地址加上成员偏移量。这个偏移量是编译器hard code的,跟内存对齐等因素有关。
千呼万唤始出来
我们来回顾一下,柔性数组用来在结构体中存放一个长度动态的字符串。
其实不用柔性数组我们一样可以做到:在结构体中定义一个方法,在方法中动态地将指针指向动态数组
#include<cstring>
#include<cstdlib>
#include<cstdio>
struct Test{
int a;
char *p;
void set_str(const char *str){
int len = std::strlen(str);
if(len <=0)
return;
p = (char*)std::malloc((len+1)*sizeof(char));
std::strcpy(p, str);
p[len] = '