可變數(shù)組

?專欄內(nèi)容：
postgresql內(nèi)核源碼分析
手寫(xiě)數(shù)據(jù)庫(kù)toadb
并發(fā)編程
個(gè)人主頁(yè)：我的主頁(yè)
座右銘：天行健，君子以自強(qiáng)不息；地勢(shì)坤，君子以厚德載物.

概述

數(shù)組中元素是順序存放，這一特性讓我們存儲(chǔ)和訪問(wèn)數(shù)據(jù)都很簡(jiǎn)單，
但也因?yàn)檫@一特性，我們?cè)趯?xiě)代碼時(shí)，往往不能確定數(shù)組元組的個(gè)數(shù)，只能按最大的數(shù)量進(jìn)行預(yù)分配，
這不僅造成了空間浪費(fèi)，而且使用起來(lái)不友好，明明我們要運(yùn)行一個(gè)小數(shù)據(jù)集，但卻要很多內(nèi)存空間。

這就產(chǎn)生了可變數(shù)組，它的元素?cái)?shù)量不需要在代碼中確定，而是在運(yùn)行時(shí)確定。

實(shí)現(xiàn)方式

可變數(shù)組在我們的程序中經(jīng)常遇到，但是它有那些實(shí)現(xiàn)方式呢？
根據(jù)數(shù)組存儲(chǔ)內(nèi)存區(qū)域的不同，可以分為

• 棧內(nèi)存實(shí)現(xiàn)方式
• 堆內(nèi)存實(shí)現(xiàn)方式
  下面我們就來(lái)看看它們是如何實(shí)現(xiàn)，有什么不同

棧內(nèi)存實(shí)現(xiàn)

這里C99中新增的VLA(variable-length array) 特性，可以讓我們?cè)谟玫臅r(shí)候定義數(shù)組,數(shù)組的長(zhǎng)度不再是靜態(tài)值，可以是變量中的值。
也就是說(shuō)，數(shù)組的長(zhǎng)度在程序編譯階段是不確定的，直到運(yùn)行時(shí)再能確定，這就避夠我們定義一個(gè)最大的數(shù)組，產(chǎn)生很多空間浪費(fèi)。

• 舉例

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;
}

數(shù)組arr的長(zhǎng)度是變量n來(lái)確定

• 注意事項(xiàng)

1. 這個(gè)特性是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)

2. 使用VLA定義的數(shù)組，不能在定義時(shí)初始化，否則會(huì)產(chǎn)生以下錯(cuò)誤，因?yàn)樗荒苁褂媚J(rèn)的初始化器，必須由用戶自己來(lái)初始化；

[senllang@hatch toadbtest]$ gcc test.c
test.c: In function ‘test’:
test.c:9:5: error: variable-sized object may not be initializedint arr[n] = {0};^~~
test.c:9:19: warning: excess elements in array initializerint arr[n] = {0};

堆內(nèi)存實(shí)現(xiàn)

在用的時(shí)候，通過(guò)malloc動(dòng)態(tài)申請(qǐng)數(shù)組空間，空間大小為 數(shù)組元素類型的n倍，n是我們需要的數(shù)組大小，它可以是輸入，也可以是程序運(yùn)行過(guò)程中的可變值。

這種方式是我們普遍使用的，也是所有編譯器都支持的。

• 舉例

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;
}

訪問(wèn)方式

數(shù)組訪問(wèn)一般有指針?lè)绞胶拖聵?biāo)方式，這與普通數(shù)組沒(méi)有什么區(qū)別，為什么要談數(shù)組的訪問(wèn)方式呢？ 因?yàn)檫@里會(huì)隱藏著驚天大坑，我們接著往下看。

C語(yǔ)言里一般，數(shù)組可以轉(zhuǎn)成指針，當(dāng)然指針也可以轉(zhuǎn)成數(shù)組來(lái)用。

數(shù)組下標(biāo)訪問(wèn)

這就很簡(jiǎn)單了，數(shù)組中的元素都是順序排列，那么按它們的位置序號(hào)訪問(wèn)就可以。

對(duì)于VLA方式定義，還是動(dòng)態(tài)申請(qǐng)方式分配的空間，它們的元素存儲(chǔ)的內(nèi)存空間都是連續(xù)的，所以兩種方式下都可以用下標(biāo)的方式來(lái)訪問(wèn)。

• 對(duì)于數(shù)組，那就再正常不過(guò)了，遞增下標(biāo)就可以獲取到各元素的值；
• 而對(duì)于動(dòng)態(tài)申請(qǐng)的數(shù)組，本身就是指向內(nèi)存空間的首地址，也可以理解為指向數(shù)組的指針，即常說(shuō)的數(shù)組指針，用下標(biāo)的方式就可以直接獲取到對(duì)應(yīng)的元素值。

/* 如上面舉例，指針類型定義的數(shù)組，也可以下標(biāo)進(jìn)行訪問(wèn) */
int *arr = NULL;
arr[i] = i;

指針訪問(wèn)

指針形式訪問(wèn)，每次指針的移動(dòng)步長(zhǎng)，都是指針基礎(chǔ)類型的字節(jié)數(shù)；
此時(shí)取值時(shí)，就要以指針的方式來(lái)取值；

