陣列配置方式 - 靜態、動態、VLA

goodbye_mylove

可變長度陣列 (Variable Length Array, VLA) 記得之前在各帖中都有討論過，
但突然要找又找不到，特發此帖一次討論完。
以下敘述，避開 scope 問題，若內容有誤，請不吝指正。

-------------
1. 靜態陣列 (Static Array)

早期接觸陣列時，都是給一定的陣列大小，如

1.     int arr[5];

複製代碼

或是設初始值，讓 compiler 在編譯時計算其大小，如

1.     int arr[] = {0,0,0,0,0};

複製代碼

若要把元素個數定義成一 macro 也行

1.     #define N 5
   
2.     int arr[N];

複製代碼

甚至用 const 方式定義元素個數也可

1.     const int N = 5
   
2.     int arr[N];

複製代碼

上面這四種方式，包含 define 、 const ，
這些都在編譯期 (compile time) 時完成的事情，
( const 和 編譯期 要解說的話會複雜一點，此處避開不談 )
只要是在「編譯期」就可確定陣列大小的，這裡都叫 Static Array。

------------------

2. 動態陣列 (Dynamic Array)

動態陣列具一特性：無時無刻都可以改變陣列的大小。
意思是你可以突然使陣列變大，也可以突然讓它變小，甚至完全不用它。
在 C/C++ 中，常用 malloc / new 方式進行，如

1.     /* in C language */
   
2.     int N, *x;
   
3.     scanf("%d", &N);
   
4.     x = (int*)malloc(sizeof(int) * N);
   
5.     /* do something */
   
6.     free(x);

複製代碼

或

1.     /* in C++ language */
   
2.     int N, *x;
   
3.     cin >> N;
   
4.     x = new int[N];
   
5.     /* do something */
   
6.     delete [] x;

複製代碼

在 C99 標準公佈之前，
只要陣列的元素個數，是在程式執行的時候 (Run time, 執行期) 才決定的，
那就一定要用 Dynamic Array 方式配置記憶體空間，
上述的二段程式碼，N 都是在執行期時，由使用者輸入決定的 (由運算得到也一樣)，
故必須使用 Dynamic Array 方式。
Dynamic Array 也可配置多維陣列，此處不予以多談。

副帶一題，真正的「動態」，
我認為可能是 C 語言的 malloc + remalloc 稱之較為合適。

---------------------

3. Static Array / Dynamic Array 差異

第一點差異已由上面提出來了，
static array 是在 compile time 決定元素個數；
dynamic array 是在 run time 決定元素個數。

第二個差異，
dynamic array 不論在配置、釋放記憶體時，
花費時間會較長，故程式中若有一段不停地進行配置、釋放動作，
這時可能要用一點技巧去減少配置、釋放所花費之時間。

第三個差異，
dynamic array 實際上是在 heap 上做配置；
static array 實際上是在 stack 上做配置。
heap 上可實用的記憶體大小，乃依作業系統有所差異，
在 XP 系統中，單一程式最多可使用記憶體為 2G/3G (依版本有所不同)，
而 stack 卻遠遠比這數值還小。

看下面例子

1. #include <iostream>
   
2. using namespace std;
   
3. #define N 1000000
   
4. int main()
   
5. {
   
6.      int i, sum;
   
7.      int x[N];
   
8.      for(i=0; i!=N; ++i) x[i]=i;
   
9.      for(i=0; i!=N; ++i) sum+=x[i];
   
10.      cout << "sum=" << sum << '\n';
    
11.      return 0;
    
12. }

複製代碼

這段碼不論在 dev-c 或 vc 下，都會失敗，它用的只是普通的 static array，
其中 x 只配置了約 4MB 之記憶體大小，程式就跑不過去了，
可知 stack 裡面可用之記憶體大小真的不大，
但這處確實可藉由 compiler IDE 協助，去調整 stack 最大之大小，
即使可以這麼做，但還是不建議這麼做，
你可以想像，一份不是很大的專案，程式一開起來就吃了五、六百MB，
客戶應都會有所抱怨。
這段碼若改成 Dynamic 的話便可正常執行

1. #include <iostream>
   
2. using namespace std;
   
3. #define N 1000000
   
4. int main()
   
5. {
   
6.      int i, sum;
   
7.      int *x = new int[N];
   
8.      for(i=0; i!=N; ++i) x[i]=i;
   
9.      for(i=0; i!=N; ++i) sum+=x[i];
   
10.      cout << "sum=" << sum << '\n';
    
11.      delete [] x;
    
12.      return 0;
    
13. }

複製代碼

用動態方式，只是 4MB，差 XP 上限 2GB/3GB 還少很多。
sum 結果是錯的我知道，這麼做是為了避免 compiler 太過於精，
連配置記憶體都不配置。
如果程式碼變下面這樣的話..

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.      int i, sum;
   
6.      unsigned N=(unsigned)(0-1);
   
7.      int *x = new int[N];
   
8.      for(i=0; i!=N; ++i) x[i]=i;
   
9.      for(i=0; i!=N; ++i) sum+=x[i];
   
10.      cout << "sum=" << sum << '\n';
    
11.      delete [] x;
    
12.      return 0;
    
13. }

複製代碼

