可变数组
专栏内容:
postgresql内核源码分析
手写数据库toadb
并发编程
个人主页:我的主页
座右铭:天行健,君子以自强不息;地势坤,君子以厚德载物.
概述
数组中元素是顺序存放,这一特性让我们存储和访问数据都很简单,
但也因为这一特性,我们在写代码时,往往不能确定数组元组的个数,只能按最大的数量进行预分配,
这不仅造成了空间浪费,而且使用起来不友好,明明我们要运行一个小数据集,但却要很多内存空间。这就产生了可变数组,它的元素数量不需要在代码中确定,而是在运行时确定。
实现方式
可变数组在我们的程序中经常遇到,但是它有那些实现方式呢?
根据数组存储内存区域的不同,可以分为
- 栈内存实现方式
- 堆内存实现方式
下面我们就来看看它们是如何实现,有什么不同
栈内存实现
这里C99中新增的VLA(variable-length array) 特性,可以让我们在用的时候定义数组,数组的长度不再是静态值,可以是变量中的值。
也就是说,数组的长度在程序编译阶段是不确定的,直到运行时再能确定,这就避够我们定义一个最大的数组,产生很多空间浪费。
- 举例
void test(int n)
{
/* check */
if(n <= 0)
{
return;
}
// int arr[n] = {0};
int arr[n];
/* todo */
for(int i=0; i < n; i++)
{
arr[i] = i;
}
return;
}
数组arr的长度是变量n来确定
- 注意事项
- 这个特性是C99引入,并不是所有的编译器都能完全支持,我使用的 gcc 版本是支持的。
[senllang@hatch toadbtest]$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/8/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-redhat-linux
Configured with: ../configure --enable-bootstrap --enable-languages=c,c++,fortran,lto --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-shared --enable-threads=posix --enable-checking=release --enable-multilib --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-gcc-major-version-only --with-linker-hash-style=gnu --enable-plugin --enable-initfini-array --with-isl --disable-libmpx --enable-offload-targets=nvptx-none --without-cuda-driver --enable-gnu-indirect-function --enable-cet --with-tune=generic --with-arch_32=x86-64 --build=x86_64-redhat-linux
Thread model: posix
gcc version 8.5.0 20210514 (Red Hat 8.5.0-19) (GCC)
- 使用VLA定义的数组,不能在定义时初始化,否则会产生以下错误,因为它不能使用默认的初始化器,必须由用户自己来初始化;
[senllang@hatch toadbtest]$ gcc test.c
test.c: In function ‘test’:
test.c:9:5: error: variable-sized object may not be initialized
int arr[n] = {0};
^~~
test.c:9:19: warning: excess elements in array initializer
int arr[n] = {0};
堆内存实现
在用的时候,通过malloc动态申请数组空间,空间大小为 数组元素类型的n倍,n是我们需要的数组大小,它可以是输入,也可以是程序运行过程中的可变值。
这种方式是我们普遍使用的,也是所有编译器都支持的。
- 举例
void test(int n)
{
int *arr = NULL;
/* check */
if(n <= 0)
{
return;
}
arr = (int *)malloc(sizeof(int)*n);
if(NULL == arr)
{
return ;
}
/* todo */
for(int i=0; i < n; i++)
{
arr[i] = i;
}
return;
}
访问方式
数组访问一般有指针方式和下标方式,这与普通数组没有什么区别,为什么要谈数组的访问方式呢? 因为这里会隐藏着惊天大坑,我们接着往下看。
C语言里一般,数组可以转成指针,当然指针也可以转成数组来用。
数组下标访问
这就很简单了,数组中的元素都是顺序排列,那么按它们的位置序号访问就可以。
对于VLA方式定义,还是动态申请方式分配的空间,它们的元素存储的内存空间都是连续的,所以两种方式下都可以用下标的方式来访问。
- 对于数组,那就再正常不过了,递增下标就可以获取到各元素的值;
- 而对于动态申请的数组,本身就是指向内存空间的首地址,也可以理解为指向数组的指针,即常说的数组指针,用下标的方式就可以直接获取到对应的元素值。
/* 如上面举例,指针类型定义的数组,也可以下标进行访问 */
int *arr = NULL;
arr[i] = i;
指针访问
指针形式访问,每次指针的移动步长,都是指针基础类型的字节数;
此时取值时,就要以指针的方式来取值;对于VLA方式定义,还是动态申请方式分配的空间,它们的元素存储的内存空间都是连续的,所以两种方式下都可以用指针的方式来访问。
- 对于数组,数组名就是首个元素的地址,遍历时每次递增+1,就会移动到下一个元素的地址;
- 而对于动态申请的数组,本身就是指向内存空间的首地址,也是0号元素的首地址;
int testarr[n];
int *arr = testarr;
for(int i = 0; i < n; i++,arr++)
{
*arr = i;
}
此处专门定义一个数组,然后将数组首地址赋给指针,用指针来访问数组元素
可变数组的嵌套使用
如果一个结构体里含有可变数组,同时结构体又存在嵌套,看起来都有点复杂,那它如何分配空间和访问呢?
定义
假如我们定义如下结构体,最终我们使用的是 stGroupData 这个结构体;
typedef struct Postion
{
int x;
int y;
}stPosition, *pstPostion;
typedef struct MemberData
{
int posCnt;
stPosition posArr[];
}stMemberData, *pstMemberData;
typedef struct GroupData
{
int group_id;
int memberCnt;
stMemberData memberData[];
}stGroupData, *pstGroupData;
大家是否好奇,上面结构的大小时多少呢?这个留给大家一个作业,知道答案的同学可以在评论区给出来。
分配空间
因为存在嵌套,所以就不能用VLA这个特性了,只能用动态分配了。
动态分配时,需要对外层结构体和内层结构体的元素分别计算,这里很容易遗漏;假设我们有一组数据,需要2个memberdata:
memberdata 0: 有3个postion
memberdata 1: 有1个postion
坑一:占用空间
空间需要分配多少呢?
- 可能初看好像是sizeof(stGroupData) 就可以了;
- 再看,其实需要 sizeof(stGroupData) + 2*sizeof(stMemberData) 大小;
这就掉坑里了。下面是正确的大小计算;
计算空间大小
int size = 0;
pstGroupData pgData = NULL;
/* 计算一个要分配的空间大小,假设2个memberdata:
* memberdata 0: 有3个postion
* memberdata 1: 有1个postion
*/
size = sizeof(stGroupData) + 2*sizeof(stMemberData) + 4 * sizeof(stPosition);
pgData = (pstGroupData)malloc(size);
这里计算size时,先计算结构体头部的size,因为数组部分没有定义长度,sizeof 出的来的值是不包含的,所以需要单独计算;
外层stGroupData中包含两个元素, 内层 stMemberData中分别为 3和1,也就是4个元素空间 ,再加上外层的结构体大小,就是整个所占的内存空间。
它们的内存空间分布情况,假设首地址从0开始
访问数组
那么按上面的例子,定义了一个结构体,如何访问各个数组元素呢?
可能有小伙伴立刻就想到了下标的方式 ,那么我们来看一下
坑二:下标访问
此时我们用下标方式引用会是正确的吗?
pgData->memberData[0]
pgData->memberData[1]
memberData[0] 与 memberData[1]的地址相差,应该是一个元素的sizeof(stMemberData) = 4,也就是一个int posCnt空间大小;
从内存分布图来看,就会变成这样
嵌套可变数组的访问
此时下标访问是不对的,不能采用默认的类型大小进行移动;
只能用指针方式来访问,同时需要自己计算下一个元素的偏移大小
pstMemberData pmData = NULL;
/* memberData[0] */
pmData = pgData->memberData;
/* memberData[1] */
pmData = (pstMemberData)((char*)(pgData->memberData) + sizeof(stMemberData) + 3 * sizeof(stPosition));
结尾
非常感谢大家的支持,在浏览的同时别忘了留下您宝贵的评论,如果觉得值得鼓励,请点赞,收藏,我会更加努力!
作者邮箱:study@senllang.onaliyun.com
如有错误或者疏漏欢迎指出,互相学习。文章来源:https://www.toymoban.com/news/detail-657120.html
注:未经同意,不得转载!文章来源地址https://www.toymoban.com/news/detail-657120.html
到了这里,关于C语言可变数组 嵌套的可变数组,翻过了山跨过了河 又掉进了坑的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!