對(duì)于VLA方式定義，還是動(dòng)態(tài)申請(qǐng)方式分配的空間，它們的元素存儲(chǔ)的內(nèi)存空間都是連續(xù)的，所以兩種方式下都可以用指針的方式來(lái)訪問(wèn)。

• 對(duì)于數(shù)組，數(shù)組名就是首個(gè)元素的地址，遍歷時(shí)每次遞增+1，就會(huì)移動(dòng)到下一個(gè)元素的地址；
• 而對(duì)于動(dòng)態(tài)申請(qǐng)的數(shù)組，本身就是指向內(nèi)存空間的首地址，也是0號(hào)元素的首地址；

int testarr[n];
int *arr = testarr;for(int i = 0; i < n; i++,arr++)
{*arr = i;
}

此處專門(mén)定義一個(gè)數(shù)組，然后將數(shù)組首地址賦給指針，用指針來(lái)訪問(wèn)數(shù)組元素

可變數(shù)組的嵌套使用

如果一個(gè)結(jié)構(gòu)體里含有可變數(shù)組，同時(shí)結(jié)構(gòu)體又存在嵌套，看起來(lái)都有點(diǎn)復(fù)雜，那它如何分配空間和訪問(wèn)呢？

定義

假如我們定義如下結(jié)構(gòu)體，最終我們使用的是 stGroupData 這個(gè)結(jié)構(gòu)體；

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;

大家是否好奇，上面結(jié)構(gòu)的大小時(shí)多少呢？這個(gè)留給大家一個(gè)作業(yè)，知道答案的同學(xué)可以在評(píng)論區(qū)給出來(lái)。

分配空間

因?yàn)榇嬖谇短?#xff0c;所以就不能用VLA這個(gè)特性了，只能用動(dòng)態(tài)分配了。
動(dòng)態(tài)分配時(shí)，需要對(duì)外層結(jié)構(gòu)體和內(nèi)層結(jié)構(gòu)體的元素分別計(jì)算，這里很容易遺漏；

假設(shè)我們有一組數(shù)據(jù)，需要2個(gè)memberdata:

memberdata 0: 有3個(gè)postion
memberdata 1: 有1個(gè)postion

坑一：占用空間

空間需要分配多少呢？

• 可能初看好像是sizeof(stGroupData) 就可以了；
• 再看，其實(shí)需要 sizeof(stGroupData) + 2*sizeof(stMemberData) 大小；

這就掉坑里了。下面是正確的大小計(jì)算；

計(jì)算空間大小

int size = 0;
pstGroupData pgData = NULL;/* 計(jì)算一個(gè)要分配的空間大小，假設(shè)2個(gè)memberdata:* memberdata 0: 有3個(gè)postion* memberdata 1: 有1個(gè)postion */
size = sizeof(stGroupData) + 2*sizeof(stMemberData) + 4 * sizeof(stPosition);
pgData = (pstGroupData)malloc(size);

這里計(jì)算size時(shí)，先計(jì)算結(jié)構(gòu)體頭部的size，因?yàn)閿?shù)組部分沒(méi)有定義長(zhǎng)度，sizeof 出的來(lái)的值是不包含的，所以需要單獨(dú)計(jì)算；
外層stGroupData中包含兩個(gè)元素， 內(nèi)層 stMemberData中分別為 3和1，也就是4個(gè)元素空間 ，再加上外層的結(jié)構(gòu)體大小，就是整個(gè)所占的內(nèi)存空間。
它們的內(nèi)存空間分布情況，假設(shè)首地址從0開(kāi)始

訪問(wèn)數(shù)組

那么按上面的例子，定義了一個(gè)結(jié)構(gòu)體，如何訪問(wèn)各個(gè)數(shù)組元素呢？
可能有小伙伴立刻就想到了下標(biāo)的方式 ，那么我們來(lái)看一下

坑二：下標(biāo)訪問(wèn)

此時(shí)我們用下標(biāo)方式引用會(huì)是正確的嗎？

pgData->memberData[0] 
pgData->memberData[1] 

memberData[0] 與 memberData[1]的地址相差，應(yīng)該是一個(gè)元素的sizeof(stMemberData) = 4,也就是一個(gè)int posCnt空間大小；
從內(nèi)存分布圖來(lái)看，就會(huì)變成這樣

嵌套可變數(shù)組的訪問(wèn)

此時(shí)下標(biāo)訪問(wèn)是不對(duì)的，不能采用默認(rèn)的類型大小進(jìn)行移動(dòng)；
只能用指針?lè)绞絹?lái)訪問(wèn)，同時(shí)需要自己計(jì)算下一個(gè)元素的偏移大小

pstMemberData pmData = NULL;/* memberData[0] */
pmData = pgData->memberData;/* memberData[1] */
pmData = (pstMemberData)((char*)(pgData->memberData) + sizeof(stMemberData) + 3 * sizeof(stPosition));

結(jié)尾

非常感謝大家的支持，在瀏覽的同時(shí)別忘了留下您寶貴的評(píng)論，如果覺(jué)得值得鼓勵(lì)，請(qǐng)點(diǎn)贊，收藏，我會(huì)更加努力！

作者郵箱：study@senllang.onaliyun.com
如有錯(cuò)誤或者疏漏歡迎指出，互相學(xué)習(xí)。

注：未經(jīng)同意，不得轉(zhuǎn)載！