可變數組

?專欄內容：
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 initializedint arr[n] = {0};^~~
test.c:9:19: warning: excess elements in array initializerint 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));