2008年12月5日 星期五

C/C++:動態產生陣列

以下為C語言動態產生陣列:

動態產生大小為m的一維陣列:
int n;
int *Array;
  Array = (int *)malloc(n*sizeof(int));

動態產生一個[m][n]陣列 Array 的方法:
int i;
int **Array;
Array= (int **)malloc(m*sizeof(void *));
for (i=0; i<m; i++)
    Array=(int *)malloc(n*sizeof(int *));


但這不夠好,若你要的是一個較大的m*n陣列,那麼太多的malloc
會使記憶體碎片化(memory fragment)!窮則變,變則通
問題既出在for loop不斷的 memory allocation,那就從這下手:

int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *));
pData= (int *)malloc(m*n*sizeof(int));
for (i=0; i<m; i++, pData+=n)
    Array[i]=pData;

注意到嗎?這次只用了二次的malloc。
當要release memory也只要free Array[0] 和 Array 就成了!
(注意先free Array[0] 再 free Array)
如果嫌兩個alloc/free還是太多,也可簡單併成一個:
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *)+m*n*sizeof(int));
for (i=0,pData= (int *)(Array+m); i<m; i++, pData+=n)
    Array[i]=pData;

要 free 時只要 free Array 就行了。
如果用的是C++,那可用的方法就更多了!

以下為C++動態產生陣列:

《幼幼班》嘗試錯誤的階段
Question: int Array[][] = new int [10][20];//這樣行嗎?
當然不行! int Array[][]不是一個指標,而且只能有
一維為不定大小。

《小班》終於會從1數到100了
Question: 那...
Question: int *Array[] = new int [10][20];//這樣行嗎?

有點想法了!但可惜的是 '*' 在 C++的語法是修飾前面的
識別字,所以 int *Array[]的意思是 "Array是一個 int 指標
的一維陣列!"

如果能使那個 '*' 以獨立指標型態去宣告Array,就會變成
"Array是一個指標,指向一維 int 的陣列",而我們知道指標
本身就可以當做一維的陣列,那麼是不是就成了"Array是一個二維
的int陣列"?
對了!這正是我們要的!問題是怎麼讓'*'成為獨立指標型態,
不會去修飾前面的int識別字?答案是使用括號:
int (*Array)[20] = new int [10][20];//這是正解!

但問題又來了, new 運算子可以使用 new int [m][n],但
int (*Array)[20] 的 [20]卻沒辦法以 [n] 來取代,所以就
沒辦法做到不定大小的宣告了。所以這只能算是小班的答案,
要做到不定大小的動態多維宣告,加上 STL 的運用,是不錯
的想法。

《中班》vector 模板的運用
vector<int> *array=new vector<int>[m];
for (int i=0; i<n; i++) array[i].reserve(n);
嘿嘿...不錯吧!?不定大小的二維陣列,而且每個維度還
可以隨時調整大小喔!
不過還是有缺點ㄟ!!那行 for loop 看起來有點礙眼,不能
拿掉嗎?拿掉的話,基本上Array 還是二維陣列,但第二維
並沒有預留空間放東西你可以用push.back等成員函式來增加
空間和存放data,但不能在還沒有空間時使用像
array[5][3]=3; 這種陣列的存取方式。沒更好的方法了嗎?
vector 不是有預留空間大小的建構子嗎?像一維的宣告:
vector<int> *Array= new vector <int>(n);
//這不是預留了 n 個元素的陣列了嗎?
只可惜,這是一維的宣告,若你嘗試做這樣的宣告:
vector<int> *Array= new vector <int>[m](n);
編譯器會給你無情的嘲諷:陣列不能呼叫帶參數的建構子!
這是很令人失望的!為十麼不行?不是邏輯的問題,或許下
一版本的C++會可以這樣宣告吧!但為今之計只能自力救濟
了。

《大班》使用模板在模版中
仔細觀察下面的宣告:
vector<vector<int> > Array(m, vector<int>(n));

不用懷疑!這是相當於宣告一個動態二維不定大小的 int Array[m][n];
不相信的話你可以在m,n範圍內存取 Array[i][j] 看看。
若你能一眼看出這是在幹嘛,那麼你早已超出大班的程度了!
若你暫時不知所云,也沒關係,你可以安全的使用它帶給你的好處。
只是你也只好留在大班留班查看了 ^_^

解釋這個宣告,其實不難,但首先你要對模版的使用有相當的了解,當然
還要對 vector 模版的建構子不能陌生。這樣子自然很容易可以看得懂它。
了然於胸了嗎?恭喜你,大班可以畢業了 ^_@

沒有留言:

張貼留言