好的 coder 總是有辦法以 1D array 來駕馭高維陣列操作，
但有時使用高維陣列，可讓 code 中的邏輯概念更加清晰。
早期的 C 或目前的 C++ 中，無動態陣列配置的語法，
(在 C99 中才有，例如 gcc 可編譯動態陣列)
因此需要自己實現，底下是我的簡單作法:
設計陣列配置時有 3 點需考量:
1. 配置效率: 最好只呼叫一次 malloc 或 new。
2. 存取效率: 存取速度必須逼近 primary array。
3. 語意: array 的記憶體必須連續分佈。
(所以 vector< vector
只是個 array container... )
N維動態陣列配置較複雜，先從二維的寫起：
(1) 使用 C 語言:
void** new_arr (int size, int x, int y) //size = 元素大小 { int sz = sizeof (void*); void** a = (void **) malloc (sz*x + size*x*y); if (!a) return 0; char* p = (char*)a + sz * x; while (x--) a[x] = p + size*x*y; return a; } void del_arr (void** a) { if (a) free (a); } void set_arr (void** a, int size, int n...) { va_list p; va_start (p, n); memcpy (a[0], p, size*n); } int main () { typedef struct {float f; char c;} CC; CC cc[4] = {0.2,'a', 0.4,'b', 0.6,'c', 0.8, 'd'}; int sz; int **a; char* **b; CC **c; a = (int**) new_arr (sz = sizeof(int), 2,4); set_arr ((void**)a, sz, 2*4, 1,2,3,4, //依序輸入資料 7,8,9,0 ); printf ("%d", a[1][2]); b = (char***) new_arr (sz = sizeof(char*), 2,2); set_arr ((void**)b, sz, 2*2, "陣列","2D", //依序輸入資料 "輸入","範例" ); printf ("\n%s", b[0][1]); c = (CC**) new_arr (sz = sizeof(CC), 2,2); set_arr ((void**)c, sz, 2*2, cc[0], cc[1], //依序輸入資料 cc[2], cc[3] ); printf ("\n%f %c", c[1][0].f, c[0][0].c); del_arr ((void**)a); del_arr ((void**)b); del_arr ((void**)c); }
(2) 使用 C++:
template <class T> struct Array { Array (int x, int y=1): y(y), x(x), p(new T[x*y]) {} ~Array () { for (x*=y; x--; p[x].~T()); delete[] p; } T* operator[] (int i) { return p+i*y; } Array<T>& operator< (T o) { p[n=0] = o; return*this; } Array<T>& operator, (T o) { p[++n] = o; return*this; } private: int x, y, n; T* p; }; int main () { struct CC {float f; char c;} cc[4] = {0.2,'a', 0.4,'b', 0.6,'c', 0.8, 'd'}; Array<int> a (2,4); a < 1,2,3,4, //依序輸入資料 7,8,9,0; cout << a[1][2]; Array<char*> b (2,2); b < "陣列","模版", //依序輸入資料 "輸入","範例"; cout <<endl << b[0][1]; Array<CC> c (2,2); c < cc[0], cc[1], //依序輸入資料 cc[2], cc[3]; cout <<endl << c[1][0].f <<" " << c[0][0].c; }依照相同概念，繼續擴展到 N 維:
C 語言寫法: (此 code 由曾侃的程式修改而來)
#include <stdarg.h> void* new_arr (int size, int nDim, int n...) { static int d[32] = {0}; //限制最多到 32 維 int i,j, nPtr, nElem, sz = sizeof (void*); //指位器與元素數目 void *a, **b, **c, **t; char *p; //a = 動態陣列起始位址 va_list v; va_start (v, nDim); for (i=nDim-1; i>=0; i--) //讀取各個維數 d[i] = va_arg (v, int); if (0 == nDim) return 0; //禁止配置 0 維陣列 d[nDim-1] = n; //糾正Release版別移掉n nPtr = d[1]; //計算指位器表大小 nElem = d[0]*d[1]; //與元素所佔之總空間 for (i=2; i<nDim; i++) ++nPtr*=d[i], nElem*=d[i]; n = nPtr*sz + nElem*size; a = malloc (n); //配置動態陣列空間 if (!a) { printf ("記憶體配置失敗: %d Bytes", n); _getch(); return 0; //若配置失敗則傳回 0 } p = (char*)a + nPtr*sz; //p 指向實際儲存點的開頭位址 b = (void**)p - (nElem /= d[0]); //b 指向第 1D 指位器表的開頭 c = b; i = nElem; //令 c 遍歷指位器表 while (i--) { *c++ = p; p += d[0]*size; } //設定 1D 指位器表的索引位址 for (i=1; i<nDim-1; i++) { //設定 2~N 維指位器表的索引 t = b; //t 指向欲被索引的指位器元素 c = (b -= (nElem /= d[i])); //令 c 遍歷 2~N 維指位器表 for (j=0; j<nElem; j++) *c++ = t, t += d[i]; } return a; }測試程式：
int main () { typedef int**** I4D; int i; I4D a = (I4D) new_arr (sizeof(I4D), 4, 2,3,4,5); for (i=0; i<2*3*4*5; i++) a[0][0][0][i] = i; printf ("\n%d", a[1][1][1][2]); //87 printf ("\n%d", a[1][0][3][1]); //76 del_arr (a); }C++ 寫法:
C++ 動態多維陣列目前最有效率的實作是... 暴力法....
也就是用 template 由 1 維一直特製化到 N 維，
此法速度等同 build-in array，亦是 boost::multi_array 的 4~5 倍..
底下另取它徑，實作一個動態陣列的變形，
改以 array (D1, D2, ...) 的形式來存取陣列元素:
template <class T, int N> struct Array { Array (int d...) //傳入各維的維度 { dim[1] = dim[N] = 1; //確保()能正確存取 memcpy (dim, &d, N*sizeof(int)); //紀錄各維的維度 for (n=dim[N-1], i=N-2; i>=0; i--) n *= dim[i], dim[i] = n; //預先計算累加維度 if (0 == n) cout <<"arr size=0"; //配置錯誤 else p = new T[dim[0]]; //配置實體空間 } T& operator()(int j...) { va_start (v,j); for (n=j*dim[1], i=2; i<=N; ++i) n += dim[i] * va_arg (v,int); //算出索引偏移量 return p[n]; } ~Array () { for (i=dim[0]; i--; p[i].~T()); //解構陣列內元素 delete[] p; } private: int i,n, dim[N+1]; //dim[.] = 各維的維度 va_list v; T* p; //陣列實體 }; int main (/* daviddr 080705 */) { Array<int,4> a(2,3,4,5); for (int i=0; i<2*3*4*5; i++) a(0,0,0,i) = i; cout <<endl<< a(1,1,1,2); //87 cout <<endl<< a(1,0,3,1); //76 }
為了模擬陣列語法，只好再加些又長又醜陋的碼，
於是現在可以用 arr (D1,D2,..Dn) 與 arr [D1][D2]..[Dn]
兩種方法來存取陣列了~
template <typename T, int N=1> struct Array { Array (int d...) //傳入各維的維度 { dim[1] = dim[N] = 1; //確保()能正確存取 memcpy (dim, &d, N*sizeof(int)); //紀錄各維的維度 for (n=dim[N-1], i=N-2; i>=0; i--) n *= dim[i], dim[i] = n; //預先計算累加維度 if (0 == n) cout <<"arr size=0"; //配置錯誤 else p = new T[dim[0]]; //配置實體空間 } T& operator()(int j...) { va_start (v,j); for (n=j*dim[1], i=2; i<=N; ++i) n += dim[i] * va_arg (v,int); //算出索引偏移量 return p[n]; } ~Array () { for (i=dim[0]; i--; p[i].~T()); //解構陣列內元素 delete[] p; } template <typename T, int N> struct Ptr //遞迴定義中繼物件 { Ptr<T,N> (T* t, int* d): p(t), d(d) {} Ptr<T,N-1> operator[] (int n) { return Ptr<T,N-1> (p + n*(*d), d+1); } operator T*() {return p;} private: T* p; int* d; //用來傳遞暫時參數 }; template <typename T> struct Ptr<T,1> //邊界定義 { Ptr (T* t, int*): p(t) {} T& operator[](int n) {return p[n];} operator T*() {return p;} private: T* p; }; Ptr<T,N-1> operator[] (int n) { return Ptr<T,N-1> (p + n*dim[1], dim+2); } operator T*() {return p;} private: int i,n, dim[N+1]; //dim[.] = 各維的維度 va_list v; T* p; //陣列實體 }; template <class T> struct Array<T,1> { Array (int d): d(d), p(new T[d]) {} ~Array () { while (d--) p[d].~T(); delete[] p; } T& operator[] (int n) {return p[n];} T& operator() (int n) {return p[n];} private: T* p; int d; } ; int main (/* daviddr 080705 */) { int i; Array<int,4> a(2,3,4,5); for (i=0; i<2*3*4*5; i++) a(0,0,0,i) = i; cout <<endl<< a(1,1,1,2) //87 <<endl<< a[1][0][3][1] //76 <<endl<< *a[1][0][3]; //75 struct Java { char* tool; float version; } java[3] = {"NetBeans",3.2, "Eclipse",3.5, "JCreator",5.1}; Array<Java> b(3); for (i=0; i<3; i++) b(i) = java[i]; cout <<endl<< b[1].tool <<endl<< b(2).version; }
沒有留言:
張貼留言