裡面大概是要配 4*4G = 16GB 記憶體，這超過 xp 上限太多了，
若真遇到這種問題，大概只有下列幾種方式可解決
a. 換作業系統、加硬體。
b. 換演算法。
c. 將 x 陣列內容寫入檔案裡面去，再做讀取
d. 一台電腦沒 16G，8台電腦就有；8台電腦沒有16G，16台電腦總有吧！
   ( Distrubite Processing System )

-----------

4. 可變長度陣列 (Variable Length Array)

這是在 C99 以後才有的。
也由於 C99 以後才規定，你可以使用這種寫法

1.      int n=10;
   
2.      int x[n] = {0};

複製代碼

早期在 C99 出現時，這都是被禁止的。但 VLA 的出現卻引出來一些爭議，
特別我也是不建議用 VLA 的一群。為何？
再測以下程式碼

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.      int N=1000000;
   
6.      int i, sum;
   
7.      int x[N];
   
8.      for(i=0; i!=N; ++i) x[i]=i;
   
9.      for(i=0; i!=N; ++i) sum+=x[i];
   
10.      cout << "sum=" << sum << '\n';
    
11.      delete [] x;
    
12.      return 0;
    
13. }

複製代碼

雖只有 4MB 記憶體大小，但很遺憾的， VLA 沒辦法配置出來。
我沒確切的資料能說明，VLA 實際上是在 heap 或是 stack 上，
但我的確相信， VLA 是配置在 stack 上而非 heap，
上面程式只是一個推斷的例子而已。

同時 VLA 我認為它的名稱真的取得不是很好 - 可變長度陣列，
但一旦我用了 int x[N] 時，在 x 生命週期結束之前，
它所有可用元素都只有 N 個，沒辦法變大，沒辦法變小，
我認為直接稱它 semi-dynamic array (半動態陣列) 可能還比較合適。

---------------

5. Variable Legnth Array / Dynamic Array

若拿動態陣列與 VLA 做比較，大致上有幾點是可注意的

a. VLA 可宣告的範圍與 Static Array 無二異，甚至會少一點，
   ( 有另一說，VLA 會配置比實際用得元素還多，但那些多配置的就浪費了。)
   
b. 都是 run time 時配置

c. 並非所有 compiler 都支援 VLA，但所有 compiler 都支援 Dynamic Array

d. Dynamic Array 在配置、釋放時花時間，VLA、Static Array 無此問題。

光是 a. 與 c. ，我便主張不用 VLA，Dynamic Array 在 d. 缺點上之表現，
實際上仍有些技巧可改善一直重覆配置的問題，於此便不多談。

---------------

以上若有誤，歡迎不吝指正。...

瀏覽完整內容，請先 註冊 或 登入會員

之前對VLA的概念很朦朧 這篇寫得好詳細！

superjoeliao

受教了
寫得真好
可否再介紹2維的Dynamic Array
謝謝

hkaa88

i think VLA like dynamic , complier gen array size from compile time.
can do this  ?  void f(n) { char x[n]; }

p12332145600

superjoeliao 發表於 2012-3-10 08:47 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

受教了
寫得真好
可否再介紹2維的Dynamic Array

1. int num,x**;
   
2. scanf("%d",&num);
   
3. 
   
4. x=(int **)malloc(num*sizeof(int *));
   
5. for(int y=0;y<num;y++){
   
6.     x[y]=(int*)malloc(num*sizeof(int*));
   
7. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

superjoeliao

感謝指教
那再請教 2維的釋放記憶體的程式要如何實現呢
還請賜教

jo35k6

很棒 現在對VLA 動態陣列, 靜態陣列都有更深一步的認知了.

k85218693

superjoeliao 發表於 2012-3-16 10:20 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

感謝指教
那再請教 2維的釋放記憶體的程式要如何實現呢
還請賜教

1. for(int i = 0; i < num; i++) {
   
2.     free(x[i]);
   
3. }
   
4. free(x);

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

superjoeliao

感謝指導
如此一來這就是一篇
很完整的c語言Dynamic Array

趕緊抓下珍藏

EdisonX

p12332145600 發表於 2012-3-16 09:42 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

二維配置不建議這麼做，原因在於碎片化問題，
沒辦法調用 memset、memcpy 等 function，
...

瀏覽完整內容，請先 註冊 或 登入會員

EdisonX

hkaa88 發表於 2012-3-16 03:23 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

i think VLA like dynamic , complier gen array size from compile time.
can do this  ?  void f(n) { ch ...

no, this article means dynamic array , allocate memory on heaps.
...

瀏覽完整內容，請先 註冊 或 登入會員

果真是精華中的精華，了解不少!!!

10樓的作法真的很不錯耶，把二維陣列配置用一維去模擬，
而且操作和釋放上也十分方便！不過第18行應該是 free(*arr), free(arr);不然好像怪怪的。

orsinobbb

^_^學習了，感謝分享！

chevylin0802

動態記憶體配置的迷思很多
很多的人不是那麼清楚
我必須要在這個地方提出一點基本的建議
在32位元的系統裏
有alignment上的問題
意思就是說 即使配置1個byte的記憶體時 事實上系統是保留了2個word給你
在64位元的系統裏
即使配置1個byte的記憶體 事實上系統仍然是保留了4個word給你
但是
不要以為多配置給你就可以使用
那是很容易出錯的
...

瀏覽完整內容，請先 註冊 或 登入會員